Posts published in “Array Operations”

13. Roman to Integer (javascript)

By stone on April 8, 2021

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]];
    }
    return total;
};

12. Integer to Roman (javascript)

By stone on April 8, 2021

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

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

485. Max Consecutive Ones (javascript)

By stone on April 8, 2021

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

LeetCode 442. Find All Duplicates in an Array (javascript)

By stone on April 7, 2021

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

LeetCode 945. Minimum Increment to Make Array Unique (javascript)

By stone on March 28, 2021

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:

0 <= A.length <= 40000
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;
};

LeetCode 581. Shortest Unsorted Continuous Subarray (javascript)

By stone on March 28, 2021

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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵

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

LeetCode 78. Subsets (javascript)

By stone on March 28, 2021

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) {
        // record answer
        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) {
        // record answer
        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();
    }
};

LeetCode 73. Set Matrix Zeroes (javascript)

By stone on March 28, 2021

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

Follow up:

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
-2³¹ <= matrix[i][j] <= 2³¹ - 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;
            }
        }
    }
};

LeetCode 54. Spiral Matrix (javascript)

By stone on March 28, 2021

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

LeetCode 26. Remove Duplicates from Sorted Array (javascript)

By stone on March 26, 2021

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 * 10⁴
-10⁴ <= nums[i] <= 10⁴
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;
};