February LeetCoding Challenge 2021

Posted on | In

In January, I spent so much time (almost a month) on calling AT&T and repaired my internet. It also turned out I needed to topup my phone because it exceeded 1 thousand miniutes limit. AT&T’s DSL is slow and not stable. Eventually switched to Comcast and finished setting up a cable.

Week 1: February 1st - February 7th

Squirrel Simulation

There’s a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. The squirrel can only take at most one nut at one time and can move in four directions - up, down, left and right, to the adjacent cell. The distance is represented by the number of moves.

Example 1:

1
2
3
4
5
6
7
8
Input:
Height : 5
Width : 7
Tree position : [2,2]
Squirrel : [4,4]
Nuts : [[3,0], [2,5]]
Output: 12
Explanation:

Squirrel Simulation

Note:

  1. All given positions won’t overlap.

  2. The squirrel can take at most one nut at one time.

  3. The given positions of nuts have no order.

  4. Height and width are positive integers. 3 <= height * width <= 10,000.

  5. The given positions contain at least one nut, only one tree and one squirrel.

Hint 1:

Will Brute force solution works here? What will be its complexity?

Hint 2:

Brute force definitely won’t work here. Think of some simple solution. Take some example and make some observations.

Hint 3:

Will order of nuts traversed by squirrel is important or only first nut traversed by squirrel is important?

Hint 4:

Are there some paths which squirrel have to cover in any case? If yes, what are they?

Hint 5:

Did you notice only first nut traversed by squirrel matters? Obviously squirrel will choose first nut which will result in minimum distance.

Explanation

  1. Except the first nut that the squirrel pick, the distance for picking every other nuts and bring back to the tree is equal to 2 * getLen(tree, nuts[i]). If the squirrel is in the tree, then the result is just 2 * getLen(tree, nuts[i]) for every i. Now the squirrel is not in the tree, so it can save us some distance. For example, t is the tree, x is the squirrel, n and m are two nuts.
1
2
t - - - n - x - m
1 2 3 4 5 6 7 8 9
  1. If the squirrel picks n first, then it can save (5 - 1) * 2 - ((7 - 5) + (5 - 1)) = 2 distance. If the squirrel picks m first, then it can save (9 - 1) * 2 - ((9-7) + (9-1)) = 6 distance. So picking the correct first nut matter.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int getLen(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int res = 0;
        int maxDistSave = Integer.MIN_VALUE;

        for (int i = 0; i < nuts.length; i++) {
            int curLen = getLen(tree, nuts[i]);
            res += curLen * 2;
            maxDistSave = Math.max(maxDistSave, curLen - getLen(squirrel, nuts[i]));
        }

        return res - maxDistSave;
    }
}

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

1
2
3
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

  • The input must be a binary string of length 32

Follow up: If this function is called many times, how would you optimize it?

Explanation

  1. Initialize res is 0. Get the right most bit, use AND, if the right most bit is 1, then n&1 is 1; if the right most bit is 0, then n&1 is 0. No matter is 1 or 0, we add it to res.

  2. In each iteration, we right shift n by 1.

  3. Finally return res.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    if (n & 1) res += 1;
    n >>= 1;
  }
  return res;
};

Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1: Trim a Binary Search Tree

1
2
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Trim a Binary Search Tree

1
2
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Example 3:

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

Example 4:

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

Example 5:

1
2
Input: root = [1,null,2], low = 2, high = 4
Output: [2]

Constraints:

  • The number of nodes in the tree in the range [1, 10^4].

  • 0 <= Node.val <= 10^4

  • The value of each node in the tree is unique.

  • root is guaranteed to be a valid binary search tree.

  • 0 <= low <= high <= 10^4

Explanation

  1. We can use recursion to solve this problem. The base case is if the root is NULL, then we return NULL. Next we check if the root value is less than low, that means this root and its left subtree will be trimed, so we recursively check its right subtree. If the root value is greater than high, that means this root and its right subtree will be trimed, so we recursively check its left subtree. If the root value is in between low and high, then we keep this root and we recursively check both its left and right subtree, and at the end return this root.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    if (root === null) return root;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);

    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);

    return root;
};

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Linked List Cycle

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Linked List Cycle

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Linked List Cycle

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 10^4].

  • -10^5 <= Node.val <= 10^5

  • pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Explanation

  1. Both fast and slow pointers points to the head.

  2. When fast pointer moves two steps, slow pointer move one step.

  3. If fast pointer hits null, then no cycle; else if slow pointer and fast pointer point to the same node, then there’s cycle.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (!head || !head.next) return false;

    let slow = head, fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break;
    }

    return slow === fast;
};

Longest Harmonious Subsequence

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

1
2
3
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 2 * 10^4

  • -10^9 <= nums[i] <= 10^9

Explanation

  1. We can think of each number from the input array is the minimum number, then we need to find how many maximum numbers from the array. The maximum number will just be the minimum number plus 1. When we know the frequency of minimum number and its corresponding maximum number’s frequency, then we know the result will just be frequency of minimum number plus frequency of maximum numbers.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function(nums) {
    let res = 0;
    const hm = new Map();
    for (const num of nums) {
        hm.set(num, hm.get(num) + 1 || 1);
    }
    for (const [curNum, curFreq] of hm.entries()) {
        if (hm.get(curNum + 1)) {
            res = Math.max(res, curFreq + hm.get(curNum + 1));
        }
    }
    return res;
};

Simplify Path

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

  • The path starts with a single slash '/'.

  • Any two directories are separated by a single slash '/'.

  • The path does not end with a trailing '/'.

The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

1
2
3
Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

1
2
3
Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

1
2
3
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

1
2
Input: path = "/a/./b/../../c/"
Output: "/c"

Constraints:

  • 1 <= path.length <= 3000

  • path consists of English letters, digits, period '.', slash '/' or '_'.

  • path is a valid absolute Unix path.

Explanation

  1. First, we can split the input string by "/". Then we can create a stack, iterate the array, if we see .. then we pop, otherwise we push the name of the directory to the stack.

  2. Special case is when we see the . or empty string, we ignore it. And at the end, the most inside directory name is at the top of the stack.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const arr = path.split("/");
    const st = [];

    for (const str of arr) {
        if (str === '..') {
            if (st.length > 0) st.pop();
        } else if (str !== '' && str !== '.') {
            st.push(str);
        }
    }

    if (st.length === 0) return '/';

    return '/' + st.join('/');
};

Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Binary Tree Right Side View

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

Example 2:

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

Example 3:

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

Constraints:

  • The number of nodes in the tree is in the range [0, 100].

  • -100 <= Node.val <= 100

Explanation 1

  1. In each level, we want to get the most right node. So we can use level-order traversal to solve this problem.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 rightSideView = function(root) {
    if (root === null) return [];
    const res = [];
    const queue = [];

    queue.push(root);
    while (queue.length > 0) {
        for (let i = queue.length - 1; i >= 0; i--) {
            const cur = queue.shift();
            if (i === 0) res.push(cur.val);
            if (cur.left !== null) queue.push(cur.left);
            if (cur.right !== null) queue.push(cur.right);
        }
    }

    return res;
};

Explanation 2

  1. We can also use recursion to solve this problem. First, we create a result list. Pass the result list, the tree root, and the level (depth) which initialize to 0 to the helper function.

  2. In the helper function, the basecase is if the tree node is empty, we immediately return. If the size of the result list is equal to the depth, then we add the tree node value to the result list. Then we recursively call the helper function with the tree node’s right child first, then recursively call the helper function with the tree node’s left child.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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 rightSideView = function(root) {
    const res = [];
    helper(root, res, 0);
    return res;
};

var helper = function(root, res, level) {
    if (root === null) return;

    if (res.length === level) res.push(root.val);
    helper(root.right, res, level + 1);
    helper(root.left, res, level + 1);
}

Shortest Distance to a Character

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

Example 1:

1
2
3
4
5
6
7
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 3.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

Example 2:

1
2
Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:

  • 1 <= s.length <= 10^4

  • s[i] and c are lowercase English letters.

  • It is guaranteed that c occurs at least once in s.

Explanation

  1. We can solve this problem in 2 pass. First pass is looping from left to right and we only consider the distance to c where c is on the left side. Second pass is looping from right to left and now we take the minimum between the current (distance to left side) and the distance to the right side c, in other word, res[i] = min(res[i], res[i + 1] + 1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    const res = Array(s.length).fill(s.length);

    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            res[i] = 0;
        } else if (i > 0) {
            res[i] = res[i-1] + 1;
        }
    }

    for (let i = s.length - 2; i >= 0; i--) {
        res[i] = Math.min(res[i], res[i+1] + 1);
    }

    return res;
};

Week 2: February 8th - February 14th

Number of Distinct Islands

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Example 1:

1
2
3
4
11000
11000
00011
00011

Given the above grid map, return 1.

Example 2:

1
2
3
4
11011
10000
00001
11011

Given the above grid map, return 3.

Notice that:

1
2
11
1

and

1
2
 1
11

are considered different island shapes, because we do not consider reflection / rotation.

Note: The length of each dimension in the given grid does not exceed 50.

Explanation

  1. The difficult part about this problem is how to record the distinct island. We solve it by using a set of strings. Each string is represented by the direction of 1s. In the main method, if grid[r][c] equals to 1, then we enter the flood fill helper method and we append a string "o" (origin) to the builder. Inside the helper method, if the top direction is 1, then we append a string "t" (top) to the builder, similarily for right, down and left directions. After we finish checking the 4 directions, we also need to append a string "b" (backtrack) to the builder because this can record how deep of the recursive helper method we backtrack. In the main method, after the helper method, we can append the string builder into our set. At the end, we can just return set.size().

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    int[] dirs = new int[]{0, 1, 0, -1, 0};
    String[] dirsStr = new String[]{"t", "r", "d", "l"};

    void helper(int[][] grid, int r, int c, StringBuilder sb, String cur) {
        int row = grid.length, col = grid[0].length;

        grid[r][c] = 0;
        sb.append(cur);

        for (int i = 0; i < dirs.length - 1; i++) {
            int nr = r + dirs[i];
            int nc = c + dirs[i+1];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 1) {
                helper(grid, nr, nc, sb, dirsStr[i]);
            }
        }

        sb.append("b");
    }

    public int numDistinctIslands(int[][] grid) {
        int row = grid.length, col = grid[0].length;

        Set<String> set = new HashSet<>();

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == 1) {
                    StringBuilder sb = new StringBuilder();
                    helper(grid, r, c, sb, "o");
                    set.add(sb.toString());
                }
            }
        }

        return set.size();
    }
}

Peeking Iterator

Design an iterator that supports the peek operation on a list in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

  • PeekingIterator(int[] nums) Initializes the object with the given integer array nums.

  • int next() Returns the next element in the array and moves the pointer to the next element.

  • bool hasNext() Returns true if there are still elements in the array.

  • int peek() Returns the next element in the array without moving the pointer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

Constraints:

  • 1 <= nums.length <= 1000

  • 1 <= nums[i] <= 1000

  • All the calls to next and peek are valid.

  • At most 1000 calls will be made to next, hasNext, and peek.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Hint 1:

Think of “looking ahead”. You want to cache the next element.

Hint 2:

Is one variable sufficient? Why or why not?

Hint 3:

Test your design with call order of peek() before next() vs next() before peek().

Hint 4:

For a clean implementation, check out Google’s guava library source code.

Explanation

  1. In java, we extends iterator interface, and it already has hasNext and next methods. We can use these methods to help us, and we should add the peek method.

  2. In the constructor, we initialize an iterator iter equals to the argument iterator, and we cache the nex integer value and hasNex boolean value by checking if iterator hasNext and update nex = iterator.next() and hasNex = true. Else we can just set hasNex = false. So in the peek method, we just retur nex. In the hasNext method, we just return hasNex.

  3. In the next method, saved the return value nex as temp and return it at the end. Before we return temp, if iter hasNext, then we update nex to iter.next() and hasNex to true, which is same as the constructor.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * // This is the Iterator's API interface.
 * // You should not implement it, or speculate about its implementation.
 * function Iterator() {
 *    @ return {number}
 *    this.next = function() { // return the next number of the iterator
 *       ...
 *    };
 *
 *    @return {boolean}
 *    this.hasNext = function() { // return true if it still has numbers
 *       ...
 *    };
 * };
 */

/**
 * @param {Iterator} iterator
 */
var PeekingIterator = function(iterator) {
    this.iter = iterator;

    if (this.iter.hasNext()) {
        this.nex = this.iter.next();
        this.hasNex = true;
    } else {
        this.hasNex = false;
    }
};

/**
 * @return {number}
 */
PeekingIterator.prototype.peek = function() {
    return this.nex;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.next = function() {
    if (!this.hasNex) throw new Error('NoSuchElementException');

    const res = this.nex;

    if (this.iter.hasNext()) {
        this.nex = this.iter.next();
        this.hasNex = true;
    } else {
        this.hasNex = false;
    }

    return res;
};

/**
 * @return {boolean}
 */
PeekingIterator.prototype.hasNext = function() {
    return this.hasNex;
};

/**
 * Your PeekingIterator object will be instantiated and called as such:
 * var obj = new PeekingIterator(arr)
 * var param_1 = obj.peek()
 * var param_2 = obj.next()
 * var param_3 = obj.hasNext()
 */

Convert BST to Greater Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node’s key.

  • The right subtree of a node contains only nodes with keys greater than the node’s key.

  • Both the left and right subtrees must also be binary search trees.

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Example 1:

Convert BST to Greater Tree

1
2
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

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

Example 3:

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

Example 4:

1
2
Input: root = [3,2,4,1]
Output: [7,9,4,10]

Constraints:

  • The number of nodes in the tree is in the range [0, 10^4].

  • -10^4 <= Node.val <= 10^4

  • All the values in the tree are unique.

root is guaranteed to be a valid binary search tree.

Explanation

  1. We can use in order traversal to solve this problem, but instead from the smallest element to the largest, we go from the largest to the smallest. Each time after we update the node’s value, we also update sum equals to that node’s value, so it’s accumulating the sum of all the right nodes.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 {TreeNode}
 */
var convertBST = function(root) {
    let sum = 0;

    const helper = function(root) {
        if (root === null) return;

        helper(root.right);

        root.val += sum;
        sum = root.val;

        helper(root.left);
    }

    helper(root);

    return root;
};

Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val

  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Copy List with Random Pointer

1
2
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Copy List with Random Pointer

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

Example 3:

Copy List with Random Pointer

1
2
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

1
2
3
Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

Constraints:

  • 0 <= n <= 1000

  • -10000 <= Node.val <= 10000

  • Node.random is null or is pointing to some node in the linked list.

Hint 1:

Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, make sure you are not making multiple copies of the same node.

Hint 2:

You may want to use extra space to keep old node —> new node mapping to prevent creating multiples copies of same node.

Hint 3:

We can avoid using extra space for old node —> new node mapping, by tweaking the original linked list. Simply interweave the nodes of the old and copied list. For e.g.

1
2
Old List: A --> B --> C --> D
InterWeaved List: A --> A' --> B --> B' --> C --> C' --> D --> D'

Hint 4:

The interweaving is done using next pointers and we can make use of interweaved structure to get the correct reference nodes for random pointers.

Explanation 1

  1. We can solve this problem by creating a hashmap that maps the original node with its newly copied node. After creating a hashmap, loop from the head again, each iteration, we can easily set the current copied node hm[curNode]’s next node to hm[curNode.next], and the random node to hm[curNode.random].

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if (!head) return head;
    const hm = new Map();

    let cur = head;
    while (cur) {
        const cpyNode = new Node(cur.val);
        hm.set(cur, cpyNode);
        cur = cur.next;
    }

    cur = head;
    while (cur) {
        hm.get(cur).next = hm.get(cur.next) || null;
        hm.get(cur).random = hm.get(cur.random) || null;
        cur = cur.next;
    }

    return hm.get(head);
};

Explanation 2

  1. In the above method, we used hashmap that costs extra space. This method can save space.

  2. First, we copy a new node behind each node.

  3. Then, we can assign new node’s random pointer by doing cur.next.random = cur.random.next.

  4. Finally, we can cut off the original node and copied node’s list.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if (!head) return head;

    let cur = head;
    while (cur) {
        const cpyNode = new Node(cur.val);
        cpyNode.next = cur.next;
        cur.next = cpyNode;
        cur = cur.next.next;
    }

    cur = head;
    while (cur) {
        if (cur.random) cur.next.random = cur.random.next;
        cur = cur.next.next;
    }

    cur = head;
    const res = cur.next;
    while (cur) {
        const temp = cur.next;
        cur.next = temp.next;
        if (temp.next) temp.next = temp.next.next;
        cur = cur.next;
    }

    return res;
};

Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Note:

You may assume the string contains only lowercase alphabets.

Follow up:

What if the inputs contain unicode characters? How would you adapt your solution to such case?

Explanation

  1. If these two strings have different length, we can return false.

  2. Since all string characters are lower case, we can create an array with size 26 to store the frequency of the characters. In the first loop, we count the frequency of string s.

  3. In the second for loop of t, we decrease the array’s frequency. If any one element has negative frequency, we return false.

  4. Outside of the two for loop, we return true as the result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    const arr = Array(26).fill(0);
    for (const ch of s) arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
    for (const ch of t) arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)] -= 1;
    return arr.every(freq => freq === 0);
};

Number of Steps to Reduce a Number to Zero

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

1
2
3
4
5
6
7
8
9
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

1
2
3
4
5
6
7
Input: num = 8
Output: 4
Explanation:
Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

1
2
Input: num = 123
Output: 12

Constraints:

  • 0 <= num <= 10^6

Hint 1:

Simulate the process to get the final answer.

Explanation 1

  1. We can use brute force to solve this problem.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps  = function(num) {
    let res = 0;
    while (num > 0) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num -= 1;
        }
        res += 1;
    }
    return res;
};

Explanation 2

  1. We can also use bit manipulation to solve this problem.

  2. We AND the num by 1, if the result is 1, that means it’s odd number, so we increase counter by 2; else if the result is 0, then it is even number, so we increase counter by 1. One corner case is when num equals to 1, it’s odd number, but this time we only increase the counter by 1.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps  = function(num) {
    if (num === 0) return 0;

    let res = 0;
    while (num > 0) {
        res += (num % 2 === 0 ? 1 : 2);
        num >>= 1;
    }

    return res - 1;
};

Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

  • All the visited cells of the path are 0.

  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Shortest Path in Binary Matrix

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

Example 2:

Shortest Path in Binary Matrix

1
2
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

1
2
Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

  • n == grid.length

  • n == grid[i].length

  • 1 <= n <= 100

  • grid[i][j] is 0 or 1

Hint 1:

Do a breadth first search to find the shortest path.

Explanation

  1. We can solve this problem using BFS.

  2. First we check if the top left element and bottom right element is 1 or not, if it’s 1, then we return the result as -1 immediately. Next, we create a queue and push the top left position [0, 0] into the queue and mark it as visited by updating grid[0][0] = 2. While the queue is not empty, we loop through all the current level’s elements and pop them. For the current popped element, we loop through its 8 neighbors, if the neighbor is 0, then we push it into the queue and mark it as visited. After we finishing looping the current level, we increase the level or res by 1. When we pop the element from the queue, the pop element is located at the bottom right, then we return res + 1. Outside the queue, that means we don’t can’t go to bottom right, so we return -1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    const dirs = [-1, 0, 1, 0, -1, -1, 1, 1, -1];
    const row = grid.length, col = grid[0].length;
    if (grid[0][0] === 1 || grid[row-1][col-1] === 1) return -1;

    let res = 0;
    const queue = [];
    grid[0][0] = 2;
    queue.push([0, 0]);
    while(queue.length > 0) {
        res += 1;
        for (let i = queue.length - 1; i >= 0; i--) {
            const cur = queue.shift();
            const curRow = cur[0];
            const curCol = cur[1];
            grid[curRow][curCol] = 2;
            if (curRow === row - 1 && curCol === col - 1) {
                return res;
            }

            for (let j = 0; j < dirs.length - 1; j++) {
                const nr = curRow + dirs[j];
                const nc = curCol + dirs[j+1];
                if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] === 0) {
                    grid[nr][nc] = 2;
                    queue.push([nr, nc]);
                }
            }
        }
    }

    return -1;
};

Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

There are no self-edges (graph[u] does not contain u). There are no parallel edges (graph[u] does not contain duplicate values). If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example 1:

Is Graph Bipartite?

1
2
3
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Is Graph Bipartite?

1
2
3
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

  • graph.length == n

  • 1 <= n <= 100

  • 0 <= graph[u].length < n

  • 0 <= graph[u][i] <= n - 1

  • graph[u] does not contain u.

  • All the values of graph[u] are unique.

  • If graph[u] contains v, then graph[v] contains u.

Explanation 1

  1. We can rephrase this problem to use two colors to color the graph, if there are two connected nodes have the same color, then we return false, else return true.

  2. First, initialize an array colors[] to store all nodes’ color. 0 means the node haven’t colored yet, 1 means blue, -1 means red. We can loop through all the nodes, if the current node haven’t colored yet, then we color it, then we can use DFS to color its neighbor nodes with a different color. Inside the helper method, first we check if the node already has color, then we if this color is the same as the color we are going to color, then we return true, else we can return false immediately.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function(graph) {
    const n = graph.length;
    const colors = Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        if (colors[i] === 0) {
            if (!helper(graph, colors, i, 1)) {
                return false;
            };
        }
    }

    return true;
};

var helper = function(graph, colors, v, color) {
    if (colors[v] !== 0) return colors[v] === color;

    colors[v] = color;

    for (const neighbor of graph[v]) {
        if (!helper(graph, colors, neighbor, -color)) {
            return false;
        }
    }

    return true;
}

Explanation 2

  1. We can also use BFS to solve this problem.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function(graph) {
    const n = graph.length;
    const colors = Array(n).fill(0);
    const queue = [];

    for (let i = 0; i < n; i++) {
        if (colors[i] !== 0) continue;
        colors[i] = 1;
        queue.push(i);

        while (queue.length > 0) {
            const cur = queue.shift();
            for (const neighbor of graph[cur]) {
                if (colors[neighbor] === 0) {
                    colors[neighbor] = -colors[cur];
                    queue.push(neighbor);
                } else if (colors[neighbor] !== -colors[cur]) {
                    return false;
                }
            }
        }
    }

    return true;
};

Week 3: February 15th - February 21st

Kill Process

You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the ith process and ppid[i] is the ID of the ith process’s parent process.

Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.

Example 1:

Kill Process

1
2
3
Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.

Example 2:

1
2
Input: pid = [1], ppid = [0], kill = 1
Output: [1]

Constraints:

  • n == pid.length

  • n == ppid.length

  • 1 <= n <= 5 * 10^4

  • 1 <= pid[i] <= 5 * 10^4

  • 0 <= ppid[i] <= 5 * 10^4

  • Only one process has no parent.

  • All the values of pid are unique.

  • kill is guaranteed to be in pid.

Explanation 1

  1. We need to kill the process kill and all its children process. We can solve it by creating a hashmap, key is the parent process id, value is a list of its children process id. Then we can use BFS to traverse all the children process under process kill.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, List<Integer>> hm = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            hm.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(kill);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res.add(cur);
            for (int child: hm.getOrDefault(cur, new ArrayList<>())) {
                queue.offer(child);
            }
        }
        return res;
    }
}

Explanation 2

  1. We can also use DFS recursively to record all the processes under id kill.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    void helper(Map<Integer, List<Integer>> hm, List<Integer> res, int kill) {
        res.add(kill);
        for (int child: hm.getOrDefault(kill, new ArrayList<>())) {
            helper(hm, res, child);
        }
    }

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, List<Integer>> hm = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            hm.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        helper(hm, res, kill);
        return res;
    }
}

The K Weakest Rows in a Matrix

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1’s will appear to the left of all the 0’s in each row.

A row i is weaker than a row j if one of the following is true:

  • The number of soldiers in row i is less than the number of soldiers in row j.

  • Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: mat =
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers in each row is:
- Row 0: 2
- Row 1: 4
- Row 2: 1
- Row 3: 2
- Row 4: 5
The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: mat =
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]],
k = 2
Output: [0,2]
Explanation:
The number of soldiers in each row is:
- Row 0: 1
- Row 1: 4
- Row 2: 1
- Row 3: 1
The rows ordered from weakest to strongest are [0,2,3,1].

Constraints:

  • m == mat.length

  • n == mat[i].length

  • 2 <= n, m <= 100

  • 1 <= k <= m

  • matrix[i][j] is either 0 or 1.

Hint 1:

Sort the matrix row indexes by the number of soldiers and then row indexes.

Explanation 1

  1. We can loop through every row of the matrix, for each row, we can use binary search to count the number of soldiers, then make a pair of [rowIdx, numSoldiers]. Next, we push this pair into an array or PriorityQueue that is sorted base on the problem description. At the end, we return the first K weakest rows.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    const pq = new PriorityQueue((a, b) => {
        if (a[1] === b[1]) {
            return a[0] - b[0];
        } else {
            return a[1] - b[1];
        }
    });

    for (let i = 0; i < mat.length; i++) {
        const cnt = helper(mat[i]);
        pq.push([i, cnt]);
    }

    const res = [];
    while (k > 0) {
        const idx = pq.shift()[0];
        res.push(idx);
        k -= 1;
    }

    return res;
};

var helper = function(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2) + 1;
        if (arr[mid] === 0) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    if (arr[right] === 1) return right + 1;
    return 0;
}

var PriorityQueue = function(cb) {
    this.arr = [];
    this.compare = cb;
}

PriorityQueue.prototype.push = function bottomUp(val) {
    this.arr.push(val);
    if (this.arr.length === 1) return;

    let idx = this.arr.length - 1;
    while (idx > 0) {
        const parentIdx = Math.floor((idx - 1) / 2);
        const parent = this.arr[parentIdx];

        if (this.compare(val, parent) < 0) {
            [this.arr[idx], this.arr[parentIdx]] = [this.arr[parentIdx], this.arr[idx]];
            idx = parentIdx;
        } else {
            break;
        }
    }
};

PriorityQueue.prototype.shift = function topDown() {
    const minNode = this.arr[0] || {};
    const lastNode = this.arr.pop();
    if (this.arr.length < 1) return minNode;

    this.arr[0] = lastNode;
    let idx = 0;
    while (idx < this.arr.length) {
        const leftIdx = 2 * idx + 1;
        const rightIdx = 2 * idx + 2;
        const leftNode = this.arr[leftIdx] || {};
        const rightNode = this.arr[rightIdx] || {};

        let smallerIdx;
        if (this.compare(leftNode, lastNode) < 0) {
            smallerIdx = leftIdx;
        }
        if (!smallerIdx && this.compare(rightNode, lastNode) < 0) {
            smallerIdx = rightIdx;
        }
        if (smallerIdx && this.compare(rightNode, leftNode) < 0) {
            smallerIdx = rightIdx;
        }
        if (!smallerIdx) {
            break;
        }

        [this.arr[idx], this.arr[smallerIdx]] = [this.arr[smallerIdx], this.arr[idx]];
        idx = smallerIdx;
    }

    return minNode;
};

PriorityQueue.prototype.peek = function() {
    return this.arr[0];
}

Explanation 2

  1. We can also use a number score to represent both the numSoldiers and rowIdx. The formula is score = numSoldiers * row + rowIdx. We can get numSoldiers = score / row and rowIdx = score % row.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    const pq = [];

    for (let i = 0; i < mat.length; i++) {
        const cnt = helper(mat[i]);
        const score = cnt * mat.length + i;
        pq.push(score);
    }
    pq.sort((a, b) => a - b);

    const res = [];
    while (k--) {
        const idx = pq.shift() % mat.length;
        res.push(idx);
    }

    return res;
};

var helper = function(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2) + 1;
        if (arr[mid] === 0) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    if (arr[right] === 1) return right + 1;
    return 0;
}

Letter Case Permutation

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output in any order.

Example 1:

1
2
Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

1
2
Input: S = "3z4"
Output: ["3z4","3Z4"]

Example 3:

1
2
Input: S = "12345"
Output: ["12345"]

Example 4:

1
2
Input: S = "0"
Output: ["0"]

Constraints:

  • S will be a string with length between 1 and 12.

  • S will consist only of letters or digits.

Explanation 1

  1. We can use BFS to solve this problem. First putting the input string to the queue first.

  2. Loop i through each character of the input string. If the current character is a digit, then we continue. Else, we loop j the current queue’s size, each time we poll the string out of the queue, then convert it to an array and update the index i character to lower case and append the updated string to the queue, similarlly, we also update the index i character to upper case and append the updated string to the queue.

  3. At the end, the queue contains all the permutations.

  4. For example, if the input string is abc, then we have:

1
2
3
4
  [abc] put input string to the queue
  [abc, Abc] updated index 0
  [abc, aBc, Abc, ABc] updated index 1
  [abc, abC, aBc, aBC, Abc, AbC, ABc, ABC] updated index 2

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
    const queue = [S];

    for (let i = 0; i < S.length; i++) {
        if (!isAlpha(S[i])) continue;

        for (let j = queue.length - 1; j >= 0; j--) {
            const curS = queue.shift();
            const lowerS = replace(curS, i, S[i].toLowerCase());
            queue.push(lowerS);
            const upperS = replace(curS, i, S[i].toUpperCase());
            queue.push(upperS);
        }
    }

    return queue;
};

var isAlpha = function(ch) {
    return /[A-Z]/i.test(ch);
}

var replace = function(str, index, replacement) {
    return str.substr(0, index) + replacement + str.substr(index + replacement.length);
}

Explanation 2

  1. Based on the above explanation, we can also use DFS to solve this problem. In the helper function, we pass the array representation of the input string, the result list, and the current index of the string. We want to use the index to mutate the arr[index] character.

  2. The base case is if the index is equal to the length of the array, we add the string representation of the array to the result list.

  3. If arr[index] is a number, then we recursively call the helper function and pass index++. Else, we mutate the index character arr[index] be lower case and pass to the helper function with updated index be index++, and mutate one more time be upper case and pass to the helper function.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
    const res = [];
    helper(S, res, 0);
    return res;
};

var helper = function(S, res, curIdx) {
    if (curIdx === S.length) {
        res.push(S);
        return;
    }

    if (!isAlpha(S[curIdx])) {
        helper(S, res, curIdx+1);
    } else {
        helper(replace(S, curIdx, S[curIdx].toLowerCase()), res, curIdx+1);
        helper(replace(S, curIdx, S[curIdx].toUpperCase()), res, curIdx+1);
    }
}

var isAlpha = function(ch) {
    return /[A-Z]/i.test(ch);
}

var replace = function(str, index, replacement) {
    return str.substr(0, index) + replacement + str.substr(index + replacement.length);
}

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Container With Most Water

1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

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

Example 3:

1
2
Input: height = [4,3,2,1,4]
Output: 16

Example 4:

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

Constraints:

  • n == height.length

  • 2 <= n <= 10^5

  • 0 <= height[i] <= 10^4

Hint 1:

The aim is to maximize the area formed between the vertical lines. The area of any container is calculated using the shorter line as length and the distance between the lines as the width of the rectangle.

1
Area = length of shorter vertical line * distance between lines

We can definitely get the maximum width container as the outermost lines have the maximum distance between them. However, this container might not be the maximum in size as one of the vertical lines of this container could be really short.

Container With Most Water

Container With Most Water

Hint 2:

Start with the maximum width container and go to a shorter width container if there is a vertical line longer than the current containers shorter line. This way we are compromising on the width but we are looking forward to a longer length container.

Explanation

  1. We calculate the area by multipling the x-axis with the height, specifically the min height between the two bar.

  2. When two bars at the beginning and at the end, the x-axis is the largest. So, we starts from here and use two pointers technique. We first calcualte the area with two bar at both end, then compare those two bars. If the left bar is shorter, we move it to the next bar, and compute the area. Else, if the right bar is shorter, then we move it to the previous bar and compute the area. Until the left pointer is greater or equal to the right pointer, we break out and return the maximum area.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0, right = height.length - 1;
    let area = 0;

    while (left < right) {
        area = Math.max(area, (right - left) * Math.min(height[left], height[right]));
        if (height[left] < height[right]) {
            left += 1;
        } else {
            right -= 1;
        }
    }

    return area;
};

Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

1
2
3
Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

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

Constraints:

  • 1 <= nums.length <= 5000

  • -1000 <= nums[i] <= 1000

Explanation

  1. [1,2,3] has 1 arithmetic slice. [1,2,3,4] has 3 arithmetic slices. [1,2,3,4,5] has 6 arithmetic slices, which are:

    1
    2
    3
    4
    5
    6
    7
     ```
 len = 3: [1,2,3], [2,3,4], [3,4,5]

 len = 4: [1,2,3,4], [2,3,4,5]

 len = 5: [1,2,3,4,5]
 ```

  2. When len is equals to arr.length, then we have 1 arithmetic slice. When len = arr.length-1, then we have 2 arithmetic slice. When len = arr.length-3, then we have 3 arithmetic slices. Therefore, the total arithmetic slice will be 1 + 2 + 3 + ... + n-2. In other words, (n-1)(n-2)/2.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    if (nums.length < 3) return 0;
    let res = 0;
    let cnt = 2;

    for (let i = 2; i < nums.length; i++) {
        if (nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
            cnt += 1;
        } else {
            res += (cnt-1) * (cnt-2) / 2;
            cnt = 2;
        }
    }

    if (cnt > 2) {
        res += (cnt-1) * (cnt-2) / 2;
    }

    return res;
};

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
    if (nums.length < 3) return 0;
    let res = 0;
    let cur = 0;

    for (let i = 2; i < nums.length; i++) {
        if (nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
            cur += 1;
            res += cur;
        } else {
            cur = 0;
        }
    }

    return res;
};

Minimum Remove to Make Valid Parentheses

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, contains only lowercase characters, or

  • It can be written as AB (A concatenated with B), where A and B are valid strings, or

  • It can be written as (A), where A is a valid string.

Example 1:

1
2
3
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

1
2
Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

1
2
3
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

1
2
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Constraints:

  • 1 <= s.length <= 10^5

  • s[i] is one of '(' , ')' and lowercase English letters.

Hint 1:

Each prefix of a balanced parentheses has a number of open parentheses greater or equal than closed parentheses, similar idea with each suffix.

Hint 2:

Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.

Explanation

  1. We need to remove the minimum number of parentheses to make the rest of parentheses valid, so we can think of this problem’s input doesn’t contain any letter.

  2. We can verify a valid pair of parentheses by pushing left parenthese into the stack, if we see right parenthese, then we pop the stack, but If the stack is empty, then we know the current right parenthese is invalid, so we can increase the count for removing right parenthese. After we finish looping all characters of the string, if the stack is not empty, then the stack size is the count for removing left parenthese.

  3. Now we have both the count for removing left parenthese and right parenthese. We can remove these extra left parenthese from right to left, and remove extra right parenthese from left to right.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    let removeLeftCnt = 0;
    // let removeRightCnt = 0;

    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch === '(') {
            removeLeftCnt += 1;
        } else if (ch === ')') {
            if (removeLeftCnt === 0) {
                // removeRightCnt += 1;
                s = replace(s, i, '#');
            } else {
                removeLeftCnt -= 1;
            }
        }
    }

    for (let i = s.length - 1; i >= 0; i--) {
        if (removeLeftCnt === 0) break;
        if (s[i] === '(') {
            s = replace(s, i, '#');
            removeLeftCnt -= 1;
        }
    }

    return s.replace(/#/g, '');
};

var replace = function(str, index, replacement) {
    return str.substr(0, index) + replacement + str.substr(index + replacement.length);
}

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.

  • X can be placed before L (50) and C (100) to make 40 and 90.

  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

1
2
Input: s = "III"
Output: 3

Example 2:

1
2
Input: s = "IV"
Output: 4

Example 3:

1
2
Input: s = "IX"
Output: 9

Example 4:

1
2
3
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

1
2
3
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15

  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Hint 1:

Problem is simpler to solve by working the string from back to front and using a map.

Explanation

  1. Create a HashMap to map the roman character with its corresponding integer.

  2. We can also loop through the roman string. If the current character’s corresponding integer is less than or equal to its previous character’s corresponding integer, then we add the current integer. For example VI, we add 5, add 1. In other words, (5+1=6).

  3. Else if the current character’s corresponding integer is greater than its previous character’s corresponding integer, then we add the current integer and subtract the previous character’s corresponding integer multiple by 2. For example IV, we add 1, add 5, subtract 2x1. In other words, (1+5-2x1=4).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let res = 0;
    const hm = new Map([
        ['I', 1],
        ['V', 5],
        ['X', 10],
        ['L', 50],
        ['C', 100],
        ['D', 500],
        ['M', 1000]
    ]);

    for (let i = 0; i < s.length; i++) {
        if (i === 0 || hm.get(s[i]) <= hm.get(s[i-1])) {
            res += hm.get(s[i]);
        } else {
            res += hm.get(s[i]) - 2 * hm.get(s[i-1]);
        }
    }

    return res;
};

Broken Calculator

On a broken calculator that has a number showing on its display, we can perform two operations:

  • Double: Multiply the number on the display by 2, or;

  • Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

1
2
3
Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

1
2
3
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

1
2
3
Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

1
2
3
Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

  1. 1 <= X <= 10^9

  2. 1 <= Y <= 10^9

Explanation

  1. We can think of this problem by given Y and finding X by using /2 and +1. The reason is going from X to Y is not deterministic, because one can choose to x2, or -1 first and then x2. However, going from Y to X is deterministic, because we cannot do /2 when Y is an odd number. Therefore, whenever Y is an odd number, the only thing we can do is +1 and then /2. Therefore, going from Y to X is straightforward.

  2. Another explanaion is for X < Y, if we start from X, then we don’t have a clue how should we pick -1 or x2, but if we start from Y, and look at it odd-eveness, then we would have a clue.

    • If Y is odd, then the last operation must be -1, no other approaches.
    • Hence from Y to find X, we will +1 when Y is odd.
    • If Y is even, then we have two choices: -1 or x2.
    • To get last Y from last second Y2, we have two ways: Y2 * 2 or Y2 * 2 - 1 - 1 * Y2 * 2 -1 - 1 = (Y2-1) * 2, and (Y2-1) * 2 can save us one operation. * Hence from Y to find X, we will always pick /2 when Y is even.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} X
 * @param {number} Y
 * @return {number}
 */
var brokenCalc = function(X, Y) {
    let cnt = 0;

    while (Y > X) {
        if (Y % 2 == 0) Y /= 2;
        else Y += 1;
        cnt += 1;
    }

    return X - Y + cnt;
};

Week 4: February 22nd - February 28th

Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1), and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her, but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Example 1:

Find the Celebrity

1
2
3
Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2:

Find the Celebrity

1
2
3
Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

  • n == graph.length

  • n == graph[i].length

  • 2 <= n <= 100

  • graph[i][j] is 0 or 1.

  • graph[i][i] == 1

Follow up: If the maximum number of allowed calls to the API knows is 3 * n, could you find a solution without exceeding the maximum number of calls?

Hint 1:

The best hint for this problem can be provided by the following figure:

Find the Celebrity

Hint 2:

Well, if you understood the gist of the above idea, you can extend it to find a candidate that can possibly be a celebrity. Why do we say a “candidate”? That is for you to think. This is clearly a greedy approach to find the answer. However, there is some information that would still remain to be verified without which we can’t obtain an answer with certainty. To get that stake in the ground, we would need some more calls to the knows API.

Explanation 1

  1. If knows(i, j) == true || knows(j, i) == false then we know i is not a celebrity, else we know j is not a celebrity. We can use two for loops to try every pair of persion and find out the celebrity.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        Set<Integer> notCelebrity = new HashSet<>();

        for (int i = 0; i < n; i++) {
            if (notCelebrity.contains(i)) continue;

            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (knows(i, j) || !knows(j, i)) {
                    notCelebrity.add(i);
                    break;
                } else {
                    notCelebrity.add(j);
                }
            }

            if (!notCelebrity.contains(i)) return i;
        }

        return -1;
    }
}

Explanation 2

  1. Initialize the celebrity res = 0. Loop through every person i, if knows(res, i) == true, then we update res = i. Since we have maximum one celebrity, res maybe the celebrity. After this first loop, we know res doesn’t know every person i that is greater than res. Next we need to verify if res is the celebrity. We can check two groups of people. First group is person 0 to person res-1 inclusive. Second group is person res+1 to n-1 inclusive. For the first group of people, we need to check if knows(res, i) == true or knows(i, res) == false, then res is not celebrity. Second group is for i greater than res. Since we know knows(res, i) == false from the first for loop, we can now only check if knows(i, res) == false, then res is not celebrity. After checking both group, then res is the celebrity.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (knows(res, i)) res = i;
        }

        for (int i = 0; i <= res-1; i++) {
            if (knows(res, i) || !knows(i, res)) return -1;
        }

        for (int i = res+1; i < n; i++) {
            if (!knows(i, res)) return -1;
        }

        return res;
    }
}

Longest Word in Dictionary through Deleting

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

1
2
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2:

1
2
Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

Constraints:

  • 1 <= s.length <= 1000

  • 1 <= dictionary.length <= 1000

  • 1 <= dictionary[i].length <= 1000

  • s and dictionary[i] consist of lowercase English letters.

Explanation

  1. We can use the isSubsequence method from Longest Uncommon Subsequence II to check if the iterated string is the subsequence of string s. So we iterate the strings from the list, if the current iterated string is the subsequence and its length is longer than res, we update res be the iterated string.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    let res = "";
    let max = 0;

    for (const d of dictionary) {
        if (helper(s, d) && d.length >= max) {
            if (d.length > max || d.length === max && d < res) res = d;
            max = d.length;
        }
    }

    return res;
};

var helper = function(s, d) {
    let cnt = 0;

    for (const ch of s) {
        if (ch === d[cnt]) {
            cnt += 1;
            if (cnt === d.length) return true;
        }
    }

    return false;
}

Search a 2D Matrix II

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

  • Integers in each row are sorted in ascending from left to right.

  • Integers in each column are sorted in ascending from top to bottom.

Example 1:

Search a 2D Matrix II

1
2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Search a 2D Matrix II

1
2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints:

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= n, m <= 300

  • -10^9 <= matix[i][j] <= 10^9

  • All the integers in each row are sorted in ascending order.

  • All the integers in each column are sorted in ascending order.

  • -10^9 <= target <= 10^9

Explanation

  1. We notice that the bottom left number is special. All numbers above the bottom left number are less than it; all numbers on the right side of the bottom left number are greater than it. Similar to the top right number.

  2. We can choose either bottom left or top right number to compare with the target value. For example, if we choose bottom left number num[r][c], if the target is smaller, then we make the new bottom left number to be the num[r-1][c]; else if the target is greater, then we make the new bottom left number to be num[r][c+1]; else if the target is equal to the bottom left number, we return true. If row and column are out of bound, we return false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    const row = matrix.length, col = matrix[0].length;

    let r = row - 1, c = 0;
    while (r >= 0 && c < col) {
        if (matrix[r][c] < target) {
            c += 1;
        } else if (matrix[r][c] > target) {
            r -= 1;
        } else {
            return true;
        }
    }

    return false;
};

Score of Parentheses

Given a balanced parentheses string S, compute the score of the string based on the following rule:

  • () has score 1

  • AB has score A + B, where A and B are balanced parentheses strings.

  • (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

1
2
Input: "()"
Output: 1

Example 2:

1
2
Input: "(())"
Output: 2

Example 3:

1
2
Input: "()()"
Output: 2

Example 4:

1
2
Input: "(()(()))"
Output: 6

Note:

  1. S is a balanced parentheses string, containing only ( and ).

  2. 2 <= S.length <= 50

Explanation 1

  1. We can use a stack to hold the scores for each depth. Iterate the string, if the current character is (, then we push 0 into the stack because we start a new depth and this depth’s score is 0. If the current character is ), then the current depth’s score will be max(1, 2 * curDepthScore), also the current depth score need to plus its previous depth’s score. For example ( ( ) ( ) . ), when we are on index 4, the current depth will be 1 + 1 = 2. That’s also the reason we add 0 as the previous depth’s score into the stack before we iterate the string.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} S
 * @return {number}
 */
var scoreOfParentheses = function(S) {
    const st = [];
    st.push(0);

    for (const ch of S) {
        if (ch === "(") {
            st.push(0);
        } else {
            const curDepthScore = st.pop();
            const preDepthScore = st.pop();
            const newCurDepthScore = preDepthScore + Math.max(1, curDepthScore * 2);
            st.push(newCurDepthScore);
        }
    }

    return st.pop();
};

Explanation 2

  1. We keep track of the depth. If we meet (, we increase the depth by 1. If we meet ), we decrease the depth by 1. If we meet ( ), then we know the outside depth, so we increase the result by 2 to the powe of outsideDepth. For example, ( ( ) . ). When we are on index 2, the outside depth is 1, so we increase the result by 2^1. Another example is ( ( ) ( ) ), when we are on index 2, outside depth is 1, so we increase result by 2 ^ 1, when we are on index 4, outside depth is 1, so we increase result by 2 ^ 1, so total result is 4.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} S
 * @return {number}
 */
var scoreOfParentheses = function(S) {
    let res = 0;
    let depth = 0;

    for (let i = 0; i < S.length; i++) {
        if (S[i] === "(") depth += 1;
        else depth -= 1;

        if (S[i] === ")" && S[i-1] === "(") {
            res += Math.pow(2, depth);
        }
    }

    return res;
};

Shortest Unsorted Continuous Subarray

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:

1
2
3
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:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 10^4

  • -10^5 <= nums[i] <= 10^5

Follow up: Can you solve it in O(n) time complexity?

Explanation

  1. We want to find the subarray’s left and right end index.

  2. We can create max equals to the first number of the input array, and we create min equals to the last number of the input array. Start looping i from the second number, update max equals to the maximum of max and nums[i]. After update, if max is greater than nums[i], then right = i. Similarlly, update min to be the minimum of min and nums[nums.length-1-i]. If min is less than nums[nums.length-1-i], then we have left = nums.length-1-i. Notice that right is moving to the right, left is moving to theleft. At the end, we get the subarray’s beginning idex left and ending index right. Then we can get its length.

  3. For example, think of the input array is [4, 3, 2, 1]. Initially, max = 4, min = 1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let left = -1, right = -2;
    let max = nums[0], min = nums[nums.length - 1];

    for (let i = 1; i < nums.length; i++) {
        max = Math.max(max, nums[i]);
        if (nums[i] < max) right = i;

        min = Math.min(min, nums[nums.length - 1 - i]);
        if (nums[nums.length - 1 - i] > min) left = nums.length - 1 - i;
    }

    return right - left + 1;
};

Validate Stack Sequences

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

1
2
3
4
5
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

1
2
3
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

  • 0 <= pushed.length == popped.length <= 1000

  • 0 <= pushed[i], popped[i] < 1000

  • pushed is a permutation of popped.

  • pushed and popped have distinct values.

Explanation

  1. We can use brute force to solve this problem. Loop through the pushed array. Inside the pushed array, we push pushed[i] into a stack. While the top of the stack is equal to popped[popIdx], then we pop the stack and increase popIdx. At the end, if popIdx is equal to the length of popped[], we return true, else return false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    const st = [];
    let popIdx = 0;

    for (const cur of pushed) {
        st.push(cur);
        while (st.length > 0 && st[st.length-1] === popped[popIdx]) {
            st.pop();
            popIdx += 1;
        }
    }

    return popIdx == popped.length;
};

Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, assume that your function returns 2^31 − 1 when the division result overflows.

Example 1:

1
2
3
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

1
2
3
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Example 3:

1
2
Input: dividend = 0, divisor = 1
Output: 0

Example 4:

1
2
Input: dividend = 1, divisor = 1
Output: 1

Constraints:

  • -2^31 <= dividend, divisor <= 2^31 - 1

  • divisor != 0

Explanation

  1. We can use bit operation to solve this problem.

  2. Initialize res = 0. While divident is greater or equal than the divisor, we left shift the divisor. Each time we left shift the divisor, we multiple by 2 and add to the res. For example, if the divident is 32 and divisor is 3. Left shift one time, divisor becomes 6; left shift two time, it becomes 12; left shift three times, it becomes 24; left shift four times, it becomes 48. Now the divisor is greater than the divident, so we need left shift 3 times to keep the divisor less than divident, and the res = 2^3=8. If we left shift 3 times, the divisor is 24, we use divident subtract it, we get the new divident = 32-24 = 8. Repeat the same step with divident=8 and divisor=3. Now, we can only left shift 1 times since 3*2=6<8, and res will be 2^1=2, so we get res = 8+2 = 10.

  3. JavaScript bitwise is for signed 32-bit, so instead of while ((base << 1) <= dividend), we do while (base <= (dividend >> 1)).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    const MIN = -1 * 2 ** 31;
    const MAX = 2 ** 31 - 1;
    if (dividend === MIN && divisor === -1) return MAX;

    let dividendA = Math.abs(dividend);
    let divisorA = Math.abs(divisor);
    let res = 0;

    while (divisorA <= dividendA) {
        let base = divisorA;
        let curRes = 1;
        while (base <= dividendA >> 1) {
            curRes <<= 1;
            base <<= 1;
        }

        res += curRes;
        dividendA -= base;
    }

    if (dividend > 0 !== divisor > 0) return -res;
    return res;
};

Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

  • FreqStack() constructs an empty frequency stack.

  • void push(int val) pushes an integer val onto the top of the stack.

  • int pop() removes and returns the most frequent element in the stack.

    • If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Constraints:

  • 0 <= val <= 10^9

  • At most 2 * 10^4 calls will be made to push and pop.

  • It is guaranteed that there will be at least one element in the stack before calling pop.

Explanation

  1. First, we need to maintain a frequency map, the key is the number, the value is its frequency. Since we are popping the max frequency number, so we need to maintain a maxFrequency value. To keep track of all numbers that have the same frequency, we can create a hashmap freqSt, the key is the frequency, the value is a stack of numbers that has that frequency, so that the latest number is always on the top of that stack.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var FreqStack = function() {
    this.freqHm = new Map();
    this.freqSt = new Map();
    this.maxFreq = 0;
};

/**
 * @param {number} val
 * @return {void}
 */
FreqStack.prototype.push = function(val) {
    this.freqHm.set(val, this.freqHm.get(val) + 1 || 1);
    const curFreq = this.freqHm.get(val);
    this.maxFreq = Math.max(this.maxFreq, curFreq);

    if (!this.freqSt.get(curFreq)) this.freqSt.set(curFreq, []);
    this.freqSt.get(curFreq).push(val);
};

/**
 * @return {number}
 */
FreqStack.prototype.pop = function() {
    if (this.freqSt.get(this.maxFreq).length === 0) this.maxFreq -= 1;
    const popVal = this.freqSt.get(this.maxFreq).pop();
    this.freqHm.set(popVal, this.freqHm.get(popVal) - 1);
    return popVal;
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * var obj = new FreqStack()
 * obj.push(val)
 * var param_2 = obj.pop()
 */