Press "Enter" to skip to content

Posts tagged as “Medium”

LeetCode 279. Perfect Squares (javascript)

By stone on April 21, 2021

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

Idea: (Dynamic Programing)

  • Time complexity: O(n * sqrt(n))
  • Space complexity: O(n)
dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 = 
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 = 
dp[0] + 5 = 5
 };
so dp[5] = 2

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    // Important: n + 1 length because we use dp[0]
    let dp = new Array(n + 1).fill(Number.MAX_VALUE);
    dp[0] = 0;
    for (let i = 1; i <= n; i++)
        for(let j = 1; j * j <= i; j++)
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    
    return dp[n];
};

LeetCode 79. Word Search (javascript)

By stone on April 19, 2021

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    for (let x = 0; x < board[0].length; x++)
        for (let y = 0; y < board.length; y++)
            if (dfs(board, word, 0, x, y)) return true;
    return false;
};

function dfs(board, word, i, x, y) {
    // exit recursion:
    if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
        return false;
    // found the last letter
    if (i === word.length - 1)
        return true;
    
    let cur = board[y][x];
    // mark it 0 means already visit
    board[y][x] = 0;
    let found = dfs(board, word, i + 1, x + 1, y) || 
                dfs(board, word, i + 1, x - 1, y) ||
                dfs(board, word, i + 1, x, y + 1) ||
                dfs(board, word, i + 1, x, y - 1);
    // recover
    board[y][x] = cur;
    return found;
}

LeetCode 841. Keys and Rooms

By stone on April 18, 2021

There are N rooms and you start in room 0.  Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. 

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length.  A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0). 

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined is at most 3000.

Idea:

DFS

Solution:

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    let visited = [];
    dfs(rooms, visited, 0);
    return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
    // exit recursion:
    if (visited.includes(roomNum)) return;
    
    visited.push(roomNum);
    // possible solution
    for (let key of rooms[roomNum])
        dfs(rooms, visited, key);
}

LeetCode 148. Sort List (javascript)

By stone on April 15, 2021

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

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

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

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 sortList = function(head) {
    // empty or one node
    if (head === null || head.next === null) 
        return head;
    let mid = getMid(head);
    let left = sortList(head);
    let right = sortList(mid);
    return merge(left, right);
};

function merge(list1, list2) {
    let newHead = new ListNode();
    let tail = new ListNode();
    tail = newHead;
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
            tail = tail.next; 
        } else {
            tail.next = list2;
            list2 = list2.next;
            tail = tail.next; 
        }   
    }
    tail.next = (list1 !== null) ? list1 : list2;
    return newHead.next;
};

function getMid(head) {
    let slow = head;
    let fast = head;
    let midHead = null;
    while (fast !== null && fast.next !== null) {
        midHead = slow;
        slow = slow.next
        fast = fast.next.next;
    }
    let secondHalf = midHead.next;
    // !!!Important here:
    // disconnect, split them into two lists
    midHead.next = null;
    return secondHalf;
}

LeetCode 912. Sort an Array (javascript)

By stone on April 14, 2021

Given an array of integers nums, sort the array in ascending order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

Idea:

Use Merge Sort Template

Solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums === null || nums.length === 0) return;
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    // deal with first half
    mergeSort(nums, start, Math.floor((start + end) / 2), temp);
    // deal with second half
    mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
    // merge
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid = Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
            temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = start; i <= end; i++) {
        nums[i] = temp[i];
    }
}

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