Posts tagged as “array”

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

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