Press "Enter" to skip to content

Posts published in “Algorithms”

LeetCode 155. Min Stack (javascript)

By stone on March 28, 2021

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

Idea:

Use two stacks to solve this problem

Solution:

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.min = [];
    this.stack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    let min = this.getMin();
    if (min === undefined || min >= x) {
        this.min.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    let val = this.stack.pop();
    let min = this.getMin();
    if (val === min) this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min[this.min.length - 1];
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

LeetCode 32. Longest Valid Parentheses (javascript)

By stone on March 28, 2021

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Solution:

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let stack = [];
    // track the start position
    let start = 0;
    let ans = 0;
    
    for (let i = 0; i < s.length; i++) {
        // open parenthese '(' push that index of '('
        if (s[i] === '(') {
            stack.push(i);
        } else {
            // if stack empty => invalid, start from i + 1
            if (stack.length === 0) {
                start = i + 1;
            } else {
                stack.pop();
                // empty stack: calculate [start...i]  
                // or Not empty stack calculate [index of '('...i]
                // store the max length
                ans = Math.max(ans, stack.length === 0 ? i - start + 1 : i - stack[stack.length - 1]);
            }
        }
    }
    return ans;
};

LeetCode 20. Valid Parentheses (javascript)

By stone on March 28, 2021

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Idea:

Stack

Solution:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    let open = {'(' : ')', '{' : '}', '[' : ']'};
    let close = {')':true, '}':true, ']': true};
    
    for (let char of s) {
        if (open[char]) {
            stack.push(char);
        } else if (close[char]) {
            if (open[stack.pop()] !== char) return false;
        }
    }
    
    return stack.length === 0;
};

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:

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

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

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

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 258. Add Digits (javascript)

By stone on March 28, 2021

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

Constraints:

  • 0 <= num <= 231 - 1

Idea 1:

recursive

Solution 1:

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    let nums = num.toString().split("");
    let sumOfNums = sum(nums);
        
    // base case:
    if (sumOfNums  < 10) return sumOfNums; 
    return addDigits(sumOfNums);
};

function sum(arr) {
    return arr.reduce((a, b) => parseInt(a) + parseInt(b), 0);
}

Idea 2:

mathematics algorithms in O(1) runtime

Solution 2:

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    return num % 9 ? num % 9 : Math.min(num, 9);
};

LeetCode 172. Factorial Trailing Zeroes (javascript)

By stone on March 28, 2021

Given an integer n, return the number of trailing zeroes in n!.

Follow up: Could you write a solution that works in logarithmic time complexity?

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 104

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    return n < 5 ? 0 : parseInt(n / 5) + trailingZeroes(parseInt(n / 5));
};