Posts published in “Difficulty”

LeetCode 145. Binary Tree Postorder Traversal (javascript)

By stone on April 5, 2021

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

Example 1:

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

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: [2,1]

Constraints:

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

Idea:

Use two stacks:

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack(res[])
   2.2 Push left and right children of the popped node to first stack
3. Pop all elements from second stack(res.reverse())

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 postorderTraversal = function(root) {
    let res = []; // use res as another stack
    // empty tree case:
    if (root === null) return res;
    let stack = [];
    
    // postorder visit: left, right, root
    stack.push(root);
    while (stack.length !== 0) { 
        let cur = stack.pop();
        // treat it as stack, store them in reverse order:
        // i.e root, left, right
        res.push(cur.val); 
        if (cur.left) stack.push(cur.left);
        if (cur.right) stack.push(cur.right);
    }
    
    // we can pop all elements one by one, or just reverse them
    return res.reverse();
};

LeetCode 144. Binary Tree Preorder Traversal (javascript)

By stone on April 5, 2021

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

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Example 4:

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

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:

Create an empty stack and push root node to stack
Do the following while stack is not empty:
1. Pop an item from the stack and store to result array
2. Push right child of a popped item to stack
3. Push left child of a popped item to stack

Right child is pushed first: The right child is pushed before the left child to make sure that the left subtree is processed first.

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 preorderTraversal = function(root) {
    let res = [];
    // empty tree case:
    if (root === null) return res;
    let stack = [];
    
    // preorder visit: root -> left -> right
    // so the right child is pushed before the left child
    // to make sure that the left subtree is processed first.
    stack.push(root);
    while (stack.length !== 0) {
        let cur = stack.pop();
        res.push(cur.val);
        if (cur.right) stack.push(cur.right);
        if (cur.left) stack.push(cur.left);
    }
    return res;
};

LeetCode 110. Balanced Binary Tree (javascript)

By stone on April 5, 2021

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

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

Example 3:

Input: root = []
Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

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 {boolean}
 */
var isBalanced = function(root) {
    if (root === null) return true;
    const res = [true];
    height(root, res);
    return res[0];
};

function height(root, res) {
    if (root === null) return 0;
    const l = height(root.left, res);
    const r = height(root.right, res);
    if (Math.abs(l - r) > 1) res[0] = false;
    return Math.max(l, r) + 1;
}

LeetCode 102. Binary Tree Level Order Traversal (javascript)

By stone on April 4, 2021

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

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

Idea:

Use BFS Template

Note: Don’t forget root === null case

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 levelOrder = function(root) {
    const res = [];
    if (root === null) return res;
    
    const queue = [];
    queue.push(root);
    while(queue.length !== 0) {
        let size = queue.length;
        let level = []; // store same level nodes
        while(size--) {
            let cur = queue.shift();
            level.push(cur.val);
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        res.push(level.concat());
    }
    return res;
};

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 10. Regular Expression Matching (javascript)

By stone on April 4, 2021

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Constraints:

0 <= s.length <= 20
0 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Idea:

Backtracking / Depth-first search (DFS)

There are two normal cases without consideration of *:

1. s === p
2. s !== p, but p === '.' and s is any character

And then let’s consider how to handle the pattern *:

If we have a x* in the pattern(x stands for any character), we may ignore this part of
the pattern, or delete a matching character in the text

// no match: aa , c*                || match: aaa , a*
 (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));

According to these analyses, we can construct a depth-first search algorithm, it’s a recursive algorithm.

Solution:

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let sLen = s.length;
    let pLen = p.length;
    if (pLen === 0) return sLen === 0;
    let first_match = (sLen !== 0 && (p[0] === s[0] || p[0] === '.'));
    
    // If a star is present in the pattern, it will be in the 
    // second position p[1]. Then, we may ignore this part of 
    // the pattern, or delete a matching character in the text. 
    // If we have a match on the remaining strings after any of 
    // these operations, then the initial inputs matched.
    if (pLen >= 2 && p[1] === '*') {
        // no match:  aa , c*       ||      match:       aaa , a*
        return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
    } else {
        return first_match && isMatch(s.substring(1), p.substring(1));
    }
};

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