March LeetCoding Challenge 2021

Posted on | In

In February, it’s Chinese New Year. Even though people have to stay at home, in the evening, I can still hear firework outside. This year, the company gave out a jacket, a fitbit, and a useless laptop camera. Also, every week there’s free meal in Chinatown.

Week 1: March 1st - March 7th

Single-Row Keyboard

There is a special keyboard with all keys in a single row.

Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25), initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i - j|.

You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.

Example 1:

1
2
3
4
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

Example 2:

1
2
Input: keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode"
Output: 73

Constraints:

  • keyboard.length == 26

  • keyboard contains each English lowercase letter exactly once in some order.

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

  • word[i] is an English lowercase letter.

Hint 1:

Can be the problem divided in parts, so solving each part and sum their solutions it should return the answer? Yes, you only need to divide the problem in finger jumps.

Hint 2:

In each finger jump you need to move your finger from one character to another, you need to know its index.

Hint 3:

Map each character to it’s index.

Hint 4:

Use a hash table to do that.

Explanation

  1. We can use brute force to solve this problem. First create a hash map, key is the keyboard character, value is the keyboard character’s index.

  2. After we have the map, then loop through each character of the word. Initially the finger is on index 0, in other word, curIdx = 0. We can get each character’s distance by abs(hm[ch] - curIdx), then we update curIdx to hm[ch].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int calculateTime(String keyboard, String word) {
        Map<Character, Integer> hm = new HashMap<>();
        for (int i = 0; i < keyboard.length(); i++) {
            hm.put(keyboard.charAt(i), i);
        }

        int res = 0;
        int curIdx = 0;
        for (char ch: word.toCharArray()) {
            int chIdx = hm.get(ch);
            res += Math.abs(chIdx - curIdx);
            curIdx = chIdx;
        }

        return res;
    }
}

Distribute Candies

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor’s advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:

1
2
3
Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

1
2
3
Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

1
2
3
Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

  • n == candyType.length

  • 2 <= n <= 10^4

  • n is even.

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

Hint 1:

To maximize the number of kinds of candies, we should try to distribute candies such that sister will gain all kinds.

Hint 2:

What is the upper limit of the number of kinds of candies sister will gain? Remember candies are to distributed equally.

Hint 3:

Which data structure is the most suitable for finding the number of kinds of candies?

Hint 4:

Will hashset solves the problem? Inserting all candies kind in the hashset and then checking its size with upper limit.

Explanation

  1. First, we need to calculate the total kinds of candies by using a hash set. Then, since brother and sister will have same number of candies, in other words, sister can have the maximum kind of candies which is candies.length / 2 assuming every candies are different kinds. Also, if the number of kinds set.size() is less than candies.length / 2, then sister can only have set.size() kinds.

Solution

1
2
3
4
5
6
7
8
/**
 * @param {number[]} candyType
 * @return {number}
 */
var distributeCandies = function(candyType) {
    const kind = new Set(candyType);
    return Math.min(kind.size, candyType.length / 2);
};

Set Mismatch

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

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

  • 1 <= nums[i] <= 10^4

Explanation 1

  1. We can sort the input array and loop from 1 to n to find out the duplicated number and missing number, or we can also solve this problem by using a set to record the visited number, or a map to record the frequency.

  2. To solve this problem in O(1) space, we can modify the input array. When we see a number num, we can modify its corresponding index num-1’s number to negative. Before we change it to negative, we check if it’s already negative then that means the current num is duplicated. Else, we set its corresponding index’s number to negative. After that, we loop the input array again, if num is positive, that means we have a missing number which is equal to the current index + 1.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    const res = [-1, -1];

    for (const num of nums) {
        if (nums[Math.abs(num)-1] < 0) res[0] = Math.abs(num);
        else nums[Math.abs(num)-1] *= -1;
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            res[1] = i + 1;
            break;
        }
    }

    return res;
};

Explanation 2

  1. We can also solve this problem using cyclic sort to sort the input array. Then loop the array, if num is not equal to its corresponding index idx + 1, that means num is duplicated, missing number is idx + 1.

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

    for (let i = 0; i < nums.length; i++) {
        while (nums[i] != nums[nums[i] - 1]) {
            const idx1 = i, idx2 = nums[i] - 1;
            [nums[idx1], nums[idx2]] = [nums[idx2], nums[idx1]];
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            res[0] = nums[i];
            res[1] = i + 1;
            break;
        }
    }

    return res;
};

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:

1
2
3
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

1
2
3
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

1
2
3
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

1
2
3
Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length

  • 1 <= n <= 10^4

  • 0 <= nums[i] <= n

  • All the numbers of nums are unique.

Explanation 1

  1. Calculate the input array’s sum, then minums the actual array’s sum, this will gives the missing number.

Solution 1

1
2
3
4
5
6
7
8
9
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const max = nums.length;
    const sum = nums.reduce((prev, cur) => prev + cur, 0);
    return (max + 1) * max / 2 - sum;
};

Explanation 2

  1. We can use XOR to solve this problem.

  2. We XOR all the numbers in the input array with the actual array’s numbers. The result will be the missing number.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        res ^= (i+1) ^ nums[i];
    }
    return res;
};

Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

Intersection of Two Linked Lists

It is guaranteed that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Example 1:

Intersection of Two Linked Lists

1
2
3
4
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Intersection of Two Linked Lists

1
2
3
4
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Intersection of Two Linked Lists

1
2
3
4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints:

  • The number of nodes of listA is in the m.

  • The number of nodes of listB is in the n.

  • 0 <= m, n <= 3 * 10^4

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

  • 0 <= skipA <= m

  • 0 <= skipB <= n

  • intersectVal is 0 if listA and listB do not intersect.

  • intersectVal == listA[skipA + 1] == listB[skipB + 1] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?

Explanation 1

  1. We can start compaing using two pointers when both list have the same length, so we move forward diff steps on the long linked list’s pointer. Then iterate both pointer and compare each node.

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    const lenA = getLen(headA);
    const lenB = getLen(headB);

    let ptrA = headA, ptrB = headB;

    if (lenA < lenB) {
        let diff = lenB - lenA;
        while (diff) {
            ptrB = ptrB.next;
            diff -= 1;
        }
    } else {
        let diff = lenA - lenB;
        while (diff) {
            ptrA = ptrA.next;
            diff -= 1;
        }
    }

    while (ptrA != ptrB) {
        ptrA = ptrA.next;
        ptrB = ptrB.next;
    }

    return ptrA;
};

var getLen = function(head) {
    let res = 0;
    let ptr = head;
    while (ptr) {
        ptr = ptr.next;
        res += 1;
    }
    return res;
}

Explanation 2

  1. When we finish iterating one list, we move that pointer start from the beginning of another list. When two pointers meet, that node is the intesection. Because both pointers run the same length, in other word, the sum of lenA and lenB doesn’t change.

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 singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) return null;
    const lenA = getLen(headA);
    const lenB = getLen(headB);
    const totalLen = lenA + lenB;

    let ptrA = headA, ptrB = headB;
    let cnt = 0;

    while (ptrA != ptrB) {
        ptrA = ptrA.next ? ptrA.next : headB;
        ptrB = ptrB.next ? ptrB.next : headA;
        cnt += 1;
        if (cnt > totalLen) return null;
    }

    return ptrA;
};

var getLen = function(head) {
    let res = 0;
    let ptr = head;
    while (ptr) {
        ptr = ptr.next;
        res += 1;
    }
    return res;
}

Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Average of Levels in Binary Tree

1
2
3
4
Input: root = [3,9,20,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Average of Levels in Binary Tree

1
2
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Constraints:

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

  • -2^31 <= Node.val <= 2^31 - 1

Explanation

  1. We can solve this problem using level-order traversal, in other words, BFS. For each level, we use a variable sum to sum all the numbers on the same level. After we finish iterating all numbers on the same level, we then calculate the average by sum divide the numbers of that level.

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 {number[]}
 */
var averageOfLevels = function(root) {
    const res = [];
    const queue = [root];

    while (queue.length > 0) {
        let sum = 0;
        const n = queue.length;
        for (let i = n - 1; i >= 0; i--) {
            const curNode = queue.shift();
            sum += curNode.val;
            if (curNode.left) queue.push(curNode.left);
            if (curNode.right) queue.push(curNode.right);
        }
        res.push(sum / n);
    }

    return res;
};

Short Encoding of Words

A valid encoding of an array of words is any reference string s and array of indices indices such that:

  • words.length == indices.length

  • The reference string s ends with the '#' character.

  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

  • Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Example 1:

1
2
3
4
5
6
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

Example 2:

1
2
3
Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].

Constraints:

  • 1 <= words.length <= 2000

  • 1 <= words[i].length <= 7

  • words[i] consists of only lowercase letters.

Explanation 1

  1. If there are two string A and B, and B is the suffix of A, then we don’t need to count B. For example, if A = "time" and B = "me", then we can skip counting B. So the goal is to remove words from the list such that no word is a suffix of another. The result would be sum(word.length + 1 for word in words).

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
/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    const ignoreWordIdx = new Set();

    for (let i = 0; i < words.length; i++) {
        if (ignoreWordIdx.has(i)) continue;

        for (let j = 0; j < words.length; j++) {
            if (i === j) continue;
            const lastIdx = words[i].lastIndexOf(words[j]);
            if (lastIdx >= 0 && lastIdx + words[j].length === words[i].length) {
                ignoreWordIdx.add(j);
            }
        }
    }

    return words.reduce((prev, cur, idx) => {
        if (ignoreWordIdx.has(idx)) {
            return prev;
        } else {
            return prev + cur.length + 1;
        }
    }, 0);
};

Explanation 2

  1. To find whether different words have the same suffix, let’s put them backwards into a trie (prefix tree). For example, if we have "time" and "me", we will put "emit" and "em" into our trie.

  2. After, the leaves of this trie (nodes with no children) represent words that have no suffix, and we will count sum(word.length + 1 for word in words).

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
/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    let res = 0;
    const trie = new Trie();
    const hm = new Map();

    for (let i = 0; i < words.length; i++) {
        const curWord = words[i];
        let cur = trie;
        for (let j = curWord.length - 1; j >= 0; j--) {
            cur = cur.addAndGet(curWord[j]);
        }
        hm.set(cur, i);
    }

    for (const [k, v] of hm) {
        if (k.numChildren === 0) {
            res += words[v].length + 1;
        }
    }

    return res;
};

var Trie = function() {
    this.children = Array(26).fill(null);
    this.numChildren = 0;
}

Trie.prototype.addAndGet = function(ch) {
    const idx = ch.charCodeAt(0) - 'a'.charCodeAt(0);
    if (!this.children[idx]) {
        this.children[idx] = new Trie();
        this.numChildren += 1;
    }
    return this.children[idx];
}

Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

  • MyHashMap() initializes the object with an empty map.

  • void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.

  • int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

  • void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

  • 0 <= key, value <= 10^6

  • At most 10^4 calls will be made to put, get, and remove.

Follow up: Please do not use the built-in HashMap library.

Explanation 1

  1. Since the range for keys is [0, 1000000], we can create an array of size 1000001 and initialize all elements to -1. In put method, we can just update the arr[key] = value]. In get method, we can just return arr[key]. In remove method, we can just update arr[key] = -1.

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
/**
 * Initialize your data structure here.
 */
var MyHashMap = function() {
    this.arr = new Array(1000001).fill(0);
};

/**
 * value will always be non-negative.
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function(key, value) {
    this.arr[key] = value + 1;
};

/**
 * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function(key) {
    return this.arr[key] - 1;
};

/**
 * Removes the mapping of the specified value key if this map contains a mapping for the key
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function(key) {
    this.arr[key] = 0;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * var obj = new MyHashMap()
 * obj.put(key,value)
 * var param_2 = obj.get(key)
 * obj.remove(key)
 */

Explanation 2

  1. We can save space by creating an array of linked node, and the array has size 10000 or 13000 for making the key distribute evenly. If two different keys lie on the same array index, then there’s a collision. Then we need to loop through the linked node and return the previous node of the node that has the same key, so that we can delete the node by prev.next = prev.next.next. In put method, if no node on lst[idx], then we need to make a dummy node lst[idx] = new Node(-1, -1) so that prev is not pointing to null.

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
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
/**
 * Initialize your data structure here.
 */
var MyHashMap = function() {
    this.size = 10000;
    this.arr = new Array(this.size).fill(null);

    this.getHashCode = function(k) {
        return k % this.size;
    }

    this.getPrevNode = function(idx, key) {
        if (!this.arr[idx]) this.arr[idx] = new Node(-1, -1);

        let cur = this.arr[idx], prev = null;
        while (cur !== null && cur.k !== key) {
            prev = cur;
            cur = cur.next;
        }
        return prev;
    }
};

/**
 * value will always be non-negative.
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function(key, value) {
    const idx = this.getHashCode(key);
    const prevNode = this.getPrevNode(idx, key);

    if (!prevNode.next) {
        prevNode.next = new Node(key, value);
    } else {
        prevNode.next.k = key;
        prevNode.next.v = value;
    }
};

/**
 * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function(key) {
    const idx = this.getHashCode(key);
    const prevNode = this.getPrevNode(idx, key);

    if (!prevNode.next) {
        return -1;
    } else {
        return prevNode.next.v;
    }
};

/**
 * Removes the mapping of the specified value key if this map contains a mapping for the key
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function(key) {
    const idx = this.getHashCode(key);
    const prevNode = this.getPrevNode(idx, key);

    if (!prevNode.next) {
        return;
    } else {
        prevNode.next = prevNode.next.next;
    }
};

var Node = function(k, v) {
    this.k = (k !== undefined ? k : null);
    this.v = (v !== undefined ? v : null);
    this.next = null;
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * var obj = new MyHashMap()
 * obj.put(key,value)
 * var param_2 = obj.get(key)
 * obj.remove(key)
 */

Week 2: March 8th - March 14th

Strobogrammatic Number

Given a string num which represents an integer, return true if num is a strobogrammatic number.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

1
2
Input: num = "69"
Output: true

Example 2:

1
2
Input: num = "88"
Output: true

Example 3:

1
2
Input: num = "962"
Output: false

Example 4:

1
2
Input: num = "1"
Output: true

Constraints:

  • 1 <= num.length <= 50

  • num consists of only digits.

  • num does not contain any leading zeros except for zero itself.

Explanation

  1. Only the following digit can be strobogrammatic, if there’s other digit, then we return false immediately.
1
2
3
4
5
  0 -> 0
  1 -> 1
  6 -> 9
  8 -> 8
  9 -> 6

  1. If the string length is odd, then the middle character must not be 6 or 9.

  2. We can use two pointers to check if the numbers are matched with its rotated one.

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
class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num.indexOf('2') >= 0 ||
            num.indexOf('3') >= 0 ||
            num.indexOf('4') >= 0 ||
            num.indexOf('5') >= 0 ||
            num.indexOf('7') >= 0) {
            return false;
        }

        int n = num.length();
        if (n % 2 == 1) {
            char midChar = num.charAt(n / 2);
            if (midChar == '6' || midChar == '9') {
                return false;
            }
        }

        int left = 0, right = n - 1;
        while (left < right) {
            if (num.charAt(left) == '6') {
                if (num.charAt(right) != '9') return false;
            } else if (num.charAt(left) == '9') {
                if (num.charAt(right) != '6') return false;
            } else if (num.charAt(left) != num.charAt(right)) {
                return false;
            }
            left += 1;
            right -= 1;
        }

        return true;
    }
}

Remove Palindromic Subsequences

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

1
2
3
Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

1
2
3
4
Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".

Example 3:

1
2
3
4
Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".

Constraints:

  • 1 <= s.length <= 1000

  • s[i] is either 'a' or 'b'.

Hint 1:

Use the fact that string contains only 2 characters.

Hint 2:

Are subsequences composed of only one type of letter always palindrome strings ?

Explanation

  1. If the string is empty, we return 0.

  2. If the string is palindrome, we return 1.

  3. Since there are a and b in the string, we can remove sequence of all as which cost 1 operation, then remove sequence of all bs which cost 1 operation, so total 2 operations.

Solution

1
2
3
4
5
6
7
8
9
/**
 * @param {string} s
 * @return {number}
 */
var removePalindromeSub = function(s) {
    if (s === "") return 0;
    if ([...s].reverse().join("") === s) return 1;
    return 2;
};

Add One Row to Tree

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

  • Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur’s left subtree root and right subtree root.

  • cur’s original left subtree should be the left subtree of the new left subtree root.

  • cur’s original right subtree should be the right subtree of the new right subtree root.

  • If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Add One Row to Tree

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

Example 2:

Add One Row to Tree

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

Constraints:

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

  • The depth of the tree is in the range [1, 10^4].

  • -100 <= Node.val <= 100

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

  • 1 <= depth <= the depth of tree + 1

Explanation 1

  1. If d is equal to 1, then we can just make a new TreeNode and connect its left child to the root and we return the new TreeNode.

  2. Else if d is not equal to 1, we can use level-order traversal to solve this problem. First, store the root TreeNode into the queue. Then while the queue is not empty, we decrease d by 1. Poll the nodes from the queue, if d is equal to 1, then we need to save the poll node’s left and right child as left and right. Then insert the row of TreeNode with value v by p.left = new TreeNode(v) and p.right = new TreeNode(v), then connect back to the left and right by p.left.left = left and p.right.right = right. Else if d is not equal to 1, then we just add the poll node’s left child and right child into the queue. At the end, we return root.

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
/**
 * 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} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function(root, v, d) {
    if (d === 1) {
        const newRoot = new TreeNode(v);
        newRoot.left = root;
        return newRoot;
    }

    const queue = [];
    queue.push(root);
    while (queue.length > 0) {
        d -= 1;
        for (let i = queue.length - 1; i >= 0; i--) {
            const cur = queue.shift();
            if (d === 1) {
                const leftSubTree = cur.left;
                const newLeftSubTree = new TreeNode(v);
                newLeftSubTree.left = leftSubTree;
                cur.left = newLeftSubTree;

                const rightSubTree = cur.right;
                const newRightSubTree = new TreeNode(v);
                newRightSubTree.right = rightSubTree;
                cur.right = newRightSubTree;
            } else {
                if (cur.left) queue.push(cur.left);
                if (cur.right) queue.push(cur.right);
            }
        }

        if (d === 1) return root;
    }

    return root;
};

Explanation 2

  1. We can also use DFS to solve this problem. We will only add new nodes under the current root node at depth d-1.

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
42
43
44
/**
 * 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} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function(root, v, d) {
    if (d === 1) {
        const newRoot = new TreeNode(v);
        newRoot.left = root;
        return newRoot;
    }

    helper(root, v, 1, d-1);

    return root;
};

var helper = function(root, v, curDepth, targetDepth) {
    if (!root) return;

    if (curDepth === targetDepth) {
        const leftSubTree = root.left;
        const newLeftSubTree = new TreeNode(v);
        newLeftSubTree.left = leftSubTree;
        root.left = newLeftSubTree;

        const rightSubTree = root.right;
        const newRightSubTree = new TreeNode(v);
        newRightSubTree.right = rightSubTree;
        root.right = newRightSubTree;
    } else {
        helper(root.left, v, curDepth + 1, targetDepth);
        helper(root.right, v, curDepth + 1, targetDepth);
    }
}

Integer to Roman

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 an integer, convert it to a roman numeral.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

  • 1 <= num <= 3999

Explanation

Character I V X L C D M
Number 1 5 10 50 100 500 1000

  1. For example, 1437 in roman is MCDXXXVII. We find out the thousand digit, hundred digit, thenth digit, and single digit’s numbers all can be represented by roman character. 1000 is M, 400 is CD, 30 is XXX, 7 is VII. So, we can get every digit by division 1000, 100, 10, 1, and represent them.

  2. We can have 4 groups. 1-3 is one group, 4 is one group, 5-8 is one group, 9 is one group. For example:

  • 100 - C

  • 200 - CC

  • 300 - CCC

  • 400 - CD

  • 500 - D

  • 600 - DC

  • 700 - DCC

  • 800 - DCCC

  • 900 - CM

  1. We will first create a roman character array roman{'M', 'D', 'C', 'L', 'X', 'V', 'I'} and value array value{1000, 500, 100, 50, 10, 5, 1}. We will iterate two steps each time, in other words, 1000, then 100, then 10, then 1, so we can divide it to get the digit.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    let res = ""
    const val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const str = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

    for (let i = 0; i < val.length; i++) {
        while (num >= val[i]) {
            res += str[i];
            num -= val[i];
        }
    }

    return res
};

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

1
2
3
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

1
2
Input: coins = [2], amount = 3
Output: -1

Example 3:

1
2
Input: coins = [1], amount = 0
Output: 0

Example 4:

1
2
Input: coins = [1], amount = 1
Output: 1

Example 5:

1
2
Input: coins = [1], amount = 2
Output: 2

Constraints:

  • 1 <= coins.length <= 12

  • 1 <= coins[i] <= 2^31 - 1

  • 0 <= amount <= 10^4

Explanation 1

  1. For problems that asking for minimum or maximum number, we can use dynamic programming to solve.

  2. Dynamic statis a one dimensional array, dp[i] which represents for amount i, the minimum number of coins we should choose. We will create dp[amount+1] since we should consider amount=0.

  3. Dynamic init is dp[0] = 0. If amount=0, then the result should be 0 since we do not need any number of coins to get the amount 0. Other dp[i] will all be amount+1 since the maximum number of coins can choose is dp[i]=amount. We plus one, so that dp[i] cannot reach amount+1. At the end, if dp[i] still equal to amount+1, then it means we cannot form target=amount, so we return -1.

  4. Dynamic function is dp[i] = min(dp[i], dp[ i - coins[j] ] + 1, and j means loop from all coins index. For example 1, we need to find dp[11], if we choose coins coins[j]=5, then if we know dp[6], then we get the result for dp[11] = dp[6] + 1.

  5. Dynamic result is if dp[amount] still equals to amount+1, we return -1. Else, we return dp[amount].

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const dp = Array(amount + 1).fill(amount + 1);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
            }
        }
    }

    return dp[amount] === amount + 1 ? -1 : dp[amount];
};

Explanation 2

  1. We can use memoization to improve the time complexity of the above dynamic programming.

  2. We use memo[i] to represent for amount i, the minimum number of coins we choose. The base case if target is less than 0, we return -1. If memo[target] is not equal to the initial Integer.MAX_VALUE, then it means we already have the value of memo[target], so we can just return it.

  3. We need to loop through all coins, if we choose coins[j], then we recursivly find the result temp of target target-coins[j]. If that result temp >= 0, then we update the result memo[target] = min(memo[target], temp+1) similar to the above solution.

  4. Outside the loop, if memo[target] still equals to MAX_VALUE, then it means it cannot form the target since all temp < 0, so memo[target] = -1. Else we return memo[target].

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
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const memo = Array(amount + 1).fill(Number.MAX_SAFE_INTEGER);
    memo[0] = 0;
    return helper(coins, amount, memo);
};

var helper = function(coins, target, memo) {
    if (target < 0) return -1;
    if (memo[target] !== Number.MAX_SAFE_INTEGER) {
        return memo[target];
    }

    for (let i = 0; i < coins.length; i++) {
        if (coins[i] <= target) {
            const temp = helper(coins, target - coins[i], memo);
            if (temp >= 0) {
                memo[target] = Math.min(memo[target], temp + 1);
            }
        }
    }

    if (memo[target] === Number.MAX_SAFE_INTEGER) {
        memo[target] = -1;
    }

    return memo[target];
}

Check If a String Contains All Binary Codes of Size K

Given a binary string s and an integer k.

Return True if every binary code of length k is a substring of s. Otherwise, return False.

Example 1:

1
2
3
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

1
2
Input: s = "00110", k = 2
Output: true

Example 3:

1
2
3
Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.

Example 4:

1
2
3
Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

1
2
Input: s = "0000000001011100", k = 4
Output: false

Constraints:

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

  • s consists of 0’s and 1’s only.

  • 1 <= k <= 20

Hint 1:

We need only to check all sub-strings of length k.

Hint 2:

The number of distinct sub-strings should be exactly 2^k.

Explanation

  1. We can use sliding window to find all distinct substring of size k and put them into a set. If the set has 1 << k distinct substring, then we return true.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    const set = new Set();

    for (let i = 0; i <= s.length - k; i++) {
        set.add(s.substring(i, i+k));
        if (set.size == 1 << k) return true;
    }

    return false;
};

Binary Trees With Factors

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10^9 + 7.

Example 1:

1
2
3
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

1
2
3
Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Constraints:

  • 1 <= arr.length <= 1000

  • 2 <= arr[i] <= 10^9

Explanation

  1. We can solve this problem using dynamic programming. Dynamic state is dp[i] which represents the number of binary trees we can make for root value i.

  2. Dynamic init is every value in arr, we can make at least 1 binary tree, which has only one node.

  3. Dynamic function is dp[i] += dp[j] * dp[i / j] for every value j less than value i from arr. In order to find dp[i], first we need to find dp[j] so we need to sort arr in the beginning.

  4. Dynamic result is the sum of all dp[i].

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
/**
 * @param {number[]} arr
 * @return {number}
 */
var numFactoredBinaryTrees = function(arr) {
    let res = 0;
    const MOD = 1e9 + 7;
    arr.sort((a, b) => a - b);
    const dp = new Map();
    arr.forEach(num => dp.set(num, 1));

    for (let i = 0; i < arr.length; i++) {
        let curRootCnt = dp.get(arr[i]);

        for (let j = 0; j < i; j++) {
            if (arr[i] % arr[j] != 0) continue;
            if (!dp.has(arr[i] / arr[j])) continue;
            const leftRootCnt = dp.get(arr[j]);
            const rightRootCnt = dp.get(arr[i] / arr[j]);
            curRootCnt += (leftRootCnt * rightRootCnt) % MOD;
        }

        dp.set(arr[i], curRootCnt);
        res = (res + curRootCnt) % MOD;
    }

    return res;
};

Swapping Nodes in a Linked List

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Swapping Nodes in a Linked List

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

Example 2:

1
2
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

  • The number of nodes in the list is n.

  • 1 <= k <= n <= 10^5

  • 0 <= Node.val <= 100

Hint 1:

We can transform the linked list to an array this should ease things up

Hint 2:

After transforming the linked list to an array it becomes as easy as swapping two integers in an array then rebuilding the linked list

Explanation

  1. We can use brute force to solve this problem. First finding the ith node from the left and the ith node from the right, then swap their values and return head.

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var swapNodes = function(head, k) {
    let left = head, right = head, temp = head;

    for (let i = 0; i < k - 1; i++) {
        left = left.next;
        temp = temp.next;
    }

    while (temp.next) {
        right = right.next;
        temp = temp.next;
    }

    [left.val, right.val] = [right.val, left.val];

    return head;
};

Week 3: March 15th - March 21st

Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example 1:

Construct Binary Tree from String

1
2
Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

1
2
Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

1
2
Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

Constraints:

  • 0 <= s.length <= 3 * 10^4

  • s consists of digits, '(', ')', and '-' only.

Explanation 1

  1. We can use recursive method to solve this problem. First character of the input string is not parenthesis, so we can create the root node first. When we iterate to a left parenthesis, we find its mathing right parenthesis, then recusivly call the main function with the substring in between these two matching parenthesis. This recusive function will return a TreeNode curNode, if root doesn’t have left child, then add curNode to root.left, else add to root.right.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode str2tree(String s) {
        if (s.length() == 0) return null;

        int i = s.indexOf("(");
        if (i < 0) return new TreeNode(Integer.valueOf(s));
        TreeNode root = new TreeNode(Integer.valueOf(s.substring(0, i)));

        char[] arr = s.toCharArray();
        Stack<Integer> st = new Stack<>();

        while (i < arr.length) {
            if (arr[i] == '(') {
                st.push(i);
            } else if (arr[i] == ')') {
                int leftIdx = st.pop();
                if (st.isEmpty()) {
                    if (root.left == null) {
                        root.left = str2tree(s.substring(leftIdx + 1, i));
                    } else {
                        root.right = str2tree(s.substring(leftIdx + 1, i));
                    }
                }
            }
            i += 1;
        }

        return root;
    }
}

Explanation 2

  1. Iterate the input string, when we see character that is not parenthesis, then we record these characters to a string builder sb.

  2. When we see (, then make a TreeNode curNode from sb and push to stack.

  3. When we see ), then make a TreeNode curNode from sb, and curNode’s parent node is st.peek(). If parent node doesn’t have left child, add curNode to its left child, else add curNode to its right child. One corner case is two right parenthesis next to each other. For example the last two )s in 4(2(3)(1)), then sb is empty, so curNode is st.pop().

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
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode str2tree(String s) {
        if (s.length() == 0) return null;

        char[] arr = s.toCharArray();
        Stack<TreeNode> st = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                if (sb.length() > 0) {
                    st.push(new TreeNode(Integer.valueOf(sb.toString())));
                    sb.setLength(0);
                }
            } else if (arr[i] == ')') {
                TreeNode curNode = null;
                if (sb.length() > 0) {
                    curNode = new TreeNode(Integer.valueOf(sb.toString()));
                    sb.setLength(0);
                } else {
                    curNode = st.pop();
                }
                TreeNode parent = st.peek();
                if (parent.left == null) {
                    parent.left = curNode;
                } else {
                    parent.right = curNode;
                }
            } else {
                sb.append(arr[i]);
            }
        }

        return st.isEmpty() ? new TreeNode(Integer.valueOf(s)) : st.peek();
    }
}

Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Explanation 1

  1. For the encode function, we can create a list to store the url that is going to be encoded, then we return the list’s index.

  2. For the decode function, we can split the url to get its index. Then return the url from the list based on the index.

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
var lst = [];

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
    lst.push(longUrl);
    return "http://tinyurl.com/" + (lst.length-1);
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
    const temp = shortUrl.lastIndexOf("/");
    const idx = +shortUrl.substring(temp+1);
    return lst[idx];
};

/**
 * Your functions will be called as such:
 * decode(encode(url));
 */

Explanation 2

  1. When we encode, we want to generate 6 random characters for the input url. We can use a HashMap longToShort represent the key is the long url, the value is the 6 random characters. So, when we encode a same url, we can use $O(1)$ runtime to get the random 6 characters.

  2. When we decode, we are providing the 6 random characters at the end of the short url, so we first need to get these 6 random characters. We want to use $O(1)$ runtime to get back the long url, so we need a shortToLong HashMap when we doing encoding, and its key is the 6 random characters, its value is the long url before encode. We will update both HashMap when we do encode.

  3. We can generate the 6 random characters by creating a empty string builder and a dictionary string contains all 10 digits, all 26 lower case letter, and all 26 upper case letters. Then loop 6 times, each time we generate a random integer index between 0 to 61 inclusive to get a random character. If the generated 6 random characters string is inside the HashMap shortToLong, then we need to regenerate.

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
42
let longToShort = new Map(), shortToLong = new Map();

var generateRandStr = function() {
    const dict = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const randStr = new Array(6).fill().map(_ => dict.charAt(~~(Math.random() * 62)));
    return randStr.join("")
}

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
    if (longToShort.has(longUrl)) return longToShort.get(longUrl);

    let randStr = generateRandStr();
    while (shortToLong.has(randStr)) randStr = generateRandStr();

    shortToLong.set(randStr, longUrl);
    longToShort.set(longUrl, randStr);

    return "http://tinyurl.com/" + randStr;
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
    const temp = shortUrl.lastIndexOf("/");
    const randStr = shortUrl.substring(temp + 1);
    if (shortToLong.has(randStr)) return shortToLong.get(randStr) || shortUrl;
};

/**
 * Your functions will be called as such:
 * decode(encode(url));
 */

Best Time to Buy and Sell Stock with Transaction Fee

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3
4
5
6
7
8
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

1
2
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Constraints:

  • 1 < prices.length <= 5 * 10^4

  • 0 < prices[i], fee < 5 * 10^4

Hint 1:

Consider the first K stock prices. At the end, the only legal states are that you don’t own a share of stock, or that you do. Calculate the most profit you could have under each of these two cases.

Explanation 1

  1. We can use dynamic programming to solve this problem. Dynamic state. In each day, we either sell or not sell, so we create two arrays sell[i] and notSell[i]. It means at day i, the maximum profit of sell and not sell respectivly.

  2. Dynamic init is at day 1, sell[0] = 0, notSell[0] = -prices[0].

  3. Dynamic function. If we sell on day i, then the maximum profit on sell[i] either equals to the previous day’s maximum profit sell[i-1] or sell on day i, in other words, prices[i] + notSell[i-1] - fee because if sell on day i, then on day i-1 we must not sell. So we get sell[i] = max(sell[i-1], prices[i] + notSell[i-1] - fee).

  4. If we don’t sell on day i, then the maximum profit on notSell[i] either equals to the previous day’s not sell profit notSell[i-1] or buy on day i, in other words, sell[i-1]-prices[i] because we can only buy after sell. So we get notSell[i] = max(notSell[i-1], sell[i-1] - prices[i]).

  5. Dynamic result is the maximum profit we sell on the last day.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
        const sell = Array(prices.length).fill(0);
        const notSell = Array(prices.length).fill(0);
        notSell[0] = -prices[0];

        for (let i = 1; i < prices.length; i++) {
            sell[i] = Math.max(sell[i-1], notSell[i-1] + prices[i] - fee);
            notSell[i] = Math.max(notSell[i-1], sell[i-1] - prices[i]);
        }

        return sell[prices.length-1];
};

Explanation 2

  1. We can save some space. We notice that current day i ‘s sell[i] and notSell[i] are only related to day i-1. So instead of using an array to hold all day, we can use two variable sell and notSell to represent sell[i] and notSell[i].

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
        let sell = 0
        let notSell = -prices[0];

        for (let i = 1; i < prices.length; i++) {
            const temp = sell;
            sell = Math.max(sell, notSell + prices[i] - fee);
            notSell = Math.max(notSell, temp - prices[i]);
        }

        return sell;
};

Generate Random Point in a Circle

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

  1. input and output values are in floating-point.

  2. radius and x-y position of the center of the circle is passed into the class constructor.

  3. a point on the circumference of the circle is considered to be in the circle.

  4. randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Example 1:

1
2
3
4
Input:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

Example 2:

1
2
3
4
Input:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution’s constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Explanation

  1. We can use rejection sampling similar to 470. Implement Rand10() Using Rand7(). We also know the equation for a circle is (x - a) ^ 2 + (y - b) ^ 2 = r ^ 2 where a and b is the center of the circle. So we need to find out x and y.

  2. We can first find out the minimum x minX by x_center - radius, and the minimum y minY by y_center - radius. Then, we generate a random number between 0 to radius * 2, then plus the minX or minY with that random number to get the x and y.

  3. After we get the point position, then we check if this point position is inside the circle by the above formula. If this position is outside of the circle, then we repeat to calculate the position’s x and y axises.

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 {number} radius
 * @param {number} x_center
 * @param {number} y_center
 */
var Solution = function(radius, x_center, y_center) {
    this.radius = radius;
    this.centerX = x_center;
    this.centerY = y_center;
    this.minX = x_center - radius;
    this.minY = y_center - radius;
};

/**
 * @return {number[]}
 */
Solution.prototype.randPoint = function() {
    while (true) {
        const x = this.minX + Math.random() * 2 * this.radius;
        const y = this.minY + Math.random() * 2 * this.radius;
        if (Math.pow(x - this.centerX, 2) + Math.pow(y - this.centerY, 2) <= this.radius * this.radius) {
            return [x, y];
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(radius, x_center, y_center)
 * var param_1 = obj.randPoint()
 */

Wiggle Subsequence

Given an integer array nums, return the length of the longest wiggle sequence.

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

  • For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.

  • In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

  • A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

1
2
3
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

1
2
3
Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

1
2
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Constraints:

  • 1 <= nums.length <= 1000

  • 0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

Explanation 1

  1. We can use dynamic programming to solve this problem. First, we create two one dimensional array p[] and n[]. For p[i], it means until index i inclusive, the maximum length of the wiggle subsequence that ends with positive difference. For n[i], it means until index i inclusive, the maximum length of the wiggle subsequence that ends with negative difference.

  2. We can loop from index i = 1 to the last index, and for every current index i, we loop from index j = 0 to i-1 inclusive, if nums[j] < nums[i], then it means the last difference until i inclusive is positive, so we update p[i] = 1 + n[j]. 1 means the current number nums[i], we add n[i] because n[i] means until index i inclusive, the last difference is negative. For example, [1, 17, 5, 10], if i is pointing to element 10, j is pointing to element 5, then we update p[i] because [5, 10] has positive difference. Now, similarlly, if nums[j] > nums[i], we want to update n[i] = 1 + p[j].

Solution 1

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 wiggleMaxLength = function(nums) {
    const p = Array(nums.length).fill(1);
    const n = Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                p[i] = Math.max(p[i], n[j] + 1);
            } else if (nums[i] < nums[j]) {
                n[i] = Math.max(n[i], p[j] + 1);
            }
        }
    }

    return Math.max(p[nums.length-1], n[nums.length-1]);
};

Explanation 2

  1. We can solve it in $O(n)$ runtime. Instead of having two arrays p[] and n[], we can make them as two variables p and n to record the last difference is positive and negative. We can loop one time, in every iteration, we update either p or n depends on nums[i] and nums[i-1].

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    let p = 1;
    let n = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            p = n + 1;
        } else if (nums[i] < nums[i-1]) {
            n = p + 1;
        }
    }

    return Math.max(p, n);
};

Keys and Rooms

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:

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

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

Explanation 1

  1. We can use brute force BFS 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
/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = new Set();
    const queue = [];
    visited.add(0);
    queue.push(0);

    while (queue.length) {
        const curRoom = queue.shift();
        for (const key of rooms[curRoom]) {
            if (!visited.has(key)) {
                visited.add(key);
                queue.push(key);
            }
        }
    }

    return visited.size === rooms.length;
};

Explanation 2

  1. We can also use DFS 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
/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = new Set();
    const queue = [];
    visited.add(0);
    queue.push(0);

    while (queue.length) {
        const curRoom = queue.pop();
        for (const key of rooms[curRoom]) {
            if (!visited.has(key)) {
                visited.add(key);
                queue.push(key);
            }
        }
    }

    return visited.size === rooms.length;
};

Design Underground System

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t)

  • A customer with a card id equal to id, gets in the station stationName at time t.

  • A customer can only be checked into one place at a time.

void checkOut(int id, string stationName, int t)

  • A customer with a card id equal to id, gets out from the station stationName at time t.

double getAverageTime(string startStation, string endStation)

  • Returns the average time to travel between the startStation and the endStation.

  • The average time is computed from all the previous traveling from startStation to endStation that happened directly.

  • Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. If a customer gets in at time t1 at some station, they get out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.00000. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.00000
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.00000

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667

Constraints:

  • There will be at most 20000 operations.

  • 1 <= id, t <= 106

  • All strings consist of uppercase and lowercase English letters, and digits.

  • 1 <= stationName.length <= 10

  • Answers within 10^-5 of the actual value will be accepted as correct.

Hint 1:

Use two hash tables. The first to save the check-in time for a customer and the second to update the total time between two stations.

Explanation

  1. In the checkIn method, we create a hashmap checkinHm to record the input. The key is id, the value is a pair of [stationName, checkInTime].

  2. In the checkOut method, we need to prepare to calculate the average time between two stations, so we need a route name checkInStation#checkOutStation, and its total travel time and total number of travels. So we need a another hashmap routeHm, key is routeName, value is a pair of [totalTime, totalNumTravel]. So in the checkOut method, we need to record and update these data in this hashmap.

  3. In the getAverageTime method, we can just use the routeHm to get the current route’s total time divide its total number of travels to get the average time.

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

var UndergroundSystem = function() {
    this.checkinHm = new Map();
    this.routeHm = new Map();
};

/**
 * @param {number} id
 * @param {string} stationName
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkIn = function(id, stationName, t) {
    this.checkinHm.set(id, [stationName, t]);
};

/**
 * @param {number} id
 * @param {string} stationName
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkOut = function(id, stationName, t) {
    const [checkinStation, checkinTime] = this.checkinHm.get(id);
    const route = checkinStation + "#" + stationName;
    const curRouteTime = t - checkinTime;
    if (!this.routeHm.has(route)) {
        this.routeHm.set(route, [curRouteTime, 1]);
    } else {
        const [totalRouteTime, totalNumTravel] = this.routeHm.get(route);
        this.routeHm.set(route, [totalRouteTime + curRouteTime, totalNumTravel + 1]);
    }
};

/**
 * @param {string} startStation
 * @param {string} endStation
 * @return {number}
 */
UndergroundSystem.prototype.getAverageTime = function(startStation, endStation) {
    const route = startStation + "#" + endStation;
    const [totalRouteTime, totalNumTravel] = this.routeHm.get(route);
    return totalRouteTime / totalNumTravel;
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * var obj = new UndergroundSystem()
 * obj.checkIn(id,stationName,t)
 * obj.checkOut(id,stationName,t)
 * var param_3 = obj.getAverageTime(startStation,endStation)
 */

Reordered Power of 2

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

1
2
Input: 1
Output: true

Example 2:

1
2
Input: 10
Output: false

Example 3:

1
2
Input: 16
Output: true

Example 4:

1
2
Input: 24
Output: false

Example 5:

1
2
Input: 46
Output: true

Note:

  1. 1 <= N <= 10^9

Explanation 1:**

  1. We can generate all permutations of N and check each permutation if its power of two.

  2. To generate permutation, we place any digit into the first position (start = 0), then any of the remaining digits into the second position (start = 1), and so on.

  3. To check if a number is power of two, while the number is even, we can right shift it until it becomes odd number. Then we check if this odd number equals to 1, then it’s power of two, otherwise it’s not power of two.

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} N
 * @return {boolean}
 */
var reorderedPowerOf2 = function(N) {
    const S = N.toString();
    const nums = S.split("").map(Number);
    return permutation(nums, 0);
};

var permutation = function(nums, start) {
    if (start === nums.length) return isPowerOfTwo(nums);

    for (let i = start; i < nums.length; i++) {
        [nums[start], nums[i]] = [nums[i], nums[start]];

        if (permutation(nums, start+1)) return true;

        [nums[start], nums[i]] = [nums[i], nums[start]];
    }

    return false;
}

var isPowerOfTwo = function(nums) {
    if (nums[0] === 0) return false;
    let num = nums.reduce((prev, cur) => prev * 10 + cur, 0);
    while (num > 0 && (num & 1) === 0) {
        num >>= 1;
    }
    return num === 1;
}

Explanation 2

  1. Since the input number has a constraint between 1 to 10^9, we can generate all numbers that is power of two and compare it with the input. Since the input digit can reorder, we can compare by every digit’s frequency.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} N
 * @return {boolean}
 */
var reorderedPowerOf2 = function(N) {
    const arr = count(N);
    for (let i = 0; i < 31; i++) {
        const temp = count(1 << i);
        if (arr.every((e, i) => e === temp[i])) return true;
    }
    return false;
};

var count = function(N) {
    const res = Array(10).fill(0);
    while (N > 0) {
        res[N % 10] += 1;
        N = ~~(N/10);
    }
    return res;
}

Week 4: March 22nd - March 28th

Find Smallest Common Element in All Rows

Given a matrix mat where every row is sorted in strictly increasing order, return the smallest common element in all rows.

If there is no common element, return -1.

Example 1:

1
2
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

Constraints:

  • 1 <= mat.length, mat[i].length <= 500

  • 1 <= mat[i][j] <= 10^4

  • mat[i] is sorted in strictly increasing order.

Hint 1:

Notice that each row has no duplicates.

Hint 2:

Is counting the frequency of elements enough to find the answer?

Hint 3:

Use a data structure to count the frequency of elements.

Hint 4:

Find an element whose frequency equals the number of rows.

Explanation

  1. We can use brute force to solve this problem. Count the frequency of every number, if there’s a number’s frequency equals to mat.length, then we return that number.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int smallestCommonElement(int[][] mat) {
        int cnt[] = new int[10001];
        int row = mat.length, col = mat[0].length;

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (++cnt[mat[i][j]] == row) return mat[i][j];
            }
        }

        return -1;
    }
}

Vowel Spellchecker

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.

  • Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"

  • Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"

  • Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"

Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.

  • Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"

  • Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)

  • Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

  • When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.

  • When the query matches a word up to capitlization, you should return the first such match in the wordlist.

  • When the query matches a word up to vowel errors, you should return the first such match in the wordlist.

  • If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

1
2
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

  • 1 <= wordlist.length <= 5000

  • 1 <= queries.length <= 5000

  • 1 <= wordlist[i].length <= 7

  • 1 <= queries[i].length <= 7

  • All strings in wordlist and queries consist only of english letters.

Explanation

  1. We need to consider three cases. First case is when the query is exact match the word, we return the word. Second case is when the query match all characters case insensitively, we return the word. Third case is when the query is replacing all vowels then it matches the word which is also replacing all vowels case insensitively, we return the word.

  2. For the first case, we can use a set to hold all the words, then check if the query is in the set. For the second case, we can create a map, key is lower case of word, value is the original word; then check if the query’s lower case is in the map, then we return its corresponding word. For the third case, we can also create a map, key is the lower case of the word after replacing all vowels with a placeholder #, value is the original word; then check if the query after replacing all vowels with a same placeholder # is in the map, then return its corresponding original word. If the query is not matched with all three cases, then we add an empty string to the result array.

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
/**
 * @param {string[]} wordlist
 * @param {string[]} queries
 * @return {string[]}
 */
var spellchecker = function(wordlist, queries) {
    const res = [];
    const vowelRegex = /[aeiou]/g;
    const set = new Set(wordlist);
    const capHm = new Map(), vowelHm = new Map();

    for (let i = wordlist.length-1; ~i; i--) {
        const lower = wordlist[i].toLowerCase();
        capHm.set(lower, wordlist[i]);
        const deVow = lower.replace(vowelRegex, "#");
        vowelHm.set(deVow, wordlist[i]);
    }

    for (const query of queries) {
        const lower = query.toLowerCase();
        const deVow = lower.replace(vowelRegex, "#");
        if (set.has(query)) {
            res.push(query);
        } else {
            res.push(capHm.get(lower) || vowelHm.get(deVow) || "");
        }
    }

    return res;
};

3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

1
2
3
4
5
6
7
8
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

1
2
3
4
5
6
Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Constraints:

  • 3 <= arr.length <= 3000

  • 0 <= arr[i] <= 100

  • 0 <= target <= 300

Explanation

  1. We think of arr[i] is the third number, then the result res should be adding the frequency of the sum of the first two numbers. We can create a hashmap, the key is the sum of the first two numbers, the value is its frequency.

  2. Loop through the array, the current element is arr[i], then adding the frequency of the sum of the first two numbers, in other words, res += hm[target-arr[i]]. Then loop j from 0 to i inclusive. Now to prepare the next thrid number arr[i+1], the sum of the first two numbers are arr[j] + arr[i] and we update its frequency in the hashmap.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(arr, target) {
    const MOD = 1e9 + 7;
    let res = 0;
    const hm = new Map();

    for (let i = 0; i < arr.length; i++) {
        res = (res + (hm.get(target - arr[i]) || 0)) % MOD;

        for (let j = 0; j < i; j++) {
            const sum = arr[j] + arr[i];
            hm.set(sum, (hm.get(sum) || 0) + 1);
        }
    }

    return res;
};

Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

1
2
Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

1
2
Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:

  1. 1 <= A.length = B.length <= 10000

  2. 0 <= A[i] <= 10^9

  3. 0 <= B[i] <= 10^9

Explanation

  1. We can use greddy to solve this problem. We always want to satisfy the biggest number of B first because that is the hardest number to satisfy. If we can’t find a number from A to satisfy the biggest number of B, then we use the smallest number from A.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
var advantageCount = function(A, B) {
    const ord = Uint16Array.from({ length: B.length }, (_, i) => i);
    const res = new Uint32Array(B.length);
    ord.sort((a,b) => B[b] - B[a]);
    A.sort((a,b) => b - a);
    let i = 0, j = B.length - 1;
    for (const idx of ord) res[idx] = A[i] > B[idx] ? A[i++] : A[j--];
    return res;
};

Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  1. The order of returned grid coordinates does not matter.

  2. Both m and n are less than 150.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Explanation

  1. We can solve this problem using BFS. We need two visited arrays pacific[][] and atlantic[][] to note down if the elements can reach pacific or atlantic. Initially, we mark the top and left side elements in the pacific[][] be true, right side and bottom side element in the atlantic[][] be true. We also create two queues queuePacific and queueAtlantic to initially store top side and left side into queuePacific, right side and bottom side element into queueAtlantic.

  2. Now, we need two BFS helper method. We pass matrix[][], pacific[][] or atlantic[][] as visitied[][], and pass queuePacific or queueAtlantic as queue corresponding to their visited[][].

  3. Inside the BFS helper method, while the queue is not empty, we pop element out as temp[]. We need to loop through four directions and update row temp[0] and column temp[1]. If the row or column are not inside the range, or visited[r][c] is true, or the updated matrix[r][c] is less than the original temp[0] and temp[1]’s matrix height, we continue the loop and check the next direction. Else, we update the updated row and col in the visited[r][c] be true, then push it to the queue.

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
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
    const res = [];
    if (matrix.length === 0 || matrix[0].length === 0) return res;

    const row = matrix.length, col = matrix[0].length;
    const pacific = Array(row).fill(false).map(_ => Array(col).fill(false));
    const atlantic = Array(row).fill(false).map(_ => Array(col).fill(false));
    const queuePacific = [];
    const queueAtlantic = [];

    for (let r = 0; r < row; r++) {
        const tempP = [r, 0];
        const tempA = [r, col-1];
        queuePacific.push(tempP);
        queueAtlantic.push(tempA);
        pacific[r][0] = true;
        atlantic[r][col-1] = true;
    }

    for (let c = 0; c < col; c++) {
        const tempP = [0, c];
        const tempA = [row-1, c];
        queuePacific.push(tempP);
        queueAtlantic.push(tempA);
        pacific[0][c] = true;
        atlantic[row-1][c] = true;
    }

    helper(matrix, pacific, queuePacific);
    helper(matrix, atlantic, queueAtlantic);

    for (let r = 0; r < row; r++) {
        for (let c = 0; c < col; c++) {
            if (pacific[r][c] === true && atlantic[r][c] === true) {
                const temp = [r, c];
                res.push(temp);
            }
        }
    }

    return res;
};

var helper = function(matrix, visited, queue) {
    const row = matrix.length;
    const col = matrix[0].length;
    const dirs = [[0, -1], [0, 1], [1, 0], [-1, 0]];
    while (queue.length) {
        const temp = queue.shift();
        for (const dir of dirs) {
            const r = temp[0] + dir[0], c = temp[1] + dir[1];
            if (r < 0 || r >= row || c < 0 || c >= col || visited[r][c] === true || matrix[r][c] < matrix[temp[0]][temp[1]]) {
                continue;
            }
            visited[r][c] = true;
            const tempRes = [r, c];
            queue.push(tempRes);
        }
    }
};

Word Subsets

We are given two arrays A and B of words. Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".

Now say a word a from A is universal if for every b in B, b is a subset of a.

Return a list of all universal words in A. You can return the words in any order.

Example 1:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

1
2
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

Note:

  1. 1 <= A.length, B.length <= 10000

  2. 1 <= A[i].length, B[i].length <= 10

  3. A[i] and B[i] consist only of lowercase letters.

  4. All words in A[i] are unique: there isn’t i != j with A[i] == A[j].

Explanation

  1. First we get every characters’ maximum frequency in B and record it in count[26]. Then loop through every word a from A. If any character’s frequency from a word a have less frequency than its corresponding character from count[i], then this word a is not universal, else it’s universal and we add it in the result list.

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
/**
 * @param {string[]} A
 * @param {string[]} B
 * @return {string[]}
 */
var wordSubsets = function(A, B) {
    const count = Array(26).fill(0);
    for (const s of B) {
        const temp = counter(s);
        for (let i = 0; i < 26; i++) {
            count[i] = Math.max(count[i], temp[i]);
        }
    }

    const res = [];
    for (const s of A) {
        const temp = counter(s);
        let i = 0;
        for (i = 0; i < 26; i++) {
            if (count[i] > temp[i]) break;
        }
        if (i === 26) res.push(s);
    }

    return res;
};

var counter = function(s) {
    const cnt = Array(26).fill(0);
    for (const ch of s) {
        cnt[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    return cnt;
}

Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

Hint 1:

How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2:

If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?

Hint 3:

Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?

Explanation 1

  1. Loop through the string, for every character, we think it as the middle. Palindrome has two cases. Case 1 is odd length string, we can initialize two pointers i and j pointing to the same character. If s[i] == s[j], we increase the result, and i move left, j move right, until their pointing character different. Case 2 is even length string, so initialy, i points at the middle left, j points at the middle right, and check their character if they are the same. If they are the same, we increase the result and move i left, move j right.

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
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let res = 0;
    if (s.length < 2) return s.length;
    for (let i = 0; i < s.length; i++) {
        res += helper(s, i, i);
        res += helper(s, i, i+1);
    }
    return res;
};

var helper = function(s, mid1, mid2) {
    let res = 0;
    while (mid1 >= 0 && mid2 < s.length && s[mid1] === s[mid2]) {
        res += 1;
        mid1 -= 1;
        mid2 += 1;
    }
    return res;
}

Explanation 2

  1. We can also use dynamic programming to solve this problem. Dynamic state is a boolean two dimensional arraydp[i][j] represents str[i:j] if it’s palindrome or not.

  2. Dynamic init, all elements are false.

  3. Dynamic function. dp[i][j] will be true if str[i] == str[j] && (j - i <= 2), for example str=aba, str[i=0]=a and str[j=2]=a. What if j - i > 2. For example, str=xabax, str[i=0] = x, str[j=4]=x. If str[i] == str[j], then dp[i][j] will be true if dp[i+1][j-1] is true, in this case we need to check dp[i+1=1][j-1=3], so we need to loop i from the right to left, loop j from i to the right. And the dynamic function is dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]).

  4. Dynamic result. Every time, we check the dp[i][j] is true, we increase the result counter.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    if (s.length < 2) return s.length;
    let res = 0;
    const dp = Array(s.length).fill(false).map(_ => Array(s.length).fill(false));

    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i; j < s.length; j++) {
            if (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])) {
                dp[i][j] = true;
                res += 1;
            }
        }
    }

    return res;
};

Reconstruct Original Digits from English

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.

  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.

  3. Input length is less than 50,000.

Example 1:

1
2
3
Input: "owoztneoer"

Output: "012"

Example 2:

1
2
3
Input: "fviefuro"

Output: "45"

Explanation

  1. First, we count the frequency of all characters in the input string. Then, we notice from the English representation of these 10 digits "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", some character appear only once in a specific English representation. For example, z only appears in zero. w，u，x，g appear only in two，four，six，eight respectivly. So these 5 English representation are decided.

  2. For character o, it appears in zero，two，four，one, since the first three are decided, we can use the frequency of character o to subtract the first 3 English representation letter’s frequency in order to get the frequency of one. For character h, it appears in eight, three, since the first one is decided, we can calculate the frequency of three. For character f, it appears in four, five, since the first one is decided, we can calculate the frequency of five. For character s, it appears in six, seven, since the first one is decided, we can calculate the frequency of seven. For character i, it appears in six，eight，five，nine, since the first three are decided, we can calculate the frequency of nine.

  3. Therefore, we can find the frequency of English representation by following this order: "zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine".

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 {string} s
 * @return {string}
 */
var originalDigits = function(s) {
    const counts = Array(26).fill(0);
    for (const ch of s) {
        counts[ch.charCodeAt(0) - 97] += 1;
    }

    const nums = Array(10).fill(0);
    nums[0] = counts['z'.charCodeAt(0) - 97];
    nums[2] = counts['w'.charCodeAt(0) - 97];
    nums[4] = counts['u'.charCodeAt(0) - 97];
    nums[6] = counts['x'.charCodeAt(0) - 97];
    nums[8] = counts['g'.charCodeAt(0) - 97];
    nums[1] = counts['o'.charCodeAt(0) - 97] - nums[0] - nums[2] - nums[4];
    nums[3] = counts['h'.charCodeAt(0) - 97] - nums[8];
    nums[5] = counts['f'.charCodeAt(0) - 97] - nums[4];
    nums[7] = counts['s'.charCodeAt(0) - 97] - nums[6];
    nums[9] = counts['i'.charCodeAt(0) - 97] - nums[6] - nums[8] - nums[5];

    const res = [];
    for (let i = 0; i < nums.length; i++) {
        res.push(i.toString().repeat(nums[i]));
    }

    return res.join('');
};

Week 5: March 29th - March 31st

Parallel Courses

You are given an integer n which indicates that we have n courses, labeled from 1 to n. You are also given an array relations where relations[i] = [a, b], representing a prerequisite relationship between course a and course b: course a has to be studied before course b.

In one semester, you can study any number of courses as long as you have studied all the prerequisites for the course you are studying.

Return the minimum number of semesters needed to study all courses. If there is no way to study all the courses, return -1.

Example 1:

Parallel Courses

1
2
3
Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: In the first semester, courses 1 and 2 are studied. In the second semester, course 3 is studied.

Example 2:

Parallel Courses

1
2
3
Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: No course can be studied because they depend on each other.

Constraints:

  • 1 <= n <= 5000

  • 1 <= relations.length <= 5000

  • 1 <= a, b <= n

  • a != b

  • All the pairs [a, b] are unique.

Hint 1:

Try to think of it as a graph problem. It will be impossible to study all the courses if the graph had a cycle.

Hint 2:

The graph is a directed acyclic graph (DAG). The answer is the longes path in this DAG.

Hint 3:

You can use DP to find the longest path in the DAG.

Explanation

  1. This is a topological sorting problem. First, we need to implement a inDegree[i] to record how many prerequisites course i has. Also we need to implement a hashmap hm[int]int[], key is the current course, value is a list of courses that depends on the current course.

  2. We can use BFS way of topological sorting. First pushing all courses that have zero dependency into a queue. While the queue is not empty, we increase the semesterCount, then loop queue.size() times, poll out the current course, increase the courseCount. Then loop through all the courses that depends on the current course, update their inDegree[]. If after update, the inDegree becomes zero, then we push that course into the queue.

  3. At the end when the queue is empty, if courseCount if not equals to n, then we return -1, else return semesterCount.

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
class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        int[] inDegree = new int[n];
        Map<Integer, List<Integer>> hm = new HashMap<>();
        int res = 0;
        int cnt = 0;

        for (int[]relation: relations) {
            inDegree[relation[1]-1] += 1;
            hm.computeIfAbsent(relation[0]-1, k -> new ArrayList<>()).add(relation[1]-1);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            res += 1;
            for (int i = queue.size() - 1; i >= 0; i--) {
                int cur = queue.poll();
                cnt += 1;
                for (int nextCourse: hm.getOrDefault(cur, new ArrayList<>())) {
                    inDegree[nextCourse] -= 1;
                    if (inDegree[nextCourse] == 0) {
                        queue.offer(nextCourse);
                    }
                }
            }
        }

        return cnt == n ? res : -1;
    }
}

Flip Binary Tree To Match Preorder Traversal

You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.

Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

Flip Binary Tree To Match Preorder Traversal

Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.

Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].

Example 1:

Flip Binary Tree To Match Preorder Traversal

1
2
3
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

Example 2:

Flip Binary Tree To Match Preorder Traversal

1
2
3
Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

Example 3:

Flip Binary Tree To Match Preorder Traversal

1
2
3
Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation: The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.

Constraints:

  • The number of nodes in the tree is n.

  • n == voyage.length

  • 1 <= n <= 100

  • 1 <= Node.val, voyage[i] <= n

  • All the values in the tree are unique.

  • All the values in voyage are unique.

Explanation

  1. We can use brute force to solve this problem. First checking the root node. If root node is NULL, then return true. If root node is not equal to voyage[globalIdx] then return false. Next checking the root node’s left child node. If its not equal to voyage[globalIdx], then we flip it, add the current root node to the list, recursively run helper(root.right, voyage) && helper(root.left, voyage). Else if the root node’s left child equals to voyage[globalIdx], then we just run normal pre-order traversal helper(root.left, voyage) && helper(root.right, voyage). If the helper function returns false, then the result is [-1]. else we return the result list.

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
/**
 * 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[]} voyage
 * @return {number[]}
 */
var flipMatchVoyage = function(root, voyage) {
    const res = [];
    let idx = 0;

    const helper = function(root) {
        if (!root) return true;
        if (root.val !== voyage[idx++]) return false;

        if (root.left && root.left.val !== voyage[idx]) {
            res.push(root.val);
            return helper(root.right) && helper(root.left);
        }
        return helper(root.left) && helper(root.right);
    }

    const isValid = helper(root);
    return isValid ? res : [-1];
};

Russian Doll Envelopes

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

1
2
3
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

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

Constraints:

  1. 1 <= envelopes.length <= 5000

  2. envelopes[i].length == 2

  3. 1 <= wi, hi <= 10^4

Explanation

  1. We can use dynamic programming to solve this problem. First, we will sort the envelopes by width ascending, if the width is the same, we sort height ascending.

  2. Dynamic state is a one dimensional array dp[i] which represents until the ith index envelope (inclusive), the maximum Russian Doll Envelopes it has.

  3. Dynamic init is all dp[i] at least equals to 1, which is itself’s envelope.

  4. Dynamic function will be dp[i] = max(dp[i], dp[j] + 1) for 0 <= j < i and only if envelopes[i]’s width and height is greater than envelopes[j]’s width and height. Every time after we update dp[i], we compare it with res to update res be the maximum.

  5. Dynamic result will be res.

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 {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    let res = 1;
    envelopes.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        } else {
            return a[0] - b[0];
        }
    });

    const dp = Array(envelopes.length).fill(1);
    for (let i = 0; i < dp.length; i++) {
        for (let j = 0; j < i; j++) {
            if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }

    return res;
};

Stamping The Sequence

You want to form a target string of lowercase letters.

At the beginning, your sequence is target.length '?' marks. You also have a stamp of lowercase letters.

On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp. You can make up to 10 * target.length turns.

For example, if the initial sequence is “?????”, and your stamp is "abc", then you may make “abc??”, “?abc?”, “??abc” in the first turn. (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)

If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn. If the sequence is not possible to stamp, return an empty array.

For example, if the sequence is “ababc”, and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves “?????” -> “abc??” -> “ababc”.

Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves. Any answers specifying more than this number of moves will not be accepted.

Example 1:

1
2
3
Input: stamp = "abc", target = "ababc"
Output: [0,2]
([1,0,2] would also be accepted as an answer, as well as some other answers.)

Example 2:

1
2
Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]

Note:

  1. 1 <= stamp.length <= target.length <= 1000

  2. stamp and target only contain lowercase letters.

Explanation

  1. The last stamp will replace every characters of stamp on the target, so we can think in a reverse way. Let’s take an example to illustrate.Stamp = "abc", Target = "ababcbc".
1
2
3
  1) Target = ab***bc
  2) Target = ab*****
  3) Target = *******
  1. We will go through the whole Target string to find if there exists any substring equals to Stamp. And then replace the whole substring with *. We can see in the step 1, we replace substring abc with ***. Then we keep doing the same thing. In the step 2, we replace substring *bc to ***. * can match to any character because * will be override by the next stamp. Finally we get the result and output the reversed result. When the number of stars equals to target.length, we will return the result. If during one scan, we are not able to replace even one substring with *, directly return empty array.

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
/**
 * @param {string} stamp
 * @param {string} target
 * @return {number[]}
 */
var movesToStamp = function(stamp, target) {
    const res = [];
    const sArr = stamp.split('');
    const tArr = target.split('');
    const visited = Array(tArr.length).fill(false);
    let stars = 0;

    while (stars < tArr.length) {
        let doneReplace = false;
        for (let i = 0; i <= tArr.length - sArr.length; i++) {
            if (!visited[i] && canReplace(sArr, tArr, i)) {
                stars += doReplace(sArr, tArr, i);
                doneReplace = true;
                visited[i] = true;
                res.push(i);
                if (stars === tArr.length) break;
            }
        }

        if (!doneReplace) return [];
    }

    return res.reverse();
};

var canReplace = function(sArr, tArr, start) {
    for (let i = 0; i < sArr.length; i++) {
        if (tArr[start + i] !== '*' && tArr[start + i] !== sArr[i]) {
            return false;
        }
    }
    return true;
}

var doReplace = function(sArr, tArr, start) {
    let cnt = 0;
    for (let i = 0; i < sArr.length; i++) {
        if (tArr[start + i] !== '*') {
            tArr[start + i] = '*';
            cnt += 1;
        }
    }
    return cnt;
}

Source: https://leetcode.com/problems/stamping-the-sequence/discuss/201546/12ms-Java-Solution-Beats-100