Press "Enter" to skip to content

Posts published in “Difficulty”

LeetCode 129. Sum Root to Leaf Numbers (javascript)

By stone on April 13, 2021

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Idea:

Use DFS Template

Solution 1:

/**
 * 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 sumNumbers = function(root) {
    if (root === null) return;
    let res = [];
    let cur = [];
    dfs(root, res, cur);
    let sum = 0;
    for (let num of res) {
        sum += num;
    }
    return sum;
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur.push(root.val);
        res.push(parseInt(cur.join('')));
        cur.pop();
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur.push(root.val);
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur.pop();
    }
    return;
}

Solution 2: (Version 2)

var sumNumbers = function(root) {
    if (root === null) return;
    let res = [0];
    let cur = [0];
    dfs(root, res, cur);
    return res[0];
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur[0] = cur[0] * 10 + root.val;
        res[0] += cur[0];
        cur[0] = (cur[0] - root.val) / 10;
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur[0] = cur[0] * 10 + root.val;
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur[0] = (cur[0] - root.val) / 10;
    }
    return;
}

LeetCode 198. House Robber (javascript)

By stone on April 12, 2021

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Idea:

Dynamic Programing

Try to look for a pattern, see comments in the code.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // one house
    if (nums.length === 1) return nums[0];
    
    // dp[i] = max money can be taken after visited i houses
    let dp = new Array(nums.length);
    dp[1] = nums[0];
    dp[2] = Math.max(nums[0], nums[1]);
    // two houses
    if (nums.length === 2) return dp[2];
    
    // more houses - try to look for a pattern
    // dp[3] = Math.max(dp[2], dp[1] + nums[2]);
    // dp[4] = Math.max(dp[3], dp[2] + nums[3]);
    // ...
    for (let i = 3; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[nums.length];
};

LeetCode 74. Search a 2D Matrix (javascript)

By stone on April 12, 2021

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Solution 1: (DFS)

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
    let rows = matrix.length;
    let cols = matrix[0].length;
    
    // exit recursion condition, reach to the end;
    if (y === rows) return false;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % cols;
    let nextY = nextX === 0 ? y + 1 : y;

    // found return true or not found, DFS next element
    if (matrix[y][x] === target) 
        return true;
    else
        return dfs(matrix, target, nextX, nextY);

    return false;
}

Solution 2: (Binary Search) Better and Faster!

  • Time complexity: O(log(mn))
  • Space complexity: O(1)
var searchMatrix = function(matrix, target) {
    let cols = matrix[0].length;
    // 	treat 2D as 1D, use binary search
    let l = 0;
    let r = matrix.length * cols;
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        let row = Math.floor(mid / cols);
        let col = mid % cols;
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return false;
};

LeetCode 37. Sudoku Solver (javascript)

By stone on April 11, 2021

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Idea:

Create 3 tracking arrays:
  1 - 9 occur once in whole row, whole col, whole box.
  [ith row][number] [ith col][number] [ith box][number]
  ex: [ith row][N] = 1 means ith row already use number N
DFS/Backtracking
  Travese the board from left to right, row by row
  Try to fill 1-9, success return,
      if not success, recover data and try next element

Solution:

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    // 1 - 9 occur once in whole row, whole col, whole box
    // [ith row][number] [ith col][number] [ith box][number]
    // ex: [ith row][N] = 1 means ith row already use number N
    let rows = Array.from(new Array(9), () => new Array(10).fill(0));
    let cols = Array.from(new Array(9), () => new Array(10).fill(0));
    let boxes = Array.from(new Array(9), () => new Array(10).fill(0));
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const c = board[i][j];
            if (c !== '.') {
                let num = parseInt(c);
                let bx = Math.floor(j / 3);
                let by = Math.floor(i / 3);
                rows[i][num] = 1;
                cols[j][num] = 1;
                boxes[by * 3 + bx][num] = 1;
            }
        }
    }
    dfs(board, 0, 0, rows, cols, boxes);
};

function dfs(board, x, y, rows, cols, boxes) {
    // exit recursion condition, reach to the end;
    if (y === 9) return true;
    
    // traverse from left to right, then next row
    let nextX = (x + 1) % 9;
    let nextY = nextX === 0 ? y + 1 : y;
    
    // already has number, DFS next element
    if (board[y][x] !== '.') return dfs(board, nextX, nextY, rows, cols, boxes);
    
    // fill number from 1 - 9
    for (let i = 1; i <= 9; i++) {
        let bx = Math.floor(x / 3);
        let by = Math.floor(y / 3);
        let box_index = by * 3 + bx;
        // if not breaking the following 3 rules
        if (!rows[y][i] && !cols[x][i] && !boxes[box_index][i]) {
            // modify, fill the number
            rows[y][i] = 1;
            cols[x][i] = 1;
            boxes[box_index][i] = 1;
            board[y][x] = i.toString();
            // Try to fill next element, if success return true, or recover
            if (dfs(board, nextX, nextY, rows, cols, boxes)) return true;
            // recover data
            board[y][x] = '.';
            boxes[box_index][i] = 0;
            cols[x][i] = 0;
            rows[y][i] = 0;
        }
    }
    return false;
}

LeetCode 200. Number of Islands (javascript)

By stone on April 11, 2021

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Idea:

Traverse connected components: Use DFS to traverse 4 directions and mark them “0” if found “1”

Solution:

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let row = grid.length;
    if (row === 0) return 0;
    let col = grid[0].length;
    let res = 0;
    for (let x = 0; x < col ; x++) {
        for (let y = 0; y < row; y++) {
            if (grid[y][x] === "1") {
                res++;
                dfs(grid, x, y, col, row);
            }
        }
    }
    return res;
};

var dfs = function(grid, x, y, n, m) {
    // over boundry cases and not "1" => return
    if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] === "0") return;
    
    // already visited mark it "0"
    grid[y][x] = "0";
    // traverse 4 directions if any "1" => mark them "0"
    dfs(grid, x + 1, y, n, m);
    dfs(grid, x - 1, y, n, m);
    dfs(grid, x, y + 1, n, m);
    dfs(grid, x, y - 1, n, m);
}

LeetCode 230. Kth Smallest Element in a BST (javascript)

By stone on April 11, 2021

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Example 1:

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

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

Idea:

 Recursive Inorder Traversal

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
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    const nums = [];
    inorder(root, nums);
    return nums[k - 1];
};

function inorder(root, nums) {
    if (root === null) return;
    inorder(root.left, nums);
    nums.push(root.val);
    inorder(root.right, nums);
}

LeetCode 206. Reverse Linked List

By stone on April 11, 2021

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

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

Idea: 背口诀

reverse LinkedList 口诀: create newHead and next
next -> head.next -> newHead.next -> head -> next

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // empty or only one node 
    if (head === null || head.next === null) return head;
    
    let newHead = new ListNode();
    let next = new ListNode();
    while (head !== null) {
        // next helper create
        next = head.next;
        // disconnect, and point to newHead.next
        head.next = newHead.next;
        // move newHead.next to head
        newHead.next = head;
        // move head to next location
        head = next;
    }
    return newHead.next;
};

LeetCode 153. Find Minimum in Rotated Sorted Array (javascript)

By stone on April 11, 2021


Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Idea:

Use Binary Search Template

  • Time Complexity: O(logN)
  • Space Complexity: O(1)

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // if only have one number
    if (nums.length === 1) return nums[0];
    
    let l = 0;
    let r = nums.length;
    // if this array is sorted
    if (nums[0] < nums[r - 1]) return nums[0];
    
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        
        // if previous element is greater than next element,
        // next element is the smallest
        if (nums[mid] > nums[mid + 1]) 
            return nums[mid + 1];
        if (nums[mid - 1] > nums[mid]) 
            return nums[mid];
        
        // first half is sorted: min is on right side
        if (nums[mid] > nums[0]) 
            l = mid;
        else
            r = mid + 1;
    } 
    return -1;
};

Solution 2:

var findMin = function(nums) {
    return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
    // exit recursion:
    // only one or two elements in the array
    if (l + 1 >= r)
        return Math.min(nums[l], nums[r]);
    // this array is sorted
    if (nums[l] < nums[r])
        return nums[l];
    
    let mid = l + Math.floor((r - l) / 2);
    return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}

LeetCode 112. Path Sum (javascript)

By stone on April 11, 2021

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:

Input: root = [1,2], targetSum = 0
Output: false

Constraints:

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

Solution: (Recursion)

  • Time complexity: O(n)
  • Space complexity: O(n)
/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    if (root.val === targetSum && root.left === null && root.right === null) return true;
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
};

LeetCode 85. Maximal Rectangle (javascript)

By stone on April 11, 2021

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 0 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.

Idea:

Dynamic Programing

  • Time complexity: O(mn)
  • Space complexity: O(mn)
dp[i][j] := max length of all 1s ends with col j at row i.
dp[i][j] = 0 if matrix[i][j] == "0"
dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"

Then loop through matrix
Min Width(has "1"):= Math.min(width, dp[curRow][j]);
Min Height(has "1"):= curRow - i + 1;
MaxArea = Min Width * Min Height

Solution:

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {    
    let row = matrix.length;
    if (row === 0) return 0;
    let col = matrix[0].length;
    
    // dp[i][j] := max length of all 1s ends with col j at row i.
    // dp[i][j] = 0 if matrix[i][j] == "0"
    // dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"
    let dp = Array.from(new Array(row), () => new Array(col));
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] === "1") {
                dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    let maxArea = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            let width = Infinity;
            for (let curRow = i; curRow < row; curRow++) {
                width = Math.min(width, dp[curRow][j]);
                if (width === 0) break;
                let height = curRow - i + 1;
                maxArea = Math.max(maxArea, width * height);
            }
        }
    }
    return maxArea;
};