Happy 2021! It’s been a long year working from home. In 2020, I used Go for leetcoding, read some JavaScript books, and watched tutorials about JavaScript, Node.js, DOM, and CSS. This year I will improve my JavaScript data structure, indepth of Node.js, front-end, and back-end development, and learn some Web Assembly.

Week 1: January 1st - January 7th

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

Hint 1:

Consider the palindromes of odd vs even length. What difference do you notice?

Hint 2:

Count the frequency of each character.

Hint 3:

If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Explanation

A even length palindrome means every number appears even number of times. An odd length palindrome means there’s only one number appear odd number of times.
We can first count every number’s frequency, then we loop through the hashmap and count how many odd number frequency. If ther are more than one odd number frequency then we can return false immediately. At the end, we return true.

Solution

class Solution {
    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> hm = new HashMap<>();
        for (char ch: s.toCharArray()) {
            hm.put(ch, hm.getOrDefault(ch, 0) + 1);
        }

        int oddCnt = 0;
        for (Map.Entry<Character, Integer> entry: hm.entrySet()) {
            int freq = entry.getValue();
            if (freq % 2 == 1) {
                oddCnt += 1;
                if (oddCnt == 2) return false;
            }
        }

        return true;
    }
}

Check Array Formation Through Concatenation

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

Hint 1:

Note that the distinct part means that every position in the array belongs to only one piece

Hint 2:

Note that you can get the piece every position belongs to naively

Explanation

Loop through the pieces[] array, for every pieces[i], we store its first element pieces[i][0] and the pieces index i into a hashmap as key value pair.
Next, we loop through the array arr, if the current element arr[i] is not in the hashmap, that means its not the first piece element so we return false. Else, we can get the piece index pIdx = hm.get(arr[i]), and start comparing arr[i] with pieces[PIdx][j] where j is the index for the subarray pieces[Pidx].

Solution

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function(arr, pieces) {
    const hm = new Map();
    for (let i = 0; i < pieces.length; i++) {
        hm.set(pieces[i][0], i);
    }
    
    let i = 0;
    while (i < arr.length) {
        if (!hm.has(arr[i])) return false;
        const pIdx = hm.get(arr[i]);
        let j = 0;
        while (i < arr.length && j < pieces[pIdx].length) {
            if (arr[i] != pieces[pIdx][j]) return false;
            i += 1;
            j += 1;
        }
    }
    
    return true;
};

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

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

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Explanation

This is a tree traversal probelm. We can traversal the tree, when we find an target node equal to the original node, then we can return the corresponding cloned node.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} original
 * @param {TreeNode} cloned
 * @param {TreeNode} target
 * @return {TreeNode}
 */

var getTargetCopy = function(original, cloned, target) {
    if (original == null) return null;
    const leftRes = getTargetCopy(original.left, cloned.left, target);
    
    if (leftRes != null) return leftRes;
    if (target == original) return cloned;
    
    return getTargetCopy(original.right, cloned.right, target);
};

Beautiful Arrangement

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

perm[i] is divisible by i.
i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 15

Explanation

We can use DFS recursion to solve this problem. We need a visited array to record whether the number is visited or not in the result permutation. We initialize the result permutation position pos to 1. In the recursive helper function, the base case is if pos == N+1, then it means we finish iterating all the numbers from 1 to N, so we increase res. The recursion function will be a for loop i from 1 to N inclusive. If the current number i is not visited and i % pos == 0 or pos % i == 0, then we mark i visited and recursivly call the helper function with pos + 1. After the helper function, we need to backtract the visited[i] = false.

Solution

/**
 * @param {number} n
 * @return {number}
 */
var countArrangement = function(n) {
    const res = [0];
    const pos = 1;
    const visited = Array(n+1).fill(false);
    helper(n, pos, visited, res);
    return res[0];
};

var helper = function(n, pos, visited, res) {
    if (pos === n + 1) {
        res[0] += 1
    }
    
    for (let i = 1; i <= n; i++) {
        if (!visited[i] && (i % pos === 0 || pos % i === 0)) {
            visited[i] = true;
            helper(n, pos + 1, visited, res);
            visited[i] = false;
        }
    }
}

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both l1 and l2 are sorted in non-decreasing order.

Explanation 1

First, create a ListNode to hold the result.
While l1 and l2 are not null, compare l1 and l2’s value and putting the smaller one to the result ListNode.
We need a pointer pointing to the result node.

Solution 1

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const dummy = new ListNode();
    let resPtr = dummy;
    let ptr1 = l1;
    let ptr2 = l2;
    
    while (ptr1 && ptr2) {
        if (ptr1.val < ptr2.val) {
            resPtr.next = ptr1;
            ptr1 = ptr1.next;
        } else {
            resPtr.next = ptr2;
            ptr2 = ptr2.next;
        }
        resPtr = resPtr.next;
    }
    
    if (ptr1 === null) {
        resPtr.next = ptr2;
    } else {
        resPtr.next = ptr1;
    }
    
    return dummy.next;
};

Explanation 2

We can compare the l1 and l2’s first node value, if l1’s node value is smaller, then recusivly compare l1.next with l2, vice versa. If one of the ListNode is null, simply return another ListNode.

Solution 2

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

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

Example 2:

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

Constraints:

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

The list is guaranteed to be sorted in ascending order.

Explanation

We need to check if the current element is same as its previous element and its next element, so we need to create a dummy node, and a pre pointer initially points at the dummy node, a current pointer initially points at the first element, and we compare current pointer element with pre pointer element and current.next element.
If the current element is not the same as its previous and next element, then we need to store it into a linkedlist, so we can store the first distinct element into dummy.next, at the end we can return dummy.next.
After we store the matching current element, we need to move pre and cur pointers to point at the next element. Because now cur points at the correct next element and we want to cut off the result list and input list, we can set pre.next to null, one example is input list is [1, 2, 2], we want the result list to be [1]. Also, initially, the dummy.next is null and it’s not pointing to the head of the input linkedlist.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    const dummy = new ListNode();
    let resPtr = dummy;
    let pre = dummy;
    let cur = head;
    while (cur !== null) {
        if ((pre === dummy || pre.val !== cur.val) && (cur.next === null || cur.val !== cur.next.val)) {
            resPtr.next = cur;
            resPtr = resPtr.next;            
        }
        pre = cur;
        cur = cur.next;
        pre.next = null;
    }
    return dummy.next;
};

Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Hint 1:

Keep track of how many positive numbers are missing as you scan the array.

Explanation 1

We can use brute force to solve this problem. First, create a variable counter and a variable missing to count number of missing. Then, loop through the array, compare counter with the current iterated number. While counter is less than num, then we increase missing. If missing reaches k, we return counter, else, we increase counter. After finish looping all numbers, if missing is less than k, then we return arr[arr.length-1] + (k - missing).

Solution 1

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
    let counter = 0, missing = 0;
    for (const num of arr) {
        counter += 1;

        while (counter < num) {
            missing += 1;
            if (missing == k) return counter;
            counter += 1;
        }
    }
    
    if (missing < k) return arr[arr.length-1] + (k - missing);
    return -1;
};

Explanation 2

We are maintaining such invariant throughout the loop: left + k <= res <= right + k. Obviously when the array is missing k or more elements in the beginning, res = k; when there is no missing elements, ans is arr.length + k.
The number of missing is equals to A[m] - m - 1 where m is the number of not missing.
We can use binary search to find the first element at index left to make the number of missing equals to k.
left + k is the kth missing number because in the range of [1, left+k], there are left numbers not missing, and k numbers are missing.

Solution 2

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

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

Explanation

We can solve this problem using sliding window technique. Think of we will maintain a window that contains all unique characters. First initialize windowStart and windowEnd to 0. Also, initialize a hashset to record the window’s unique characters.
Loop the windowEnd from index 0 to the last index of the input string. While the set contains the current iterated character, we remove the window’s left character str[windowStart] and move windowStart 1 step forward, repeat this while loop until the set doesn’t contains the incoming iterated character. Next, we add the iterated character into the set, then calculate the result be max(res, windowEnd - windowStart + 1).

Solution

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set();
    let res = 0;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
        const ch = s[windowEnd];
        while (set.has(ch)) {
            const leftCh = s[windowStart];
            set.delete(leftCh);
            windowStart += 1;
        }
        set.add(ch);
        res = Math.max(res, windowEnd - windowStart + 1);
    }

    return res;
};

Week 2: January 8th - January 14th

Find Root of N-Ary Tree

You are given all the nodes of an N-ary tree as an array of Node objects, where each node has a unique value.

Return the root of the N-ary tree.

Custom testing:

An N-ary tree can be serialized as represented in its level order traversal where each group of children is separated by the null value (see examples).

For example, the above tree is serialized as

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].

The testing will be done in the following way:

The input data should be provided as a serialization of the tree.
The driver code will construct the tree from the serialized input data and put each Node object into an array in an arbitrary order.
The driver code will pass the array to findRoot, and your function should find and return the root Node object in the array.
The driver code will take the returned Node object and serialize it. If the serialized value and the input data are the same, the test passes.

Example 1:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

Example 2:

Input: tree = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Constraints:

The total number of nodes is between [1, 5 * 10^4].
Each node has a unique value.

Follow up:

Could you solve this problem in constant space complexity with a linear time algorithm?

Hint 1:

Node with indegree 0 is the root

Explanation 1

Loop through all the nodes, in each iteration, we add the current node’s children nodes into a visited set. At the end, only the root node would not be in the set.

Solution 1

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        Set<Node> visited = new HashSet<>();

        for (Node cur: tree) {
            for (Node child: cur.children) {
                visited.add(child);
            }
        }
        
        for (Node cur: tree) {
            if (!visited.contains(cur)) return cur;
        }
        
        return null;
    }
}

Explanation 2

Instead of using a set, we can create a variable sum. We increase the current iterated node’s value, subtract its children node’s values. At the end, the sum is equal to the root node’s value since all nodes are unique.

Solution 2

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        int sum = 0;

        for (Node cur: tree) {
            sum += cur.val;
            for (Node child: cur.children) {
                sum -= child.val;
            }
        }
        
        for (Node cur: tree) {
            if (cur.val == sum) return cur;
        }
        
        return null;
    }
}

Explanation 3

Instead of summing and subtracting, we can do XOR.

Solution 3

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        int sum = 0;

        for (Node cur: tree) {
            sum ^= cur.val;
            for (Node child: cur.children) {
                sum ^= child.val;
            }
        }
        
        for (Node cur: tree) {
            if (cur.val == sum) return cur;
        }
        
        return null;
    }
}

Check If Two String Arrays are Equivalent

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10^3
1 <= word1[i].length, word2[i].length <= 10^3
1 <= sum(word1[i].length), sum(word2[i].length) <= 10^3
word1[i] and word2[i] consist of lowercase letters.

Hint 1:

Concatenate all strings in the first array into a single string in the given order, the same for the second array.

Hint 2:

Both arrays represent the same string if and only if the generated strings are the same.

Explanation

Brute force approach will be concatenate all words in the array and compare two strings to see if they are equal. It will takes too many space if there are many words in the array. A better approach is creating two pointers for each array: wordIdx for iterating the array and strIdx to iterate character inside each word. Then we compare character by character to see if it’s equal.

Solution

/**
 * @param {string[]} word1
 * @param {string[]} word2
 * @return {boolean}
 */
var arrayStringsAreEqual = function(word1, word2) {
    let word1Idx = word2Idx = 0;
    let str1Idx = str2Idx = 0;
    
    while (word1Idx < word1.length && word2Idx < word2.length) {
        const ch1 = word1[word1Idx][str1Idx];
        const ch2 = word2[word2Idx][str2Idx];
        if (ch1 !== ch2) return false;

        if (str1Idx + 1 < word1[word1Idx].length) {
            str1Idx += 1;
        } else {
            str1Idx = 0;
            word1Idx += 1;
        }
        if (str2Idx + 1 < word2[word2Idx].length) {
            str2Idx += 1;
        } else {
            str2Idx = 0;
            word2Idx += 1;
        }
    }
    
    return word1Idx === word1.length && word2Idx === word2.length;
};

Word Ladder

Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Return 0 if there is no such transformation sequence.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Constraints:

1 <= beginWord.length <= 100
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the strings in wordList are unique.

Explanation

We can try brute force. For every character in the word, we try to replace each character with ‘a’ to ‘z’. For example, “hit”, we replace the first character with “a”, so it is “ait”; replace it with “b”, so it is “bit”; and we get “cit”, “dit”, “eit”, …, “zit”. We check if these words if it’s the endWord, if not, check if they are in the list, if the word is in the list, then it can potentially be the path to get the endWord.
Now, if the word we try is “hot”, and we check it’s in the list, then should we try “hpt”, “hqt”, “hrt”… (BFS) or “aot”, “bot”, “cot”… (DFS)? We know that it’s better to use BFS to find the minimum path, so it’s better to use BFS. After we find a word that is equal to the endWord, we can return the level plus one immediately, we plus one because the beginWord count once.

Solution

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    
    const queue = [beginWord];
    const visited = new Set();
    visited.add(beginWord);
    let level = 0;
    
    
    while (queue.length > 0) {
        for (let i = queue.length-1; i >= 0; i--) {
            const curWord = queue.shift();
            if (curWord === endWord) return level + 1;
            const curWordArr = [...curWord];

            for (let j = 0; j < curWordArr.length; j++) {
                const ori = curWordArr[j];
                for (let k = 97; k < 97+26; k++) {
                    curWordArr[j] = String.fromCharCode(k);
                    const updatedStr = curWordArr.join('');
                    if (wordSet.has(updatedStr) && !visited.has(updatedStr)) {
                        queue.push(updatedStr);
                        visited.add(updatedStr);
                    }
                }
                curWordArr[j] = ori;
            }
        }

        level += 1;
    }
    
    return 0;
};

Create Sorted Array through Instructions

Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:

The number of elements currently in nums that are strictly less than instructions[i].
The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 10^9 + 7

Example 1:

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:

Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

Constraints:

1 <= instructions.length <= 10^5
1 <= instructions[i] <= 10^5

Hint 1:

This problem is closely related to finding the number of inversions in an array

Hint 2:

if i know the position in which i will insert the i-th element in I can find the minimum cost to insert it

Explanation

This is a Binary Indexed Tree (Fenwick Tree) problem. We store the frequency of the element into the fenwick tree, at the same time, we can calculate the left cost and right cost. If the current element is n, then the left cost left is the total frequency from 1 to n-1 inclusive; the right cost right is the total number of element in the tree, in other word, the current index i, subtract the total frequency from 1 to n inclusive.
Let N be the length of instructions and M be the maximum value in instructions.
- Time Complexity: $O(Nlog(M))$. We need to iterate over instructions, and for each element, the time to find the left cost and right cost is $O(log(M))$, and we spend $O(log(M))$ inserting the current element into the BIT. In total, we need $O(N⋅log(M))=O(Nlog(M))$.
- Space Complexity: $O(M)$, since we need an array of size $O(M)$ to store BIT.

Source: https://leetcode.com/problems/create-sorted-array-through-instructions/solution/

Solution

/**
 * @param {number[]} instructions
 * @return {number}
 */
var createSortedArray = function(instructions) {
    let res = 0;
    const fwTree = new FenwickTree(Math.max(...instructions));
    
    instructions.forEach((instruction, idx) => {
        const left = fwTree.query(instruction - 1);
        const right = idx - fwTree.query(instruction);
        res += Math.min(left, right);
        fwTree.update(instruction, 1);
    });
    
    return res % (1e9+7);
};

class FenwickTree {
    constructor(n) {
        this.sums = Array(n + 1).fill(0);        
    }
    
    query = (idx) => {
        let s = 0;
        while (idx > 0) {
            s += this.sums[idx];
            idx -= this.lowbit(idx);
        }
        return s;
    }
    
    update = (idx, delta) => {
        while (idx < this.sums.length) {
            this.sums[idx] += delta;
            idx += this.lowbit(idx);
        }
    }
    
    lowbit = (x) => {
        return x & -x;
    }
}

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

0 <= n, m <= 200
1 <= n + m <= 200
nums1.length == m + n
nums2.length == n
-10^9 <= nums1[i], nums2[i] <= 10^9

Hint 1:

You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don’t know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?

Hint 2:

If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.

Explanation

First, getting the correct end index of the merged array, then we can try to compare the end element of both array and putting the bigger one to the end index of the result array.
If one array is finish putting all elements to the result array, then we can simply copy all the elements of another array to the result array.

Solution

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let idx = nums1.length - 1;
    let p1 = m - 1;
    let p2 = n - 1;

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] >= nums2[p2]) {
            nums1[idx--] = nums1[p1--];
        } else {
            nums1[idx--] = nums2[p2--];
        }
    }

    while (p2 >= 0) {
        nums1[idx--] = nums2[p2--];
    }
};

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Explanation

Create a dummy node and a pointer cur pointing to it. While l1 or l2 is not NULL, get l1’s value and l2’s value, sum them up plus carry, module 10 to be the cur node’s next node value, then update the pointer cur to be its next node, and update l1 and l2 to be their next node.
Outside of the while loop, when both l1 and l2 are null, if the carry is not zero, we create a node of the carry’s value and append to the result ListNode.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode();
    let cur = dummy;
    let sum = carry = 0;
    let [p1, p2] = [l1, l2];
    
    while (p1 !== null || p2 !== null) {
        sum = carry;
        if (p1 !== null) {
            sum += p1.val;
            p1 = p1.next;
        }
        if (p2 !== null) {
            sum += p2.val;
            p2 = p2.next;
        }
        cur.next = new ListNode(sum % 10);
        carry = Math.floor(sum / 10);
        cur = cur.next;
    }
    
    if (carry == 1) {
        cur.next = new ListNode(1);
    }
    
    return dummy.next;
};

Boats to Save People

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Explanation

Since the boat can carray at most 2 people at the same time, we can pair the lightest person with the heaviest person. If these two people’s weight exceed the limit, we let the heaviest person take the boat. Else we pair the next lightest person with the next heaviest person.

Solution

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    let res = 0;
    let i = 0;
    let j = people.length - 1;
    people.sort((a, b) => a - b);

    while (i <= j) {
        res += 1;
        if (people[i] + people[j] <= limit) {
            i += 1;
        }
        j -= 1;
    }

    return res;
};

Minimum Operations to Reduce X to Zero

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9

Hint 1:

Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.

Hint 2:

Finding the maximum subarray is standard and can be done greedily.

Explanation 1

This problem can be transformed to 325. Maximum Size Subarray Sum Equals k.
In 325. Maximum Size Subarray Sum Equals k, we loop through the array, put the accumulate sum into a hashmap as key, index as value. Before we put into the hashmap, we check the target = sum - k if target is inside the map, we can update the size of the subarray equals k in other words, res = max(res, i - hm[target]).

Solution 1

/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function(nums, x) {
    const total = nums.reduce((prev, cur) => prev + cur, 0);
    if (x === total) return nums.length;
    
    const n = helper(nums, total - x);
    
    if (n === 0) return -1;
    else return nums.length - n;
};


var helper = function(nums, x) {
    let res = 0;
    const hm = new Map();
    hm.set(0, -1);
    let sum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        const target = sum - x;
        if (hm.has(target)) res = Math.max(res, i - hm.get(target));
        if (!hm.has(sum)) hm.set(sum, i);
    }

    return res;
}

Explanation 2

We can also use two pointers to solve this problem. First, count the total sum of the array and make a variable cur = totalSum. Loop right from first index to last index, each iteration, we subtract cur from nums[right] to get cur. While cur is less than k, we increase cur with nums[left] then move left 1 step forward. When cur == k we update the result. The length will be from the first element to left exclusive, and from right+1 to the last element.

Solution 2

/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function(nums, x) {
    let res = nums.length + 1;
    const total = nums.reduce((prev, cur) => prev + cur, 0);
    let cur = total;    
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        cur -= nums[right];
        while (cur < x && left <= right) {
            cur += nums[left];
            left += 1;
        }
        
        if (cur == x) {
            res = Math.min(res, nums.length - 1 - right + left);
        }
    }
    
    return res === nums.length + 1 ? -1 : res;
};

Week 3: January 15th - January 21st

Nested List Weight Sum

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

Example 3:

Input: nestedList = [0]
Output: 0

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list is in the range [-100, 100].
The maximum depth of any integer is less than or equal to 50.

Explanation 1

We can use recursion or DFS to solve this problem. The recursive helper function will have 2 arguments. One is the input list, another one is the current depth.
Inside the helper function, we loop through the input list. If the current element is an integer, we can update the result. Else if it’s a list, then we can recursively call the helper function pass this current list and increase the depth.

Solution 1

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    int helper(List<NestedInteger> nestedList, int depth) {
        int res = 0;
        for (NestedInteger n: nestedList) {
            if (n.isInteger()) {
                res += depth * n.getInteger();
            } else {
                res += helper(n.getList(), depth + 1);
            }
        }
        return res;
    }
    
    public int depthSum(List<NestedInteger> nestedList) {
        return helper(nestedList, 1);
    }
}

Explanation 2

We can also use BFS to solve this problem. First, put all the elements from the input list into the queue. Initialize the current depth is 1. Loop through the current level (current depth) from the queue, if the current element is an integer, we update the result. Else if it’s a list, then we append the list’s elements into the queue. When we finish iterating the current level, we increase the depth.

Solution 2:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int res = 0;
        Queue<NestedInteger> queue = new LinkedList<>();
        queue.addAll(nestedList);
        
        int depth = 1;
        while (!queue.isEmpty()) {
            for (int i = queue.size() - 1; i >= 0; i--) {
                NestedInteger cur = queue.poll();
                if (cur.isInteger()) {
                    res += cur.getInteger() * depth;
                } else {
                    queue.addAll(cur.getList());
                }
            }
            depth += 1;
        }
        
        return res;
    }
}

Get Maximum in Generated Array

You are given an integer n. An array nums of length n + 1 is generated in the following way:

nums[0] = 0
nums[1] = 1
nums[2 * i] = nums[i] when 2 <= 2 * i <= n
nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array nums.

Example 1:

Input: n = 7
Output: 3
Explanation: According to the given rules:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is 3.

Example 2:

Input: n = 2
Output: 1
Explanation: According to the given rules, the maximum between nums[0], nums[1], and nums[2] is 1.

Example 3:

Input: n = 3
Output: 2
Explanation: According to the given rules, the maximum between nums[0], nums[1], nums[2], and nums[3] is 2.

Constraints:

0 <= n <= 100

Hint 1:

Try generating the array.

Hint 2:

Make sure not to fall in the base case of 0.

Explanation

We can generate the array and find the maximum element on the fly.
From example 1, we know that if i is even number, then arr[i] = arr[i / 2]. Else if i is odd number, then arr[i] = arr[i / 2] + arr[i / 2 + 1].

Solution

/**
 * @param {number} n
 * @return {number}
 */
var getMaximumGenerated = function(n) {
    if (n < 2) return n;
    let res = 0;
    
    const arr = Array(n+1).fill(0);
    [arr[0], arr[1]] = [0, 1];
    
    for (let i = 2; i < arr.length; i++) {
        arr[i] = arr[Math.floor(i/2)];
        if (i % 2 == 1) {
            arr[i] += arr[Math.floor(i/2) + 1];
        }
        res = Math.max(res, arr[i]);
    }
    
    return res;
};

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Explanation

We can use quick sort’s partition function to solve this problem in $O(N)$ time complexity because partition function return us the correct index, where all elements on the left side of the index are greather than this index number, all elements are on the right side of this index number are less than this index number. Note, we are sorting from largest to smallest.
First, we make a left pointer and right pointer that point to index 0 and the right most index. If the partition function return us p which equals to k-1, then we return nums[k-1]. Else if k-1 is greather than p, then left pointer moves to p+1, else if k-1 is smaller than p, then right pointer moves to p-1.
Inside the partition function, we first mark the first element as pivot. Left pointer moves one step forward, which is left+1, right poitner is the last index. While left pointer is smaller or equal to the right pointer, we start a while loop. If the left pointer number is smaller than the value of pivot and right pointer value is greather than pivot value, swap the left pointer and right pointer value. Then, if the left pointer value is greater or equal to the pivot value, then left pointer move right one step. If the right pointer value is smaller or equal than pivot, then right pointer value move left one step.
Out of the while loop, we swap pivot and the right pointer. Now, pivot is at its correct index. We finally return its index, which is the right pointer.

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let start = 0, end = nums.length - 1;

    while (start <= end) {
        let p = partition(nums, start, end);
        if (p == k-1) return nums[k-1];
        else if (p < k-1) start = p + 1;
        else end = p - 1;
    }

    return -1;
};

var partition = function(nums, start, end) {
    const pivot = nums[start];
    let left = start + 1, right = end;

    while (left <= right) {
        if (nums[left] < pivot && nums[right] > pivot) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
        }
        if (nums[left] >= pivot) left += 1;
        if (nums[right] <= pivot) right -= 1;
    }

    [nums[start], nums[right]] = [nums[right], nums[start]];

    return right;
}

Count Sorted Vowel Strings

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Explanation 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Explanation 3:

Input: n = 33
Output: 66045

Constraints:

1 <= n <= 50

Hint 1:

For each character, its possible values will depend on the value of its previous character, because it needs to be not smaller than it.

Hint 2:

Think backtracking. Build a recursive function count(n, last_character) that counts the number of valid strings of length n and whose first characters are not less than last_character.

Hint 3:

In this recursive function, iterate on the possible characters for the first character, which will be all the vowels not less than last_character, and for each possible value c, increase the answer by count(n-1, c).

Explanation

If we know all the string of len k, so the string of len k + 1 will be

add a before all string of len k
add e before the string of len k, which is starts with or after e
add i before the string of len k, which starts with or after i
add o before the string of len k, which starts with or after o
add u before the string of len k, which starts with or after u

Source: Java DP O(n) time Easy to understand

Solution

/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function(n) {
    let a = 1, e = 1, i = 1, o = 1, u = 1;

    while (n > 1) {
        a = a + e + i + o + u;
        e = e + i + o + u;
        i = i + o + u;
        o = o + u;
        u = u;
        n -= 1;
    }
    
    return a + e + i + o + u;
};

Max Number of K-Sum Pairs

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9

Hint 1:

The abstract problem asks to count the number of disjoint pairs with a given sum k.

Hint 2:

For each possible value x, it can be paired up with k - x.

Hint 3:

The number of such pairs equals to min(count(x), count(k-x)), unless that x = k / 2, where the number of such pairs will be floor(count(x) / 2).

Explanation 1

We can use two pointers to solve this problem. First, sort the array. Then we make one ponter i in the first index, another pointer j in the last index. If these two pointing numbers’ sum is equal to k, then we update the result, increase i and decrease j. Else if sum is smaller, then we increase i only. Else we decrease j only.

Solution 1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxOperations = function(nums, k) {
    nums.sort((a, b) => a - b);
    let i = 0, j = nums.length - 1;
    let res = 0;
    
    while (i < j) {
        const sum = nums[i] + nums[j];
        if (sum < k) {
            i += 1;
        } else if (sum > k) {
            j -= 1;
        } else {
            res += 1;
            i += 1;
            j -= 1;
        }
    }
    
    return res;
};

Explanation 2

The maximum number of pair will be len(array) / 2.
Create a hashmap to record the frequency of the numbers. Iterate the map, if the current element is different from the target k - curNum, then the max pair will be the minimum between the current number’s frequency and the target’s frequency. Later will will divide this result by 2. For example [2, 3], k = 5, 2’s target is 3 and 3’s target is 2. Else if current number and target are equal, then the pair will be current number’s frequency divide by 2. For example [3, 3, 3], k = 6, there is only one pair.

Solution 2

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxOperations = function(nums, k) {
    let hm = new Map();
    nums.forEach(num => {
        hm.set(num, (hm.get(num) || 0) + 1);
    });
    
    let a = 0, b = 0;
    
    for (const [key, val] of hm.entries()) {
        const target = k - key;
        if (target === k) {
            a += parseInt(hm.get(target) / 2);
        } else if (hm.has(target)) {
            b += Math.min(val, hm.get(target));
        }
    }
    
    return a + parseInt(b / 2);
};

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

Hint 1:

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

Hint 2:

If “aba” is a palindrome, is “xabax” a 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

If input string has length less than 2, simply return the string.
To find palindromic string, we can loop through the input string character and each character we make it as the middle of the palindromic.
Palindrom has 2 situations: First situation, abcba, here, c is the middle; Second situation, abba, here, bb is the middle.
In each iteration, we make the current character as the middle. We need to check if the current character is the same as its next character, if not the same, then we consider first situation; else, we consider the second situation.
We can define left and right pointing the middle characters. In the fist situation, left and right are c. In the second situation, left is first b, right is second b.
Then, we compare the middle’s left character and middle’s right character, in other words, str[left-1] comparing to str[right+1]. While they are the same, left = left-1 and right=right+1. After the while loop, left is pointing at the palindrome’s beginning index, and right is pointing at the palindrome’s last index. right-left+1 is its length. At the end of each iteration, we update the maximum length.
After we finish the loop using the last index of the string as middle, we can return the longest pralindrome substring using the left and its maximum length.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length <= 1) return s;
    let start = 0, maxLen = 0;
    let i = 0;
    let left = 0, right = 0;
    
    while (i < s.length) {
        left = i;
        right = i;
        while (right + 1 < s.length && s[right] === s[right+1]) right += 1;
        i = right + 1;
        
        while (left - 1 >= 0 && right+1 < s.length && s[left-1] === s[right+1]) {
            left -= 1;
            right += 1;
        }
        
        if (right - left + 1 > maxLen) {
            maxLen = right - left + 1;
            start = left;
        }
    }
    
    return s.substring(start, start+maxLen);
};

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Hint 1:

An interesting property about a valid parenthesis expression is that a sub-expression of a valid expression should also be a valid expression. (Not every sub-expression) e.g.

{ { } [ ] [ [ [ ] ] ] } is VALID expression
          [ [ [ ] ] ]    is VALID sub-expression
  { } [ ]                is VALID sub-expression

Can we exploit this recursive structure somehow?

Hint 2:

What if whenever we encounter a matching pair of parenthesis in the expression, we simply remove it from the expression? This would keep on shortening the expression. e.g.

{ { ( { } ) } }
      |_|

{ { (      ) } }
    |______|

{ {          } }
  |__________|

{                }
|________________|

VALID EXPRESSION!

Hint 3:

The stack data structure can come in handy here in representing this recursive structure of the problem. We can’t really process this from the inside out because we don’t have an idea about the overall structure. But, the stack can help us process this recursively i.e. from outside to inwards.

Explanation

Using stack.
Iterate the input string, if the current character is open symbol, we put its corresponding closed symbol to the stack. If the character is closed symbol, we compare the pop element of the stack with the current character. If they are not equal, we return false, or if the stack is empty, we return false. At the end If the stack is empty, we return true, otherwise, we return false.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let st = [];

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            st.push(')');
        } else if (s[i] === '{') {
            st.push('}');
        } else if (s[i] === '[') {
            st.push(']');
        } else {
            if (st[st.length-1] !== s[i]) return false;
            st.pop();
        }
    }
    
    return st.length === 0;
};

Find the Most Competitive Subsequence

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= nums.length

Hint 1:

In lexicographical order, the elements to the left have higher priority than those that come after. Can you think of a strategy that incrementally builds the answer from left to right?

Explanation

We can solve this problem using monotonic stack.
When we iterate to nums[i], While nums[i] is less than the top element of the stack, then we need to pop the stack. In this problem, we also need to maintain a size of k, so before we pop, we check the size of the stack after we pop is stack.length - 1, and there are nums.length - i elements we can push, so these two numbers’ sum at least be k then we can pop. Next, if stack size is less than k, we can push the current element.
At the end, the stack will be the result.

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var mostCompetitive = function(nums, k) {
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length > 0 && nums[i] < stack[stack.length-1] && stack.length - 1 + nums.length - i >= k) {
            stack.pop();
        }
        if (stack.length < k) {
            stack.push(nums[i]);
        }
    }
    
    return stack;
};

Week 4: January 22nd - January 28th

One Edit Distance

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t. Delete exactly one character from s to get t. Replace exactly one character of s with a different character to get t.

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

Constraints:

0 <= s.length <= 10^4
0 <= t.length <= 10^4
s and t consist of lower-case letters, upper-case letters and/or digits.

Explanation

First, we can check the difference of both strings’ length, if the difference is more than 1, then we can return false immediately.
Let’s assume that s is always shorter or the same length as t. If not, we can call isOneEditDistance(t, s) to inverse the string order.
Loop through every character of s and compare to t. If we find a different character, then we have 2 situations. One is both strings have the same length, then we can just return s[i+1:] == t[i+1:]. Another situation is s has one character less than t, then we can just return s[i:] == t[i+1:]. If we don’t find any different character after looping s, then t must be have one character append to the end of s in order to be true. For example s = abc and t = abcd, so we can return len(s) + 1 == len(t).

Solution

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        
        if (sLen > tLen) return isOneEditDistance(t, s);
        
        if (tLen - sLen > 1) return false;
        
        for (int i = 0; i < sLen; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (sLen == tLen) {
                    return s.substring(i+1).equals(t.substring(i+1));
                } else {
                    return s.substring(i).equals(t.substring(i+1));
                }
            }
        }
        
        return sLen + 1 == tLen;
    }
}

Determine if Two Strings Are Close

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.
- For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example, aacabb -> bbcbaa (all a’s turn into b’s, and all b’s turn into a’s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 10^5
word1 and word2 contain only lowercase English letters.

Hint 1:

Operation 1 allows you to freely reorder the string.

Hint 2:

Operation 2 allows you to freely reassign the letters’ frequencies.

Explanation

If word1 and word2 have different length, we can return false immediately.
If we only allow to perform operation 1, then word1 and word2 must have the same frequency of same characters.
Now considering operation 2, after we transform characters, the frequency value is still the same, the frequency position is just swapped. For example, aacabb, frequency for a, b, c are [3, 2, 1]; after transform, we have bbcbaa, frequency for a, b, c are [2, 3, 1]. So if word1 and word2 are formed by the same frequency values, then we can return true.

Solution

/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function(word1, word2) {
    if (word1.length != word2.length) return false;
    
    const hm1 = new Map();
    const hm2 = new Map();
    for (let i = 0; i < word1.length; i++) {
        hm1.set(word1[i], hm1.get(word1[i]) + 1 || 1);
        hm2.set(word2[i], hm2.get(word2[i]) + 1 || 1);
    }
    
    if (hm1.size != hm2.size) return false;
    for (const k of hm1.keys()) if (!hm2.has(k)) return false;
    for (const k of hm2.keys()) if (!hm1.has(k)) return false;
    
    const freqOfFreq = new Map();
    for (const [_, f] of hm1) {
        freqOfFreq.set(f, freqOfFreq.get(f) + 1 || 1);
    }
    for (const [_, f] of hm2) {
        if (!freqOfFreq.has(f) || freqOfFreq.get(f) == 0) return false;
        freqOfFreq.set(f, freqOfFreq.get(f) - 1);
    }
    
    return true;
};

Sort the Matrix Diagonally

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Example 2:

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Hint 1:

Use a data structure to store all values of each diagonal.

Hint 2:

How to index the data structure with the id of the diagonal?

Hint 3:

All cells in the same diagonal (i,j) have the same difference so we can get the diagonal of a cell using the difference i-j.

Explanation

Values on the same diagonal have the same pattern diff = r - c, in other word, all values that are on the same diagonal have the same difference when their row index minus column index.
We can use a hashmap to store the key as diff = r - c, value will be a priority queue that holds all the values that have the same diff.

Solution

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(mat) {
    const hm = new Map();
    
    for (let r = 0; r < mat.length; r++) {
        for (let c = 0; c < mat[0].length; c++) {
            const diff = r - c;
            hm.set(diff, [...(hm.get(diff) || []), mat[r][c]]);
        }
    }
    
    for (const [k, v] of hm) {
        v.sort((a, b) => a - b).reverse();
    }
    
    for (let r = 0; r < mat.length; r++) {
        for (let c = 0; c < mat[0].length; c++) {
            const diff = r - c;
            mat[r][c] = hm.get(diff).pop();
        }
    }
    
    return mat;
};

Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won’t exceed 10^4.

Explanation

We can use divide and conquer method to solve this problem. For example, if we have 6 ListNode, then we can solve ListNode1 with ListNode4, ListNode2 with ListNode5, ListNode3 with ListNode6.
Then, we have 3 ListNode need to sort. We then sort ListNode1 with ListNode3.
Then, we have 2 ListNode need to sort. We then sort ListNode1 with ListNode2.
Finally, we return the result of ListNode1.
Since there are $k$ ListNode in the array, similarly to merge sort, we divide $k$ ListNode takes $\log(k)$ time, and there are total of $kn$ nodes to compare, so the total time complexity is $kn\log(k)$. The space complexity is $log(k)$ because of the recursive stack.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length === 0) return null;

    let n = lists.length;
    while (n > 1) {
        const mid = Math.floor((n + 1) / 2);
        for (let i = 0; i < Math.floor(n / 2); i++) {
            lists[i] = mergeTwoLists(lists[i], lists[n-1-i]);
        }
        n = mid;
    }
    
    return lists[0];
};

var mergeTwoLists = function(lstA, lstB) {
    if (lstA === null) return lstB;
    if (lstB === null) return lstA;
    
    if (lstA.val < lstB.val) {
        lstA.next = mergeTwoLists(lstA.next, lstB);
        return lstA;
    } else {
        lstB.next = mergeTwoLists(lstA, lstB.next);
        return lstB;
    }
}

Check If All 1’s Are at Least Length K Places Away

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true

Constraints:

1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i] is 0 or 1

Hint 1:

Each time you find a number 1, check whether or not it is K or more places away from the next one. If it’s not, return false.

Explanation 1

We can solve this problem in one-pass by counting the number of zeros in between the “neighbor” 1s. When we iterate to the number equals 1, we can reset the counter.
To bypass the first 1 in the array, we can initalize the counter equals k.

Solution 1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function(nums, k) {
    let count = k;

    for (const num of nums) {
        if (num === 0) {
            count += 1;
        } else {
            if (count < k) return false;
            count = 0;
        }
    }
    
    return true;
};

Explanation 2

We can also two pointer approach, we use a variable start to mark the previous 1’s index, then when we iterate to a number that is equals to 1, we can use the current index to subtract start to see if the difference is less than or equals to k, then return false, else reset start to the current index.

Solution 2

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function(nums, k) {
    let start = nums.indexOf(1);

    let i = start + 1;
    while (i < nums.length) {
        if (nums[i] === 1) {
            if (i - start <= k) return false;
            start = i;
        }
        i += 1;
    }

    return true;
};

Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

Hint 1:

Consider the grid as a graph, where adjacent cells have an edge with cost of the difference between the cells.

Hint 2:

If you are given threshold k, check if it is possible to go from (0, 0) to (n-1, m-1) using only edges of ≤ k cost.

Hint 3:

Binary search the k value.

Explanation 1

We can solve this problem using Binary Search and BFS. We binary search for a potential result. Based on the constraints 1 <= heights[i][j] <= 10^6 the minimum result left is 0, the maximum result right is 10^6. So while left < right, if within the limited effort mid, we can reach the bottom right from top left, then we can update left = mid + 1, else we can update right = mid.
Now given the limit effort, we can use BFS to check we can reach the bottom right. To prevent go back to the same position, we also need a visited array.
Time complexity: O(log(MAX_HEIGHT) * m * n), where MAX_HEIGHT = 10^6. Space complexity is O(m * n).

Solution 1

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function(heights) {
    let left = 0, right = 1e6;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (canReach(heights, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

var canReach = function(heights, limit) {
    const dir = [0, 1, 0, -1, 0];
    const row = heights.length, col = heights[0].length;
    const queue = [];
    const visited = Array(row).fill([]).map(r => Array(col).fill(false));
    
    queue.push([0, 0]);
    visited[0][0] = true;
    
    while (queue.length > 0) {
        const cur = queue.shift();
        const r = cur[0], c = cur[1];
        if (r == row - 1 && c == col - 1) return true;
        
        for (let i = 0; i < 4; i++) {
            const nr = r + dir[i];
            const nc = c + dir[i + 1];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col && !visited[nr][nc]) {
                const nEffort = Math.abs(heights[nr][nc] - heights[r][c]);
                if (nEffort <= limit) {
                    queue.push([nr, nc]);
                    visited[nr][nc] = true;
                }
            }
        }
    }
    
    return false;
}

Explanation 2

We can also use Dijkstra and BFS with PriorityQueue to solve this problem. We initialize a 2d array efforts[][] to hold every cell’s minimum effort. We know that the effort to reach the top left is 0, for other cells, we can iniitalize the effort to reach them is INT_MAX. First, we calculate the effort to reach the current top left cell’s neighbor cells, and push these cells with its effort into a PriorityQueue. This priority queue will hold integer array as value, this integer array will have length 3, and each index represents [effort, row, col]. The PriorityQueue will sort as the minimum effort on the top of the queue. So each time we poll from the queue, we will always get the cell using the minimum effort to reach. After we poll [effort, row, col], we check if this poll cell is the bottom right cell, if it is, then we can return its effort.
Time complexity: O(E log V), where E is number of edges E = 4*M*N, V is number of veritices V = M*N, so time complexity equals (ElogV) = O(M*N log M*N), where M is the number of rows and N is the number of columns in the matrix. Space complexity is O(M * N).

Solution 2

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function(heights) {
    const dir = [0, 1, 0, -1, 0];
    const row = heights.length, col = heights[0].length;
    
    const efforts = Array(row).fill([]).map(r => Array(col).fill(Infinity));
    efforts[0][0] = 0;

    const pq = new PriorityQueue((a, b) => {
        if (a[0] < b[0]) return -1;
        else if (a[0] > b[0]) return 1;
        return 0;
    });
    pq.push([0, 0, 0]);

    while (pq.arr.length > 0) {
        const cur = pq.shift();
        const [curEffort, r, c] = cur;
        if (r === row - 1 && c === col - 1) return curEffort;
        
        for (let i = 0; i < 4; i++) {
            const nr = r + dir[i];
            const nc = c + dir[i + 1];
            if (nr >= 0 && nr < row && nc >= 0 && nc < col) {
                const nEffort = Math.max(curEffort, Math.abs(heights[nr][nc] - heights[r][c]));
                if (nEffort < efforts[nr][nc]) {
                    efforts[nr][nc] = nEffort;
                    pq.push([nEffort, nr, nc]);
                }
            }
        }   
    }
    
    return Infinity;
};

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

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

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

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

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

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

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

    return minNode;
};

Concatenation of Consecutive Binary Numbers

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1. 

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

Constraints:

1 <= n <= 10^5

Hint 1:

Express the nth number value in a recursion formula and think about how we can do a fast evaluation.

Explanation

When we append a new number, we shift the current result res by len bit to the left where len is the binary representation of the new number, after shifting, we add the current number to res to get the new result.
To get the length of the new number’s binary representation string, in Java, we can use Integer.toBinaryString(num).length(). In general, if n is power of 2, we increase len by 1. For example,
1
2
3
4
5
6
7
8
n = 1, len = 1 n = 2, len = 2 n = 3, len = 2 n = 4, len = 3 n = 5, len = 3 n = 6, len = 3 n = 7, len = 3 n = 8, len = 4

We can initialize len = 0, when (n & (n-1)) == 0, we increase len by 1.

Solution

/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function(n) {
    const MOD = 10**9 + 7;
    let res = 0, len = 0;

    for (let i = 1; i <= n; i++) {
        if ((i & (i-1)) === 0) len += 1;
        res = (res * (1 << len) + i) % MOD;
    }

    return res;
};

Smallest String With A Given Numeric Value

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:

Input: n = 5, k = 73
Output: "aaszz"

Constraints:

1 <= n <= 10^5
n <= k <= 26 * n

Hint 1:

Think greedily.

Hint 2:

If you build the string from the end to the beginning, it will always be optimal to put the highest possible character at the current index.

Explanation

First creating a character array with length n and fill with all a, so now the k becomes k - n. While k is greater than 0, then we start updating from the last character, we wanna increase the last character by min(25, k), then update k = k - min(25, k), and move to update the second last character in the next iteration.

Solution

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getSmallestString = function(n, k) {
    const arr = Array(n).fill('a');
    k -= n;
    let idx = arr.length - 1;

    while (k > 0) {
        const temp = Math.min(25, k);
        arr[idx] = String.fromCharCode(arr[idx].charCodeAt(0) + temp);
        k -= temp;
        idx -= 1;
    }

    return arr.join('');
};

Week 5: January 29th - January 31st

Number Of Corner Rectangles

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

Note:

The number of rows and columns of grid will each be in the range [1, 200].
Each grid[i][j] will be either 0 or 1.
The number of 1s in the grid will be at most 6000.

Hint 1:

For each pair of 1s in the new row (say at new_row[i] and new_row[j]), we could create more rectangles where that pair forms the base. The number of new rectangles is the number of times some previous row had row[i] = row[j] = 1.

Explanation

If there are two 1s in the same row, in other words, colStart == 1 && colEnd == 1, that is a valid base. Then fix the colStart and colEnd, we loop every row, count for the number of valid base numBase. If there are 2 valid base, then there is 1 rectangle; if there are 3 valid base, then there are 1 + 2 rectangles; if there are 4 valid base, then there are 1 + 2 + 3 rectangles.

Solution

class Solution {
    public int countCornerRectangles(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int res = 0;
        
        for (int cStart = 0; cStart < col; cStart++) {
            for (int cEnd = cStart + 1; cEnd < col; cEnd++) {
                int numBase = 0;
                for (int r = 0; r < row; r++) {
                    if (grid[r][cStart] == 1 && grid[r][cEnd] == 1) numBase += 1;
                }
                res += numBase * (numBase - 1) / 2;
            }
        }
        
        return res;
    }
}

Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.

Example 2:

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
          1 is at the top, so it comes first.
          5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.

Example 3:

Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints:

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

Explanation

We can create a list and store all nodes with their corresponding row and column, in other words, lst[i] = [row, col, nodeVal]. Then sort this list base on smallest column first, if same column, then sort by their row and smaller row first, otherwise same column and row, then smallest number first.
Next, iterate the list, push the current element’s nodeVal into a sublist, if the current element’s column is different from the next element’s column, then we push this sublist into the result list.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function(root) {
    const lst = []; // [[row, col, root.val]]
    helper(root, lst, 0, 0);

    lst.sort((a, b) => {
        if (a[1] === b[1]) {
            if (a[0] === b[0]) {
                return a[2] - b[2];
            } else {
                return a[0] - b[0];
            }
        } else {
            return a[1] - b[1];
        }
    });
    
    const res = [];
    let sub = [];
    for (let i = 0; i < lst.length; i++) {
        sub.push(lst[i][2]);
        if (i === lst.length - 1 || lst[i][1] !== lst[i+1][1]) {
            res.push(sub);
            sub = [];
        }
    }
    
    return res;
};

var helper = function(root, lst, row, col) {
    if (root === null) return;
    lst.push([row, col, root.val]);
    helper(root.left, lst, row + 1, col - 1);
    helper(root.right, lst, row + 1, col + 1);
}

Minimize Deviation in Array

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].
If the element is odd, multiply it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= 10^9

Hint 1:

Assume you start with the minimum possible value for each number so you can only multiply a number by 2 till it reaches its maximum possible value.

Hint 2:

If there is a better solution than the current one, then it must have either its maximum value less than the current maximum value, or the minimum value larger than the current minimum value.

Hint 3:

Since that we only increase numbers (multiply them by 2), we cannot decrease the current maximum value, so we must multiply the current minimum number by 2.

Explanation

The deviation is equal to the maximum number minus the minimum number.
Even number never increase.
We can double all odd numbers, so they become even numbers. Then we only need to care about the division operation. Now, we only need to decrease the largest number when it’s even.
Double odd numbers and put all numbers into a max heap. Track the smallest number. Track the minimum difference between the top of the heap and the smallest number. While the top of the heap is even, remove it, divide, and put back to the heap.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeviation = function(nums) {
    let res = Number.MAX_SAFE_INTEGER;
    
    const pq = new PriorityQueue((a, b) => b - a);
    let min = Number.MAX_SAFE_INTEGER;

    for (const num of nums) {
        if (num % 2 === 0) {
            pq.push(num);
            min = Math.min(min, num);
        } else {
            pq.push(num * 2);
            min = Math.min(min, num * 2);
        }
    }
        
    while (pq.peek() % 2 === 0) {
        const top = pq.peek();
        pq.shift();
        res = Math.min(res, top - min);
        pq.push(top / 2);
        min = Math.min(min, top / 2);
    }
    
    return Math.min(res, pq.peek() - min);
};


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

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

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

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

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

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

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

    return minNode;
};

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

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

1 <= nums.length <= 100

0 <= nums[i] <= 100

Explanation

First, we can list out all the permuatations. For example, if input array is [1, 2, 3]. Then we have:
1
2
3
4
5
6
7
8
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
If the input array elements are in decreasing order, we can just return the reverse array.
If the input array elements are not in decreasing order, for example, the input array is [1, 2, 7, 4, 3, 1], then its next permutation is [1, 3, 1, 2, 4, 7].
We can look from the end elment to the beginning of the input array, we find out elements are increasing until we hit the $2$. Then, we still look from the end element to the beginning, we find out $3$ is larger than $2$. Then, we swap these two elements. Finally, we reverse all the elements starts from the index that is equal to the original input $2$’s index plus one.
1
2
3
[1, 2, 7, 4, 3, 1] //swap 2 and 3 [1, 3, 7, 4, 2, 1] //reverse all elements after 3 [1, 3, 1, 2, 4, 7] //result

Solution

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    if (nums.length < 2) return;
    const n = nums.length;
    let a = 0, b = 0;
    
    for (let i = n - 2; i >= 0; i--) {
        if (nums[i] < nums[i+1]) {
            a = i;
            break;
        }
    }
    
    for (let i = n - 1; i >= 0; i--) {
        if (nums[i] > nums[a]) {
            b = i;
            break;
        }
    }
    
    if (a === 0 && b === 0) {
        nums.reverse();
        return;
    }
    
    [nums[a], nums[b]] = [nums[b], nums[a]];
    reverse(nums, a+1, n-1);
};

var reverse = function(nums, left, right) {
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left += 1;
        right -= 1;
    }
}