Press "Enter" to skip to content

Posts published in “Medium”

94. Binary Tree Inorder Traversal (javascript)

By stone on April 4, 2021

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Idea:

Iterating method using Stack

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let stack = [];
    let res = [];
    
    while(root !== null || stack.length !== 0) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
}

LeetCode 46. Permutations (javascript)

By stone on April 4, 2021

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Idea:

Use DFS template

Solution:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let res = [];
    let cur = [];
    let len = nums.length;
    let used = new Array(len).fill(false);
    dfs(nums, len, res, cur, used);
    return res;
}    
    
function dfs(nums, len, res, cur, used) {
    // exit recursive condition
    if (cur.length === len) {
        res.push(cur.concat());
        return;
    }
    
    // possible solution
    for (let i = 0; i < len; i++) {
        // skip used integer
        if (used[i]) continue;
        
        // modify current state
        used[i] = true;
        cur.push(nums[i]);
        dfs(nums, len, res, cur, used);
        // recover current state
        cur.pop();
        used[i] = false;
    }
}

LeetCode 40. Combination Sum II (javascript)

By stone on April 4, 2021

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Idea:

DFS

  • Important Step: sort the array
  • Create a DFS recursive and keep tracking target value and start index
    • Exit DFS recursive:
      • if (target < 0) return;
      • if (target === 0) record answer and return;
    • For loop (Possible solution) pay attention to:
      • No duplication
      • Candidates can only be used once

Solution:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum2 = function(candidates, target) {
    let res = [];
    let cur = [];
    // Important Step: sort the array
    candidates.sort();
    dfs(res, cur, 0, candidates, target);
    return res;
}

function dfs(res, cur, start, can, target) {
    // exit recursive condition
    if (target < 0) return;
    if (target === 0) {
        res.push(cur.concat());
        return;
    }
    
    for (let i = start; i < can.length; i++) {
        // skip duplicate
        if (i > start && can[i] === can[i - 1]) continue;
        cur.push(can[i]);
        // Each number in candidates may only be used once 
        // in the combination. start from i + 1
        dfs(res, cur, i + 1, can, target - can[i]);
        cur.pop();
    }
    
}

LeetCode 22. Generate Parentheses (javascript)

By stone on April 4, 2021

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

  • 1 <= n <= 8

Idea:

Backtracking

Solution:

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let ans = [];
    backtrack(ans, "", 0, 0, n);
    return ans;
}

function backtrack(ans, cur, open, close, max){
    // exit recursive condition
    if (cur.length === max * 2) {
        ans.push(cur.concat());
        return;
    }
    // possible solution
    if (open < max)
        backtrack(ans, cur + "(", open + 1, close, max);
    if (close < open)
        backtrack(ans, cur + ")", open, close + 1, max);
}

LeetCode 1277. Count Square Submatrices with All Ones (javascript)

By stone on April 3, 2021

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

Idea:

Dynamic Programing

  • dp[i][j] := edge of largest square with bottom right corner at (i, j)
  • base case:
    • dp[0][0], dp[i][0], dp[0][j] = 1 if martix[i][j] = 1
  • The current unit can form the largest square matrix with the left, upper and upper left units. For example, a unit can form a matrix with a side length of 3 with the left, top, and top left units. That can also form a matrix with a side length of 2 and a side length of 1. So:
    • dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])+1 if matrix[i][j] == 1 else 0
  • Return answer:
    • ans = sum of all dp[i][j]

Solution:

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function(matrix) {
    let row = matrix.length;
    let col = matrix[0].length;
    let dp = Array.from(new Array(row), () => new Array(col));
    let sum = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // Basic cases: 
            // dp[0][0], dp[i][0], dp[0][j] cases => has 1, form a square
            dp[i][j] = matrix[i][j];
            
            if (i && j && dp[i][j]) // Why? See Above
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;

            sum += dp[i][j];
        }   
    }
    return sum;
};

LeetCode 1143. Longest Common Subsequence (javascript)

By stone on April 3, 2021

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.

Idea:

Dynamic Programing

Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])

Solution:

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    // Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i-1] and text2[0:j-1]
    // dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])
    let dp = Array.from(new Array(text1.length + 1), () => new Array(text2.length + 1));
    
    // final result dp[i + 1][j + 1] contains length of LCS  
    // for text1[0..i] and text2[0..j], so use <=
    for (let i = 0; i <= text1.length; i++) {
        for (let j = 0; j <= text2.length; j++) {
            // base case:
            if (i === 0 || j === 0) 
                dp[i][j] = 0;
            else if (text1[i - 1] === text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    // dp[text1.length][text2.length] contains length of LCS  
    // for text1[0..text1.length-1] and text2[0..text2.length-1]
    return dp[text1.length][text2.length];
}

LeetCode 300. Longest Increasing Subsequence (javascript)

By stone on April 3, 2021

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

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

Idea:

dp[i] represents the length of the longest increasing subsequence of nums[0...i]
dp[0] = 1
dp[i] = max(dp[j]'s) + 1 if j < i when nums[i] > nums[j]
result: find the max of all dp[i]'s

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        // local max
        let max = 0;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(dp[j], max);
            }
        }
        dp[i] = max + 1;
    }
    // result: find the max of all dp[i]'s
    return Math.max(...dp);
};

LeetCode 64. Minimum Path Sum (javascript)

By stone on April 3, 2021

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Idea:

Dynamic Programing

save space: we just use the original grid to calcuate the min path sum
grid[i][j] represent the min path sum of i x j grid
grid[i][j] = get the min of previous grid(top/left) + current val

Solution:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    // save space: we just use the original grid to calcuate the min path sum
    // grid[i][j] = min path sum of i x j grid
    let m = grid.length;
    let n = grid[0].length;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // grid[0][0] itself contains the min path sum
            if (i === 0 && j === 0) continue;
            // first row: grid[i][j] = previous grid(left) + current val
            if (i === 0) grid[i][j] += grid[i][j - 1];
            // first column: grid[i][j] = previous grid(top) + current val
            else if (j === 0) grid[i][j] += grid[i - 1][j];
            // grid[i][j] = get the min of previous grid(top/left) + current val
            else grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
        }
    }
    return grid[m - 1][n - 1];
}

LeetCode 62. Unique Paths (javascript)

By stone on April 3, 2021

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 109.

Idea:

Dynamic Programing

dp[m][n] = unique paths of m x n grid
// base case:
dp[1][1] = 1; 
// dp[i][j] = top(unique paths) + left(unique paths)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

Solution:

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // one row or one column dp[i][1] = dp[1][j] = 1; Let's fill them all 1
    let dp = Array.from(new Array(m), () => new Array(n).fill(1));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // dp[i][j] = top(unique paths) + left(unique paths)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

LeetCode 5. Longest Palindromic Substring (javascript)

By stone on April 2, 2021

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

Idea:

Dynamic Programing

dp[i][j] = if the substring from i to j is a palindrome = true
dp[i][j] = dp[i+1][j-1] and s[i] === s[j]
base case:
dp[i][i] = true; 
dp[i][i+1] = s[i] === s[i+1];
  • Time complexity : O(n2)
  • Space complexity : O(n2)

Solution:

var longestPalindrome = function(s) {
    let len = s.length;
    if (s === null || len === 1) return s;
    let dp = Array.from(new Array(len), () => new Array(len));
    let res = "";
    let max = 0;
    
    for (let j = 0; j < len; j++) {
        // remember i <= j
        for (let i = 0; i <= j; i++) {
            let isSame = s[i] === s[j];
            
            // one and two letters palindromes only check s[i] === s[j]
            // more than 2, check subset dp[][] && s[i] === s[j]
            dp[i][j] = j - i <= 2 ? isSame : dp[i + 1][j - 1] && isSame;
            
            // any new max palindrome, update max and longest result
            if (dp[i][j] && j - i + 1 > max) {
                max = j - i + 1;
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}