# Posts tagged as “array”

Roman numerals are represented by seven different symbols: `I``V``X``L``C``D` and `M`.

```Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000```

For example, `2` is written as `II` in Roman numeral, just two one’s added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

```Input: s = "III"
Output: 3
```

Example 2:

```Input: s = "IV"
Output: 4
```

Example 3:

```Input: s = "IX"
Output: 9
```

Example 4:

```Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
```

Example 5:

```Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```

Constraints:

• `1 <= s.length <= 15`
• `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
• It is guaranteed that `s` is a valid roman numeral in the range `[1, 3999]`.

Idea:

• Accumulate the value of each symbol.
• If the current symbol is greater than the previous one, substract twice of the previous value. e.g. IX, 1 + 10 – 2 * 1 = 9

Solution:

• Time complexity: O(n)
• Space complexity: O(1)
``````/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let conversion = {"I": 1, "V":5,"X":10,"L":50,"C":100,"D":500,"M":1000};
let total = 0;

for (var i = 0; i < s.length; i++) {
// first symbol
total += conversion[s[i]];
// if current symbol is bigger than previous symbol
// subtract 2 times of the previous value
if (i > 0 && conversion[s[i]] > conversion[s[i - 1]])
total -= 2 * conversion[s[i - 1]];
}
};``````

Roman numerals are represented by seven different symbols: `I``V``X``L``C``D` and `M`.

```Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000```

For example, `2` is written as `II` in Roman numeral, just two one’s added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

```Input: num = 3
Output: "III"
```

Example 2:

```Input: num = 4
Output: "IV"
```

Example 3:

```Input: num = 9
Output: "IX"
```

Example 4:

```Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
```

Example 5:

```Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```

Constraints:

• `1 <= num <= 3999`

Solution:

``````/**
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
const val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const symbol =["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

let result = "";
for (let i = 0; i < val.length; i++) {
while (num >= val[i]) {
num -= val[i];
result += symbol[i];
}
}

return result;
};``````

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

```Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]```

Idea:

To solve this in O(1) space and O(n) runtime, we have to do some modification in the original array.

In for loop:

• Flipping the index location number (to negative number)
• when we meet the duplicate number, we should see index location is negative, save the result

Solution:

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
const res = [];
for (let i = 0; i < nums.length; i++) {
let index = Math.abs(nums[i]) - 1;
// flipping the index location number (to negative number)
// if we found they are negative, save the result
if (nums[index] < 0) res.push(index + 1); // because index = ABS(nums[i]) - 1
nums[index] = -nums[index];
}
return res;
};``````

Given an array of integers A, a move consists of choosing any `A[i]`, and incrementing it by `1`.

Return the least number of moves to make every value in `A` unique.

Example 1:

```Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].
```

Example 2:

```Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
```

Note:

1. `0 <= A.length <= 40000`
2. `0 <= A[i] < 40000`

Solution:

``````/**
* @param {number[]} A
* @return {number}
*/
var minIncrementForUnique = function(A) {
// sort array first!
A.sort((a, b) => a - b);
let ans = 0;
for (let i = 1; i < A.length; i++) {
// skip if A[i] > A[i - 1], no need to change
if (A[i] > A[i - 1]) continue;
// when A[i] >= A[i - 1] after previous modification
// record how many move to make them unique
ans += (A[i - 1] - A[i]) + 1;
// make A[i] slightly bigger than A[i - 1]
A[i] = A[i - 1] + 1;
}
return ans;
};``````

Given an integer array `nums`, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Example 1:

```Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
```

Example 2:

```Input: nums = [1,2,3,4]
Output: 0
```

Example 3:

```Input: nums = [1]
Output: 0
```

Constraints:

• `1 <= nums.length <= 104`
• `-105 <= nums[i] <= 105`

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function(nums) {
if (!nums || nums.length <= 1) return 0;
let len = nums.length;
let l = 0;
let r = len - 1;

// Scan from left to right and find the first element
// which is greater than the next element
for (; l < len; l++) {
if (nums[l] > nums[l + 1]) break;
}
if (l === len) return 0; // sorted already!
// Scan from right to left and find the first element
// which is smaller than the next element
for (; r > 0; r--) {
if (nums[r] < nums[r - 1]) break;
}

// Find the minimum and maximum values in arr[l..r]
let arr = nums.slice(l, r + 1);
let min = Math.min(...arr);
let max = Math.max(...arr);

// Find the first element (if there is any) in arr[0..l]
// which is greater than min
for (let i = 0; i < l; i++) {
if (nums[i] > min) {
l = i;
break;
}
}

// Find the last element (if there is any) in arr[r..n-1]
// which is smaller than max
for (let i = len ; i > r; i--) {
if (nums[i] < max) {
r = i;
break;
}
}

let gap = r - l + 1;
return gap;
};``````

Given an integer array `nums` of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

```Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

Example 2:

```Input: nums = [0]
Output: [[],[0]]
```

Constraints:

• `1 <= nums.length <= 10`
• `-10 <= nums[i] <= 10`
• All the numbers of `nums` are unique.

Idea:

DFS(Depth First Search)

DFS Template:

``````function dfs(nums, n, start, cur, res...) {
if (exit recursive condition) {
return;
}
for (possible solution) {
// modify current state
dfs(nums, n, i + 1, cur, res...);
// recover current state

}
return something if need // option
};``````

Solution:

``````/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
let cur = [];
let res = [];
for (let i = 0; i <= nums.length; i++) {
dfs(nums, i, 0, cur, res);
}
return res;
};

var dfs = function(nums, n, start, cur, res) {
// exit recursive condition
if (cur.length === n) {
res.push(cur.concat());
return;
}

// possible solution
for (let i = start; i < nums.length; i++) {
// modify current state
cur.push(nums[i]);
dfs(nums, n, i + 1, cur, res);
// recover current state
cur.pop();
}
};``````

Given an `m x n` matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

Example 1:

```Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
```

Example 2:

```Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
```

Constraints:

• `m == matrix.length`
• `n == matrix[0].length`
• `1 <= m, n <= 200`
• `-231 <= matrix[i][j] <= 231 - 1`

Solution:

``````/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
let rowHasZero = [];
let colHasZero = [];

for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === 0) {
rowHasZero.push(i);
colHasZero.push(j);
}
}
}

for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (rowHasZero.includes(i) || colHasZero.includes(j)) {
matrix[i][j] = 0;
}
}
}
};``````

Given an `m x n` `matrix`, return all elements of the `matrix` in spiral order.

Example 1:

```Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
```

Example 2:

```Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 10`
• `-100 <= matrix[i][j] <= 100`

Solution:

``````/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
if (matrix === null) return null
let res = [];
let l = 0;
let t = 0;
let r = matrix[0].length - 1;
let b = matrix.length - 1;
const total = (r + 1) * (b + 1);
let d = 0;
let x = 0;
let y = 0;
while (res.length < total - 1) {
// right
if (d === 0) {
while (x < r) res.push(matrix[y][x++]);
t++; // reach end, turn 90 degree, move down
// down
} else if (d === 1) {
while (y < b) res.push(matrix[y++][x]);
r--; // reach end, turn 90 degree, move left
// left
} else if (d === 2) {
while (x > l) res.push(matrix[y][x--]);
b--; // reach end, turn 90 degree, move up
// up
} else if (d === 3) {
while (y > t) res.push(matrix[y--][x]);
l++; // reach end, turn 90 degree, move up right
}
d = (d + 1) % 4;
}
// last move to the center if exist
if (res.length !== total)
res.push(matrix[y][x]);

return res;
};``````