# Posts published in “Array Operations”

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 a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

```Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
```

Note:

• The input array will only contain `0` and `1`.
• The length of input array is a positive integer and will not exceed 10,000

Solution 1:

``````/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function(nums) {
let max = 0;
let count = 0;
for (let num of nums) {
if (num === 1) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
max = Math.max(max, count);
return max;
}``````

Solution 2:

``````var findMaxConsecutiveOnes = function(nums) {
let max = 0;
let res = 0;
for (let num of nums) {
let sign = 1;
if (num === 0) {
sign = 0;
} else {
sign = 1;
}
max = sign * max + num;
// update max result
if (max > res) res = max;
}
return res;
};``````

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;
};``````

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

```// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}```

Example 1:

```Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = `2`, with the first two elements of `nums` being `1` and `2` respectively. It doesn't matter what you leave beyond the returned length.
```

Example 2:

```Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = `5`, with the first five elements of `nums` being modified to `0`, `1`, `2`, `3`, and `4` respectively. It doesn't matter what values are set beyond the returned length.
```

Constraints:

• `0 <= nums.length <= 3 * 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in ascending order.

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
if(nums === null || nums.length === 0) return 0;
if(nums.length == 1) return 1;
var count = 0;
for(var i = 0; i < nums.length; i++) {
if(nums[i] !== nums[i+1]){
count++;
nums[count] = nums[i+1];
}
}
return count;
};``````