Starting August, LeetCode will also include premium questions in August LeetCoding Challenge.

Week 1: August 1st - August 7th

Logger Rate Limiter

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true;

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

Explanation

If we use brute force solution, we can create a hashmap, key is the message string, value is the timestamp. For each shouldPrintMessage method call, we check if the message argument is in the hashmap or not. If not, then that means this message didn’t appear before, so we return true and put this message and timestamp to the hashmap. Else, we compare the hashmap.get(message) with timestamp to see if this timestamp is in the range or not. This will have space complexity $O(n)$.
We can reduce space complexity to $O(1)$ by creating two hashmaps. The first hashmap is used to store the timestamp within last 0 to 10 seconds, the second hashmap is the OLD last 0 to 10 seconds hashmap. We also need an extra variable t which represents the initial time that starts checking the last 10 seconds hashmap.
When the message comes in, we check if this message is in the previous 0 to 10 seoncd hashmap, if yes, then we return false.
Next, we also need to check if this message is in the OLD hashmap, if yes, then we compare old[message] + 10 and timestamp, if timestamp is smaller, then return false. The reason is if we start checking the last 10 seconds from t = 11, in other words, now the last 10 seconds is from 11 - 21 second, there was a message at 9 second in the OLD hashmap, now the same message comes in at 15 second, we still need to return false because 9 + 10 > 15.
Next, the current message is not in both hashmap, then we add it to the pre0To10 hashmap.
When do we update the OLD hashmap? That’s why we need to variable t. If the incoming message timestamp >= t + 10, then we update the old hashmap be the current pre0To10 hashmap, and udpate t be the current incoming timestamp.

Solution

class Logger {
    int t;
    Map<String, Integer> pre0To10;
    Map<String, Integer> old;

    /** Initialize your data structure here. */
    public Logger() {
        this.t = 0;
        this.pre0To10 = new HashMap<>();
        this.old = new HashMap<>();
    }

    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        if (timestamp >= t + 10) {
            old = new HashMap<>(pre0To10);
            pre0To10.clear();
            t = timestamp;
        }
        if (pre0To10.containsKey(message)) return false;
        if (old.containsKey(message) && old.get(message) + 10 > timestamp) return false;
        pre0To10.put(message, timestamp);
        return true;
    }
}

/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */

Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital, like “Google”.

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

Explanation

If we know the first two characters, then we can determine the result base on the rest of characters.
If both the first two characters are upper case, then the rest characters should all be upper case. For example, AB(XYZ), XYZ must all be upper case in order to be True.
Else both the first two characters are not upper case, then from the second character and beyond, the rest characters must all be lower case. For example, A(bxyz), a(Bxyz), a(bxyz).

Solution

func detectCapitalUse(word string) bool {
    if len(word) == 1 { return true }
    isFirstUpper := unicode.IsUpper(rune(word[0]))
    isSecondUpper := unicode.IsUpper(rune(word[1]))

    if isFirstUpper && isSecondUpper {
        for i := 2; i < len(word); i++ {
            if unicode.IsLower(rune(word[i])) { return false }
        }
    } else {
        for i := 1; i < len(word); i++ {
            if unicode.IsUpper(rune(word[i])) { return false }
        }
    }

    return true
}

Design HashSet

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

To be specific, your design should include these functions:

add(value): Insert a value into the HashSet.
contains(value): Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false (not found)
hashSet.add(2);
hashSet.contains(2);    // returns true
hashSet.remove(2);
hashSet.contains(2);    // returns false (already removed)

Note:

All values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashSet library.

Explanation

We can solve this problem and collision using seperate chaining. First, we create an array of list List<Integer>[] buckets, in other word, adjacency list, and also initialize the size of this array is 15000 which is 150% of the total keys since the range of the number of operation is [1, 10000] so that we can avoid most the collision.
We also need to define our hash function, which can simpliy be key % numBuckets.
In the add method, first calculate the hash index idx, so that we know this input key is belonged to which bucket, then put the input key into the corresponding bucket bucket[idx], but before we put, we need to make sure the list buckets[idx] doesn’t have the input key.
In the remove method, first calculate the hash index idx, then make sure the list bucketx[idx] has the key, then we remove the key.
In the contains method, first calculate the hash index idx, then check if the corresponding bucket bucket[idx] doesn’t have the key.

Solution

type MyHashSet struct {
    numBuckets int
    buckets [][]int
}


/** Initialize your data structure here. */
func Constructor() MyHashSet {
    return MyHashSet{ numBuckets: 15000, buckets: make([][]int, 15000) }
}


func (this *MyHashSet) Add(key int)  {
    if this.Contains(key) { return }
    idx := this.hash(key)
    this.buckets[idx] = append(this.buckets[idx], key)
}


func (this *MyHashSet) Remove(key int)  {
    if !this.Contains(key) { return }
    idx := this.hash(key)
    this.buckets[idx] = remove(this.buckets[idx], indexOf(this.buckets[idx], key))
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    idx := this.hash(key)
    return indexOf(this.buckets[idx], key) != -1
}


func (this *MyHashSet) hash(key int) int {
    return key % this.numBuckets
}

func indexOf(arr []int, key int) int {
    for i, ele := range arr {
        if key == ele {
            return i
        }
    }
    return -1
}

func remove(arr []int, idx int) []int {
    return append(arr[:idx], arr[idx+1:]...)
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Constraints:

s consists only of printable ASCII characters.

Explanation

We can use a left and right poitner pointing to the beginning and the end of the string respectivly, and compare their character. If the character is pointing at is not a letter or digit, then we skip it; else if the character is not match, then we return false; else if they are matched, then we move left pointer to the right, right pointer to the left. Repeat it until left pointer is equal or greater than right pointer.

Solution

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        for left < right && !isalnum(s[left]) { left += 1 }
        for left < right && !isalnum(s[right]) { right -= 1 }
        if unicode.ToUpper(rune(s[left])) != unicode.ToUpper(rune(s[right])) {
            return false
        }
        left += 1
        right -= 1
    }

    return true
}

func isalnum(c byte) bool {
    return unicode.IsLetter(rune(c)) || unicode.IsDigit(rune(c))
}

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

Explanation

First, zero is not the power of any number. We can write out some numbers that are power of 4 in their binary representation.
1
2
3
4
1 1 4 100 16 10000 64 1000000
We notice that they all starts from 1 and only have one 1 in the most significant bit, and the next number have two more zeros at the end. We can use the technique of finding powerOf2 because all numbers that are powerOf2 only have the most significant bit is 1. If (num & (num-1)) == 0, then num is powerOf2.
If we always shift two bits to the right, then if num is powerOf4, it must sometimes equals to 1.
Any negative numbers will return false.

Solution

func isPowerOfFour(num int) bool {
    if (num & (num-1)) != 0 { return false }

    for num > 0 {
        if num == 1 { return true }
        num >>= 2
    }

    return false
}

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:

You may assume that all words are consist of lowercase letters a-z.

Hint 1:

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Explanation

Similar to 208. Implement Trie (Prefix Tree), we need two properties: WordDictionary[26] children and boolean isEndOfWord.
For the addWord method, it’s the same as how the Trie add word.
For the search method, if the word doesn’t have any . character, then it’s the same as how the Trie search word. If word’s current character is ., in other wrod, word[i] = '.', then we need to check all the children under the current Trie pointer, and recursively call each child’s search method with the updated word word[i+1:].

Solution

type WordDictionary struct {
    children []*WordDictionary
    isEndOfWord bool
}


/** Initialize your data structure here. */
func Constructor() WordDictionary {
    return WordDictionary{children: make([]*WordDictionary, 26), isEndOfWord: false}
}


/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string)  {
    cur := this
    for _, ch := range word {
        if cur.children[ch - 'a'] == nil {
            cur.children[ch - 'a'] = &WordDictionary{make([]*WordDictionary, 26), false}
        }
        cur = cur.children[ch - 'a']
    }
    cur.isEndOfWord = true
}


/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    cur := this
    for i, ch := range word {
        if ch == '.' {
            for _, wd := range cur.children {
                if wd != nil && wd.Search(word[i+1:]) { return true }
            }
            return false
        }
        if cur.children[ch - 'a'] == nil { return false }
        cur = cur.children[ch - 'a']
    }
    return cur != nil && cur.isEndOfWord
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */

Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Explanation

Since in the array, all elements are positive and their value are no more than n. We loop the array, for each iteration, we think the current value as an index which is idx = curVal-1. Then we make that index’s value be negative, in other words, arr[idx] *= -1. So, when we iterate the array, before we make arr[idx] be negative, if it’s already negative, that means there are same value as idx before, so we add the before’s value which is curVal to the result list.

Solution

func findDuplicates(nums []int) []int {
    res := make([]int, 0)
    for _, num := range nums {
        idx := abs(num) - 1
        if nums[idx] < 0 {
            res = append(res, abs(num))
        } else {
            nums[idx] *= -1
        }
    }

    return res
}

func abs(n int) int {
    if n < 0 {
        return -n
    } else {
        return n
    }
}

Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.

Explanation

We can create a hashmap, key will be the column number, value will be a list of pair< row number, node value>. This list will later be sorted by smaller row number to large row number, if same row number, then sort by small node value to large node value. We can use pre-order traversal to generate this map. When building this map, we also keep track of the minimum column number, and maximum column number.
Next, loop from the minimum column to maximum column. Each iteration, we can get a list of pair<row number, node value> and sort this list. Now, we can loop through this list’s node value and put into a sub list, then put this sublist to the result list.

Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalTraversal(root *TreeNode) [][]int {
    res := make([][]int, 0)
    if root == nil { return res }
    hm := make(map[int][][]int)
    minCol, maxCol := 0, 0
    helper(root, hm, &minCol, &maxCol, 0, 0)

    for c := minCol; c <= maxCol; c++ {
        cur := hm[c]
        sort.Slice(cur, func(i, j int) bool {
            if cur[i][0] == cur[j][0] {
                return cur[i][1] < cur[j][1]
            } else {
                return cur[i][0] < cur[j][0]
            }
        })

        sub := make([]int, 0)
        for _, a := range cur {
            sub = append(sub, a[1])
        }
        res = append(res, sub)
    }

    return res
}

func helper(root *TreeNode, hm map[int][][]int, minCol *int, maxCol *int, row int, col int) {
    if root == nil { return }
    if _, ok := hm[col]; !ok {
        hm[col] = make([][]int, 0)
    }
    hm[col] = append(hm[col], []int{row, root.Val})
    *minCol = min(*minCol, col)
    *maxCol = max(*maxCol, col)
    helper(root.Left, hm, minCol, maxCol, row+1, col-1)
    helper(root.Right, hm, minCol, maxCol, row+1, col+1)
}

func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func max(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

Week 2: August 8th - August 14th

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

Explanation

Since this is the binary tree, we have 3 cases.
First case is if target is less than root.val and root.left is not null, then we recursively call the main function with root.left and target and it returns the closest value l from the tree root.left. Then we compare abs(l - target) and abs(root.val - target) and return the smalleset difference’s tree value.
Second case is if target is greater than root.val and root.right is not null. This is similar to the above case.
Third case is target is equal to root.val, or target is less than root.val but root.left is null, or target is greater than root.val but root.right is null, then we just return root.val.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        if (root.val < target && root.right != null) {
            int r = closestValue(root.right, target);
            if (Math.abs(root.val - target) < Math.abs(r - target)) {
                return root.val;
            } else {
                return r;
            }
        } else if (root.val > target && root.left != null) {
            int l = closestValue(root.left, target);
            if (Math.abs(root.val - target) < Math.abs(l - target)) {
                return root.val;
            } else {
                return l;
            }
        } else {
            return root.val;
        }
    }
}

Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Explanation 1

We have two options. One is include the root node’s value as the sum and call a helper function with root node as a parameter, the other is don’t include the root node’s value and call the main function with the left child and right child respectively.

Solution 1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, sum int) int {
    if root == nil { return 0 }
    return helper(root, sum, 0) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

func helper(root *TreeNode, targetSum, curSum int) int {
    if root == nil { return 0 }
    res := 0

    curSum += root.Val
    if curSum == targetSum { res += 1 }

    res += helper(root.Left, targetSum, curSum)
    res += helper(root.Right, targetSum, curSum)
    return res
}

Explanation 2

Similar to 560. Subarray Sum Equals K, we can create a hashmap to store the accumulate sum as the key, and the count of this sum as the value. Initially, the hashmap will have key as 0, value as 1. We will update the result as res += hm[curSum - targetSum]. For example, the tree is like below, and the target sum is 3.
1
2
3
4
5
1 / 2 / 1
When we on the first node 1, we have curSum is 1, we increase res by 0 ( hm[1 - 3] = 0), then we update the hashmap and have hm[1] = 1. Next, we are on the node 2, we have curSum is 3, we increase res by 1 (hm[3-3]=1), then we update the hashmap and have hm[3] = 1. Next, we are on the second node 1, we have curSum = 4, we increase res by 1 (hm[4-3]=1) and now res = 2, then we update the hashmap and have hm[4] = 1.
At the end of each recursion call, we need to backtrack the hashmap key and value since we don’t want to carry these keys and values to the right child.

Solution 2

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, sum int) int {
    if root == nil { return 0 }
    hm := make(map[int]int)
    hm[0] = 1
    return helper(root, sum, 0, hm)
}

func helper(root *TreeNode, targetSum, curSum int, hm map[int]int) int {
    if root == nil { return 0 }
    res := 0

    curSum += root.Val
    res += hm[curSum-targetSum]

    hm[curSum] += 1
    res += helper(root.Left, targetSum, curSum, hm)
    res += helper(root.Right, targetSum, curSum, hm)

    if cnt, ok := hm[curSum]; ok {
        if cnt == 1 {
            delete(hm, curSum)
        } else {
            hm[curSum] -= 1
        }
    }

    return res
}

Rotting Oranges

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

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

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

Solution

func orangesRotting(grid [][]int) int {
    res := 0
    fresh := 0
    queue := make([][]int, 0)
    row, col := len(grid), len(grid[0])

    for r := 0; r < row; r++ {
        for c := 0; c < col; c++ {
            if grid[r][c] == 1 {
                fresh += 1
            } else if grid[r][c] == 2 {
                queue = append(queue, []int{r, c})
            }
        }
    }

    dr := []int{-1, 0, 1, 0}
    dc := []int{0, 1, 0, -1}

    for len(queue) > 0 {
        for i := len(queue)-1; i >= 0; i-- {
            cur := queue[0]
            queue = queue[1:]
            r, c := cur[0], cur[1]
            for j := 0; j < 4; j++ {
                adjRow, adjCol := r+dr[j], c+dc[j]
                if adjRow >= 0 && adjRow < row && adjCol >= 0 && adjCol < col {
                    if grid[adjRow][adjCol] == 1 {
                        grid[adjRow][adjCol] = 2
                        fresh -= 1
                        queue = append(queue, []int{adjRow, adjCol})
                    }
                }
            }
        }
        if len(queue) > 0 { res += 1 }
    }

    if fresh == 0 {
        return res
    } else {
        return -1
    }
}

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28
    ...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

Constraints:

1 <= s.length <= 7
s consists only of uppercase English letters.
s is between “A” and “FXSHRXW”.

Explanation

This is a problem that asks us to convert a twenty-six hex to a decimal number.
We can start from the most right, ‘A’ is 1, so we can do ‘A’ - ‘A’ + 1 = 1, then multiple by 26 to the power of 0; ‘B’ is 2, we can do ‘B’ - ‘A’ + 1 = 2, multiple by 26 to the power of 0. Similarlly, the second right number multiple by 26’s to the power of 1.

Solution

func titleToNumber(s string) int {
    res := 0
    for _, ch := range s {
        d := int(ch - 'A' + 1)
        res = res * 26 + d
    }
    return res
}

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
             received 3, 0, 6, 1, 5 citations respectively.
             Since the researcher has 3 papers with at least 3 citations each and the remaining
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint 1:

An easy approach is to sort the array first.

Hint 2:

What are the possible values of h-index?

Hint 3:

A faster approach is to use extra space.

Explanation

First, sort the input array.
Start from the last index to index 0, initialize count = 1. If arr[i] >= count, then update res = count. Each iteration increase count by 1. Repeat the above step, if arr[i] < count, we can break out the loop and return the res.

Solution

func hIndex(citations []int) int {
    sort.Ints(citations)
    res := 0

    for i := len(citations) - 1; i >= 0; i-- {
        count := len(citations) - i
        if citations[i] >= count {
            res = count
        } else {
            break
        }
    }

    return res
}

Pascal’s Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Explanation

If rowIndex = n, then the result will have length n + 1. Initially, we create the result list that has length n + 1 and set all elements to be 1.
If curRowIndex = 2, then initially we have res = [1, 1, 1]. Then we start updating index from curRowIndex - 1 which is 1 to be res[1] = res[1] + res[0] = 2. Now, we get res = [1, 2, 1].
If rowIndex = 3 and we already solve rowIndex = 2 using the above method, and we have res = [1, 2, 1, 1]. For i starting from curRowInex - 1 down to 1, we update res[i] = res[i] + res[i-1], then we have when i = 2, res = [1, 2, 3, 1]; when i = 1, res = [1, 3, 3, 1].

Solution

func getRow(rowIndex int) []int {
    res := make([]int, rowIndex+1)
    for i := range res { res[i] = 1 }

    for curRowIndex := 1; curRowIndex <= rowIndex; curRowIndex++ {
        for i := curRowIndex - 1; i >= 1; i-- {
            res[i] = res[i] + res[i-1]
        }
    }

    return res
}

Iterator for Combination

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It’s guaranteed that all calls of the function next are valid.

Hint 1:

Generate all combinations as a preprocessing.

Hint 2:

Use bit masking to generate all the combinations.

Explanation:

Similar to 77. Combinations, first in the constructor method, we need to create a list of the combinations in the queue.
In the next method, we poll the first string from the queue.
In the hasNext method, we check if the queue is empty or not.

Solution

type CombinationIterator struct {
    queue []string
}


func Constructor(characters string, combinationLength int) CombinationIterator {
    queue := make([]string, 0)
    getCombination(characters, combinationLength, 0, "", &queue)
    return CombinationIterator{ queue }
}


func (this *CombinationIterator) Next() string {
    res := this.queue[0]
    this.queue = this.queue[1:]
    return res
}


func (this *CombinationIterator) HasNext() bool {
    return len(this.queue) > 0
}


func getCombination(characters string, combinationLength int, start int, cur string, queue *[]string) {
    if 0 == combinationLength {
        *queue = append(*queue, cur)
        return
    }

    for i := start; i <= len(characters) - combinationLength; i++ {
        cur = cur + string(characters[i])
        getCombination(characters, combinationLength-1, i+1, cur, queue)
        cur = cur[:len(cur)-1]
    }
}


/**
 * Your CombinationIterator object will be instantiated and called as such:
 * obj := Constructor(characters, combinationLength);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:

Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Explanation

Palindrome normally has even number of characters, like cbaabc. Or has one odd number of character in the middle, like cbaxabc.
We can use a hashmap to get all characters’ frequency. Then, we loop through all hashmap’s frequency. If the current frequency is even, we just add the frequency into result. Else if the current frequency is odd, then we add its frequency and subtract 1. (if there are 3 as, then we add 3-1=2 as into the result). Also, we mark true that there’s at least one odd character.
At the end, if no odd number of character, then we return res. Else if there’s at least 1 odd number of character, we return res + 1 because one character can be added into the middle.

Solution

func longestPalindrome(s string) int {
    hm := make(map[rune]int)
    for _, ch := range s {
        hm[ch] += 1
    }

    res := 0
    hasOdd := false
    for _, freq := range hm {
        res += freq
        if freq % 2 == 1 {
            res -= 1
            hasOdd = true
        }
    }

    if hasOdd { return res + 1 }
    return res
}

Week 3: August 15th - August 21st

Find Permutation

By now, you are given a secret signature consisting of character ‘D’ and ‘I’. ‘D’ represents a decreasing relationship between two numbers, ‘I’ represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature “DI” can be constructed by array [2,1,3] or [3,1,2], but won’t be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can’t represent the “DI” secret signature.

On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, … n] could refer to the given secret signature in the input.

Example 1:

Input: "I"
Output: [1,2]
Explanation: [1,2] is the only legal initial spectial string can construct secret signature "I", where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can construct the secret signature "DI",
but since we want to find the one with the smallest lexicographical permutation, you need to output [2,1,3]

Note:

The input string will only contain the character ‘D’ and ‘I’.
The length of input string is a positive integer and will not exceed 10,000

Explanation

This problem can be solved by greedy or brute force.
For example, if the input string is “DDIIDI”, then the result changes from “1 2 3 4 5 6 7” to “3 2 1 4 6 5 7”.

D D I I D I

1 2 3 4 5 6 7

3 2 1 4 6 5 7
From the above example, we notice that we only need to reverse D’s surrounding numbers. We record D’s starting index j and the count cnt of continuous D, then reverse res[j, j+cnt] inclusive.

Solution

class Solution {
    void reverse(int[] arr, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public int[] findPermutation(String s) {
        int[] res = new int[s.length() + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') continue;
            int j = i;
            while (i < s.length() && s.charAt(i) == 'D') {
                i += 1;
            }
            reverse(res, j, i);
            i -= 1;
        }

        return res;
    }
}

Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Explanation

First, we need to sort the intervals[][] by their start. When we have less than two intervals, we can return 0 as the result.
Next, we need to find out which intervals are overlap. The way to find overlap is if the current interval’s start is less than the last included interval’s end. So if we find overlap, we need to remove 1 of the interval.
We should remove the interval that has the bigger end. Here, we are not actually removing it. We can use a variable last to mark which interval is the last included interval. So we start from index 1, and compare interval[last] with interval[i].
If the current interval is not overlapped with the last included interval, we mark the current interval as the new last included interval.

Solution

func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) < 2 { return 0 }

    sort.Slice(intervals, func (i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    res := 0
    last := 0

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[last][1] { // overlap
            res += 1
            if intervals[i][1] < intervals[last][1] {
                last = i
            }
        } else { // non-overlap
            last = i
        }
    }

    return res
}

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

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

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Explanation

Note that the maximum transaction is 2, and we can sell and buy on the same day. We can divide this array into two parts: prices[0:n-1] => prices[0:i] + prices[i:n-1], so we need to find the maximum of profit on or before day i, and the maximum profit on or after day i, then the result will be the sum of the two.
We can solve this problem by calculating every indexes i’s mostLeftProfit and mostRightProfit, then the result will be the maximum of the sum of these two.
First, we use an array to store all indexes mostLeftProfit by iterating from beginning to the end. Then, we iterate from the end back to the beginning to calculate the mostRightProfit and compare each index’s mostLeftProfit and its mostRightProfit to get the final maximum result.

Solution

func maxProfit(prices []int) int {
    if len(prices) < 2 { return 0 }
    n := len(prices)

    leftProfit := make([]int, n)
    mostLeftProfit, min := 0, prices[0]
    for i := 1; i < n; i++ {
        if prices[i] < min {
            min = prices[i]
        } else {
            mostLeftProfit = getMax(mostLeftProfit, prices[i] - min)
        }
        leftProfit[i] = mostLeftProfit
    }

    rightProfit := make([]int, n)
    mostRightProfit, max := 0, prices[n-1]
    res := 0
    for i := n-2; i >= 0; i-- {
        if prices[i] > max {
            max = prices[i]
        } else {
            mostRightProfit = getMax(mostRightProfit, max - prices[i])
        }
        rightProfit[i] = mostRightProfit

        res = getMax(res, leftProfit[i] + rightProfit[i])
    }

    return res
}

func getMax(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

Distribute Candies to People

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example 1:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

Example 2:

Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].

Constraints:

1 <= candies <= 10^9
1 <= num_people <= 1000

Hint 1:

Give candy to everyone each “turn” first [until you can’t], then give candy to one person per turn.

Explanation

We can solve this problem using brute force.
While candies greater than 0, we start to give cur candies. Each iteration, we increment the cur, distribute cur to res[idx % num_people]. Also we need to update candies -= cur. Note, candies < cur, then we update cur = candies and assign it instead.

Solution

func distributeCandies(candies int, num_people int) []int {
    res := make([]int, num_people)
    idx, cur := 0, 0

    for candies > 0 {
        cur += 1
        if candies < cur { cur = candies }
        candies -= cur
        res[idx % num_people] += cur
        idx += 1
    }

    return res
}

Numbers With Same Consecutive Differences

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

Explanation

We can solve this problem using DFS.

For example, when N = 3, K= 7, we have:

 N = 3, K = 7


         1             2          3        4        7       8
        / \           / \        / \      / \      / \     / \
       -   8         -   9      -   -     -  -    0   -   1   -
          / \           / \                      /  \    / \
         1   -         2   -                    -    7  -   8

In the main function, we loop i from 1 to 9 inclusive, each iteration, we recursively call the helper function with the current number i, N-1, and res as parameters.
Inside the helper function, the base case is if N is 0, that means we finish all the digits, so we return the current number. Else, we can get the last digit of the current number by cur % 10, then we have two cases. First is the lastDgiit - K >= 0, then we recursively call the helper function with the updated current number cur * 10 + lastDigit - K, N - 1, and res. Second case is check lastDigit + K <= 9, then we recursively call the helper function with the updated current number cur * 10 + lastDgit + K, N - 1, and res.
Note, if K is 0, the above two cases will have the repeated current number, so we need to check that and run one recursive function when K is 0. Also when N is 1, we need to add 0 to the result list.

Solution

func numsSameConsecDiff(N int, K int) []int {
    res := make([]int, 0)
    if N == 1 { res = append(res, 0) }

    for i := 1; i <= 9; i++ {
        helper(i, N-1, K, &res)
    }

    return res
}

func helper(cur, N, K int, res *[]int) {
    if N == 0 {
        *res = append(*res, cur)
        return
    }
    lastDigit := cur % 10
    if lastDigit - K >= 0 {
        helper(cur*10+lastDigit-K, N-1, K, res)
    }
    if K > 0 && lastDigit + K <= 9 {
        helper(cur*10+lastDigit+K, N-1, K, res)
    }
}

Goat Latin

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to “Goat Latin” (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word.

For example, the word ‘apple’ becomes ‘applema’.

If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma".

For example, the word "goat" becomes "oatgma".

Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.

For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Notes:

S contains only uppercase, lowercase and spaces. Exactly one space between each word.
1 <= S.length <= 150.

Explanation

To determine if the first character is vowel, we can put all vowel into a set, then check if the set has this character or not.
For the suffix of a, we can use a string builder to build the suffix. Each iteration, we append a to the string builder.
We can split the string by space, then loop through each word. First append a to the suffix. Then check if the word’s first character is vowel, then we can append the word, the "ma", the suffix and the space. Else if the word’s first character is not vowel, we need to modify the word, append "ma" the suffix and the space. At the end remove the last space and return the result.

Solution

func toGoatLatin(S string) string {
    res := strings.Builder{}
    words := strings.Split(S, " ")
    suffix := strings.Builder{}

    vowelsArr := []byte{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    vowels := make(map[byte]bool)
    for _, vowel := range vowelsArr {
        vowels[vowel] = true
    }

    for _, word := range words {
        suffix.WriteString("a")
        suffixStr := suffix.String()
        if _, ok := vowels[word[0]]; !ok {
            word = word[1:] + string(word[0])
        }
        res.WriteString(word)
        res.WriteString("ma")
        res.WriteString(suffixStr)
        res.WriteString(" ")
    }

    resStr := res.String()
    return resStr[:len(resStr)-1]
}

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1	`Given 1->2->3->4, reorder it to 1->4->2->3.`

Example 2:

1	`Given 1->2->3->4->5, reorder it to 1->5->2->4->3.`

Explanation 1

Make a cur pointer to the head, while the pointer is not null, push cur pointer’s node to the stack.
Note, if there are 4 nodes like 1->2->3->4, then we only need to pop n = (stack.size()-1)/2 = (4-1)/2 = 1 time. Because we just want to connect 1->4, but 2->3 is already connected. After we finish poping n times, we set 3->null, which is st.peek().next = null.
Make cur pointer points back to the head. Now the top node of the stack is the next node of cur. We can pop it and set it to cur.next and move the cur to the right position and decrease the counter.

Solution 1

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil { return }

    st := make([]*ListNode, 0)
    cur := head
    for cur != nil {
        st = append(st, cur)
        cur = cur.Next
    }

    n := len(st)
    if n <= 2 { return }

    cur = head
    for i := 0; i < n / 2; i++ {
        temp := cur.Next
        cur.Next = st[len(st)-1]
        st = st[:len(st)-1]
        cur.Next.Next = temp
        cur = temp
    }
    cur.Next = nil
}

Explanation 2

We don’t need the stack and reduce space complexity to $O(1)$. We notice that in the stack approach, we only care about the second half of the list. For example if the input list is 1 -> 2 -> 3 -> 4 -> 5, then the result is 1 -> 5 -> 2 -> 4 -> 3, and we notice that the second half 4 -> 5 is reversed. So we can reverse the second half of the input list, then connect first half’s node and second half’s node one at a time. For example, we connect 1 -> 5, then 2 -> 4.
To reverse the second half of the input list node, we can apply the slow and fast pointer approach to get the middle node or the second half’s first node, then from there, we reverse the node to the end.
After we reverse, we have 1 -> 2 -> 3 <- 4 <- 5. Now, head points at 1 and pre points at 5. In other words, we can think of two list nodes. n1 = 1 -> 2 -> 3, and n2 = 5 -> 4 -> 3 -> null.
While n2.next != null, we connect 1 and 5, then 2 and 4.

Solution 2

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil { return }

    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    var pre *ListNode
    // pre := &ListNode{}
    // pre = nil
    cur := slow
    for cur != nil {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }

    n1, n2 := head, pre
    for n2.Next != nil {
        temp := n1.Next
        n1.Next = n2
        n1 = temp

        temp = n2.Next
        n2.Next = n1
        n2 = temp
    }
}

Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Explanation

We can solve this problem using two pointers approach.
Create a pointer l points to the first index of the array, another pointer r poionts to the last index of the array. While l < r, while A[l] is even number, we increase l ; while A[r] is odd number, we decrease r. Now A[l] is odd number and A[r] is even number, so we swap them. Then increase pointer l and decrease pointer r. Repeat while l < r.

Solution

func sortArrayByParity(A []int) []int {
    l, r := 0, len(A)-1
    for l < r {
        for l < r && A[l] % 2 == 0 { l += 1 }
        for l < r && A[r] % 2 != 0 { r -= 1 }
        A[l], A[r] = A[r], A[l]
        l += 1
        r -= 1
    }
    return A
}

Week 4: August 22nd - August 28th

The Maze

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1:

Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: true

Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2:

Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)

Output: false

Explanation: There is no way for the ball to stop at the destination.

Note:

There is only one ball and one destination in the maze.
Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
The maze contains at least 2 empty spaces, and both the width and height of the maze won’t exceed 100.

Explanation 1

We can use DFS to solve this problem.
While the ball is not outside the boundary and not hitting the wall, we keep updating the ball’s position toward the current direction. When the ball stops, we recursively call the helper function.
We can mark the visited position as -1 in the maze array to avoid duplication.

Solution 1

class Solution {
    boolean helper(int[][] maze, int[] start, int[] destination, int[] dx, int[] dy) {
        int startRow = start[0], startCol = start[1];
        int destinationRow = destination[0], destinationCol = destination[1];
        if (startRow == destinationRow && startCol == destinationCol) return true;
        if (maze[startRow][startCol] == -1) return false;
        maze[startRow][startCol] = -1;

        int row = maze.length - 1, col = maze[0].length - 1;
        for (int i = 0; i < 4; i++) {
            int ballRow = startRow, ballCol = startCol;
            while (ballRow >= 0 && ballRow <= row && ballCol >= 0 && ballCol <= col && maze[ballRow][ballCol] != 1) {
                ballRow += dx[i];
                ballCol += dy[i];
            }
            ballRow -= dx[i];
            ballCol -= dy[i];
            if (maze[ballRow][ballCol] == -1) continue;
            boolean res = helper(maze, new int[]{ballRow, ballCol}, destination, dx, dy);
            if (res) return true;
        }

        return false;
    }

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        return helper(maze, start, destination, dx, dy);
    }
}

Explanation 2

We can also use BFS to solve this problem.
We put the ball’s start position into the queue. While queue is not empty, we pop the ball’s starting position out. First check if this position is the destination position, then updating the ball’s position until it hits the wall or outside boundary. Then pass the ball’s stopping position into the queue. Repeat until queue is empty.

Solution 2

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int row = maze.length - 1, col = maze[0].length - 1;
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(start);
        while (!queue.isEmpty()) {
            int[] curStart = queue.poll();
            int startRow = curStart[0], startCol = curStart[1];
            int destinationRow = destination[0], destinationCol = destination[1];
            if (startRow == destinationRow && startCol == destinationCol) return true;
            if (maze[startRow][startCol] == -1) continue;

            maze[startRow][startCol] = -1;
            for (int i = 0; i < 4; i++) {
                int ballRow = startRow, ballCol = startCol;
                while (ballRow >= 0 && ballRow <= row && ballCol >= 0 && ballCol <= col && maze[ballRow][ballCol] != 1) {
                    ballRow += dx[i];
                    ballCol += dy[i];
                }
                ballRow -= dx[i];
                ballCol -= dy[i];

                if (maze[ballRow][ballCol] == -1) continue;
                queue.offer(new int[]{ballRow, ballCol});
            }
        }

        return false;
    }
}

Random Point in Non-overlapping Rectangles

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

An integer point is a point that has integer coordinates.
A point on the perimeter of a rectangle is included in the space covered by the rectangles.
ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
length and width of each rectangle does not exceed 2000.
1 <= rects.length <= 100
pick return a point as an array of integer coordinates [p_x, p_y]
pick is called at most 10000 times.

Example 1:

Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]

Example 2:

Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution’s constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Explanation

We can use Reservoir Sampling to solve this problem. In the constructor, we can just pass the rects[][] to the class field this.rects. In the pick() method, in order to use reservoir sampling, we need to have a variable sumArea which means the sum of all rectangles’ area. When iterate all the rectangles, we first update sumArea. Then the current rectangle’s area will be the pool size. If the random area between 1 to sumArea inclusive is less than or equals to the current rectangle’s area, then we will choose this rectangle to find random point.
After iterating all rectangles and getting the selected rectangle, we can random pick any point on this selected rectangle.
To calculate area, we will add 1 to rectangle’s width and add 1 to its height since the point can on the corners. For example, if we have rectangle [0, 0, 1, 1], the normal area will just be 1. but since points can on corner, we have 4 points [0,0], [0, 1], [1, 0], [1, 1]. we can calculate it by (1-0+1) * (1-0+1) = 4.
Instead of randomly pick the index of the list of rectangles, we randomly pick by area because if the larger rectangle have higher chance to get picked.

Solution

type Solution struct {
    rects [][]int
    accumulatePoints []int
    totalPoints int
}


func Constructor(rects [][]int) Solution {
    totalPoints := 0
    accumulatePoints := make([]int, len(rects))
    for i := range rects {
        totalPoints += CalculatePoints(rects[i])
        accumulatePoints[i] = totalPoints
    }
    return Solution{rects, accumulatePoints, totalPoints}
}


func (this *Solution) Pick() []int {
    randNum := rand.Intn(this.totalPoints)
    left, right := 0, len(this.accumulatePoints)
    for left < right {
        mid := left + (right - left) / 2
        if this.accumulatePoints[mid] <= randNum {
            left = mid + 1
        } else {
            right = mid
        }
    }

    accumulatePointsStart := this.accumulatePoints[left] - CalculatePoints(this.rects[left])
    offset := randNum - accumulatePointsStart
    col := this.rects[left][2] - this.rects[left][0] + 1
    x := this.rects[left][0] + offset % col
    y := this.rects[left][1] + offset / col
    return []int{x, y}
}


func CalculatePoints(rect []int) int {
    width := rect[2] - rect[0] + 1
    height := rect[3] - rect[1] + 1
    return width * height
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(rects);
 * param_1 := obj.Pick();
 */

Stream of Characters

Implement the StreamChecker class as follows:

StreamChecker(words): Constructor, init the data structure with the given words.
query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note:

1 <= words.length <= 2000
1 <= words[i].length <= 2000
Words will only consist of lowercase English letters.
Queries will only consist of lowercase English letters.
The number of queries is at most 40000.

Hint 1:

Put the words into a trie, and manage a set of pointers within that trie.

Explanation

After reading the problem, first thing come up is to use Trie. From the problem’s example, we notice that when we run the query method for input character letter, if letter is not the last character of word, we return false immediately.
For example, after we query letter d, it’s the end of one of the word, then we query its previous letter c, and we find out cd is a word, so we return true.
We can modify the Trie a little bit, instead of inserting each word, we insert the reverse of each word. So the trie will have ["dc", "f", "lk"]. Also, when we query, we need to keep the previous letters. For example, we query d, it’s in the trie, then we query c. So each time when we query a letter, we append this character in the beginning of a list, so we can use a deque for this list. After we insert the letter into the deque, for example, when we are on letter d, we have [d, c, b, a]. We pass this deque to the Trie’s search method to search if the character is end of word.

Solution

type Trie struct {
    children []*Trie
    isEnd bool
}

func TrieConstructor() Trie {
    return Trie{make([]*Trie, 26), false}
}

func (this *Trie) Insert(s string) {
    cur := this
    for _, ch := range s {
        if cur.children[ch - 'a'] == nil {
            cur.children[ch - 'a'] = &Trie{make([]*Trie, 26), false}
        }
        cur = cur.children[ch - 'a']
    }
    cur.isEnd = true
}

func (this *Trie) Search(s []byte) bool {
    cur := this
    for _, ch := range s {
        if cur.children[ch - 'a'] == nil { return false }
        cur = cur.children[ch - 'a']
        if cur.isEnd == true { return true }
    }
    return false
}


type StreamChecker struct {
    trie Trie
    deque []byte
}


func Constructor(words []string) StreamChecker {
    trie := TrieConstructor()
    deque := make([]byte, 0)
    for _, word := range words {
        revWord := Reverse(word)
        trie.Insert(revWord)
    }
    return StreamChecker{trie, deque}
}


func (this *StreamChecker) Query(letter byte) bool {
    this.deque = append([]byte{letter}, this.deque...)
    return this.trie.Search(this.deque)
}


func Reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}


/**
 * Your StreamChecker object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Query(letter);
 */

Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Explanation

We can use recursion to solve this problem. We create a helper method that will return an interger.
The base case will be if the TreeNode is null, then we return 0.
So, if it has left or right child, that means this TreeNode is not a leave, we cannot add its value. So, we recursivly check its left and right child. For its left child, we should have a boolean variable that denotes it’s left child. In the left child’s helper recursive function, isLeft should be true. In the right child’s helper recrusive function, isLeft should be false. We add both recusive function’s return result to res. At the end, we return res.

Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    return helper(root, false)
}

func helper(root *TreeNode, isLeft bool) int {
    if root == nil { return 0 }
    if isLeft && root.Left == nil && root.Right == nil {
        return root.Val
    }
    res := 0
    res += helper(root.Left, true)
    res += helper(root.Right, false)
    return res
}

Minimum Cost For Tickets

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars; a 7-day pass is sold for costs[1] dollars; a 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Explanation 1

We can use dynamic programming to solve this problem.
Dynamic state is dp[i] represents the minimum cost for days[i] to days[days.length-1].
Dynamic init is dp[dp.length-1] is the minimum between costs[0], costs[1], costs[2].
Dynamic function. For i from right to left, start from the second last day, in other word, dp[dp.length-2] is either choose to buy a 1-day ticket, 7-day ticket, or 30-day ticket. If buying a 1-day ticket, then the cost will be costs[0] + dp[i + 1]. If buying a 7-day ticket, then the cost will be costs[1] + dp[j] where days[j] >= days[i] + 7.Similarlly, if buying a 30-day ticket, then the cost will be costs[2] + dp[k] where days[k] >= days[i] + 30.
For example, days = [1,4,6,7,8,20]. When i is the last index pointing to day 20, the cost will be the minimum prices among these 3 tickets. When i is the second last index points to day 8, buying 1-day ticket cost will be costs[0] + dp[i + 1]. Buying 7-day ticket will cover day 8 to day 14 inclusive, but day 20 is not cover, so the total cost will be costs[1] + dp[i + 1]. Buying a 30-day ticket will cover day 8 to day 37 inclusive, so the total cost will be costs[2]. After we calculate all 3 options, we take the minimum as the result for dp[i].
Dynamic result is dp[0].

Solution 1

func mincostTickets(days []int, costs []int) int {
    dp := make([]int, len(days))
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[len(dp) - 1] = min(costs[0], min(costs[1], costs[2]))

    for i := len(dp) - 2; i >= 0; i-- {
        j, k := i, i
        for j < len(dp) && days[j] < days[i] + 7 { j += 1 }
        for k < len(dp) && days[k] < days[i] + 30 { k += 1 }

        a := costs[0] + dp[i+1]
        b := costs[1]
        c := costs[2]
        if j < len(dp) { b += dp[j] }
        if k < len(dp) { c += dp[k] }
        dp[i] = min(a, min(b, c))
    }

    return dp[0];
}

func min (a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

Explanation 2

We can also use top down approach.

Solution 2

func mincostTickets(days []int, costs []int) int {
    hm := make(map[int]int)
    return helper(days, costs, 0, hm)
}

func helper(days []int, costs []int, startDaysIdx int, hm map[int]int) int {
    if startDaysIdx >= len(days) { return 0 }
    if _, ok := hm[startDaysIdx]; ok { return hm[startDaysIdx] }

    i, j, k := startDaysIdx, startDaysIdx, startDaysIdx
    for i < len(days) && days[i] < days[startDaysIdx] + 1 { i += 1 }
    for j < len(days) && days[j] < days[startDaysIdx] + 7 { j += 1 }
    for k < len(days) && days[k] < days[startDaysIdx] + 30 { k += 1 }

    a := costs[0] + helper(days, costs, i, hm);
    b := costs[1] + helper(days, costs, j, hm);
    c := costs[2] + helper(days, costs, k, hm);
    minCost := min(a, min(b, c));

    hm[startDaysIdx] = minCost
    return minCost;
}

func min (a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Explanation

Loop from 1 to n inclusive. Check every conditions using module operator, and add each condition result to the result list.

Solution

func fizzBuzz(n int) []string {
    res := make([]string, n)
    for i := 1; i <= n; i++ {
        if i % 15 == 0 {
            res[i-1] = "FizzBuzz"
        } else if i % 5 == 0 {
            res[i-1] = "Buzz"
        } else if i % 3 == 0 {
            res[i-1] = "Fizz"
        } else {
            res[i-1] = strconv.Itoa(i)
        }
    }
    return res
}

Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

You may assume the interval’s end point is always bigger than its start point.
You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation

It’s trivial to use brute force to solve this problem in $O(n^2)$ time. We can do better in $O(n log n)$ time by sorting the intervals base on start time, then loop through the original input intervals, make each iteration’s interval end time as target, then use binary search to find the smallest start time that is equal or greater than target.
Since we need to return its index, we can make a list of pair, each pair is the start time and its corresponding index. For example, [[startTime, idx], [startTime, idx], [startTime, idx]], and we sort this list by startTime. After we find the smallest startTime that is equal or greater than target, we return its corresponding index.

Solution

func findRightInterval(intervals [][]int) []int {
    res := make([]int, len(intervals))
    startAndIdx := make([][]int, len(intervals))
    for i := range startAndIdx {
        startAndIdx[i] = make([]int, 2)
    }

    for i := 0; i < len(intervals); i++ {
        startAndIdx[i][0] = intervals[i][0]
        startAndIdx[i][1] = i
    }

    sort.Slice(startAndIdx, func(i, j int) bool {
        return startAndIdx[i][0] < startAndIdx[j][0]
    })

    for i := 0; i < len(intervals); i++ {
        target := intervals[i][1]
        res[i] = helper(startAndIdx, target)
    }

    return res
}

func helper(startAndIdx [][]int, target int) int {
    left, right := 0, len(startAndIdx)

    for left < right {
        mid := left + (right - left) / 2
        if startAndIdx[mid][0] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }

    if left == len(startAndIdx) {
        return -1
    }

    if startAndIdx[left][0] >= target {
        return startAndIdx[left][1]
    } else {
        return -1
    }
}

Implement Rand10() Using Rand7()

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Explanation

First we run rand7() and store in v1, run rand7() and store in v2.
v1 only stores number from 1 to 5 inclusive, while v1 is greater than 5, we run rand7() again.
v2 only stores number from 1 to 6 inclusive, while v2 is equal to 7, we run rand7() again.
Now for v2, the probability of getting 1 to 3 is equal to getting 4 to 6. If v2 is between 1 to 3, we can return v1 immediately. Else if it’s in between 4 to 6, then we return v1 + 5.

Solution

func rand10() int {
    v1, v2 := rand7(), rand7()
    for v1 > 5 { v1 = rand7() }
    for v2 == 7 { v2 = rand7() }

    if v2 <= 3 {
        return v1
    } else {
        return v1 + 5
    }
}

Week 5: August 29th - August 31st

Robot Room Cleaner

Given a robot cleaner in a room modeled as a grid.

Each cell in the grid can be empty or blocked.

The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Example:

Input:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

Notes:

The input is only given to initialize the room and the robot’s position internally. You must solve this problem “blindfolded”. In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot’s position.
The robot’s initial position will always be in an accessible cell.
The initial direction of the robot will be facing up.
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
Assume all four edges of the grid are all surrounded by wall.

Explanation

We can use DFS to solve this problem. First, we define 4 directions in clock-wise. dirArr = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}} which represents top, right, bottom, left. Also, we create a visited hash set to record the visited coordinates.
In the main function, we start the DFS with the current position initialize it’s x=0, y=0, and also the robot’s direction dir, initialize dir is top (0). It’s very important that we need this dir because the robot needs to have a direction, then it can move accordingly. For example, if the robot is facing the right direction, then we cannot move it top or down or left. Inside the dfs helper function, first, we run the clean function and add this coordinate into the hashset.
Next, loop i in 4 directions. Inside the loop, first, we need to update the robot’s new direction newDir, which can be dir + i. Then we update the new x coordinate and new y coordinate base on this new direction. In other words, newX = x + dirArr[newDir][0] and newY = y + dirArr[newDir][1]. To avoid out of bound newDir need to module 4.
Next, we check this new coordinate is visited or not, if it’s not visited and move returns true, then we can recursively call this dfs helper function. After moving the robot to another coordinate, we need to backtrack the robot to its previous direction and previous coordinate. For example, in the below’s diagram, if the robot original at position A and original direction is top, then we move it top to position B. Then we want to backtrack to position A and face top direction. At position B, we can turnRight two times and move to A (at A face down direction), then turnLeft two times to face top direction.
After the if check, we are in the original position and direction, that means we finish checking this position with this direction, so we change the robot’s direction and ready for the next iteration.

Solution

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     public boolean move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     public void turnLeft();
 *     public void turnRight();
 *
 *     // Clean the current cell.
 *     public void clean();
 * }
 */

class Solution {
    void helper(Robot robot, int x, int y, int dir, int[][] dirArr, Set<String> visited) {
        robot.clean();
        visited.add(String.valueOf(x) + "#" + String.valueOf(y));

        for (int i = 0; i < 4; i++) {
            int newDir = (dir + i) % 4;
            int newX = x + dirArr[newDir][0];
            int newY = y + dirArr[newDir][1];
            if (!visited.contains(String.valueOf(newX) + "#" + String.valueOf(newY)) && robot.move()) {
                helper(robot, newX, newY, newDir, dirArr, visited);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }
            robot.turnRight();
        }
    }

    public void cleanRoom(Robot robot) {
        int[][] dirArr = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        Set<String> visited = new HashSet<>();
        helper(robot, 0, 0, 0, dirArr, visited);
    }
}

Pancake Sorting

Given an array of integers A, We need to sort the array performing a series of pancake flips.

In one pancake flip we do the following steps:

Choose an integer k where 0 <= k < A.length.
Reverse the sub-array A[0...k].

For example, if A = [3,2,1,4] and we performed a pancake flip choosing k = 2, we reverse the sub-array [3,2,1], so A = [1,2,3,4] after the pancake flip at k = 2.

Return an array of the k-values of the pancake flips that should be performed in order to sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: A = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k = 4): A = [1, 4, 2, 3]
After 2nd flip (k = 2): A = [4, 1, 2, 3]
After 3rd flip (k = 4): A = [3, 2, 1, 4]
After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.

Example 2:

Input: A = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Constraints:

1 <= A.length <= 100
1 <= A[i] <= A.length
All integers in A are unique (i.e. A is a permutation of the integers from 1 to A.length).

Explanation

The constraint of k is actually 1 <= k <= A.length. When k = 4, we flip the first 4 numbers from index 0 to index 3 inclusive.
We can fist find the correct number for the last index, then find the correct number for the second last index, etc. For example, if the input array is [3, 2, 4, 1]. We want to find the correct number for the last index (index 3), since the correct number is 4, we look for target = 4 in the input array. After we find the target’s index, which is 2, then we try to make target at index 0 by flipping from index 0 to index 2 inclusive and we get [4, 2, 3, 1]. Now, target is at index 0, we can flip from index 0 to index 3, and we get [1, 3, 2, 4]. Now, index 3 has the correct number. Next, we want to find the second last index (index 2)’s correct number using the same method. Repeat until we finish finding last n-1 numbers, then we have the sorted array.

Solution

func pancakeSort(A []int) []int {
    res := make([]int, 0)

    for i := len(A)-1; i >= 1; i-- {
        target := i+1
        if A[i] == target { continue }

        for j := 1; j < i; j++ {
            if A[j] == target {
                flip(A, j)
                res = append(res, j+1)
                break
            }
        }

        flip(A, i)
        res = append(res, i+1)
    }

    return res
}

func flip(A []int, idx int) {
    for i := 0; i <= idx / 2; i++ {
        A[i], A[idx-i] = A[idx-i], A[i]
    }
}

Largest Component Size by Common Factor

Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

Explanation

We can use Union Find alogrithm to solve this problem.
First, loop through the input array. For each number num, we want to union all its factors which is greater than 1 into one group. We can loop divisor d from 2 to square root of num inclusive, if num % d == 0, then it means d is a factor. We can group d and num, and also group num/d and num.
After we grouping all numbers with common factor, then we loop the input array. Each iteration, we find the current number’s parent. Then use a hashmap to record parent as key, count of element that has this parent as value. Also, each time, we record the maximum count. At the end, we return this maximum count.

Solution

func largestComponentSize(A []int) int {
    maxNum := 0
    for _, num := range A {
        maxNum = max(maxNum, num)
    }
    parents := make([]int, maxNum + 1)
    for i := range parents {
        parents[i] = i
    }

    for _, num := range A {
        for d := 2; d <= sqrt(num); d++ {
            if num % d == 0 {
                union(d, num, parents)
                union(num/d, num, parents)
            }
        }
    }

    res := 0
    hm := make(map[int]int)
    for _, num := range A {
        pn := find(num, parents)
        hm[pn] += 1
        res = max(res, hm[pn])
    }

    return res
}

func find(a int, parents []int) int {
    pa := parents[a]
    if pa == a { return a }
    parents[a] = find(pa, parents)
    return parents[a]
}

func union(a, b int, parents []int) {
    pa := find(a, parents)
    pb := find(b, parents)
    if pa != pb {
        parents[pa] = pb
    }
}

func max(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

func sqrt(num int) int {
    a := math.Sqrt(float64(num))
    return int(a)
}

Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Explanation 1

Besides the problem’s example, we have one more example and the remove key is 4 in this example.

We can use recursive method to solve this problem. We can find the key very quick using BST’s characteristic. If the current TreeNode’s value is equals to key, then if one of this TreeNode’s child is null, then we return another child. If this TreeNode’s both children exist, then we replace this TreeNode’s value equals to its right child tree’s minium value, in other words, the most left node of the right child which is the inorder successor. After replacing, we recursivly remove the replaced value as key on the right child.

Solution 1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil { return root }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        if root.Left == nil {
            return root.Right
        } else if root.Right == nil {
            return root.Left
        } else {
            inorderSuccessor := root.Right
            for inorderSuccessor.Left != nil {
                inorderSuccessor = inorderSuccessor.Left
            }
            root.Val = inorderSuccessor.Val
            root.Right = deleteNode(root.Right, root.Val)
        }
    }
    return root
}

Explanation 2

Instead of finding the inorder successor two times, we can save the inorder successor’s parent. After replacing the root value as the inorder successor’s value, then we can delete the replaced value from inorder successor parent node. In other word, inorderSuccessorParent.left = deleteNode(inorderSuccessor, root.val).

Solution 2

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil { return root }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        if root.Left == nil {
            return root.Right
        } else if root.Right == nil {
            return root.Left
        } else {
            inorderSuccessorParent := root
            inorderSuccessor := root.Right
            for inorderSuccessor.Left != nil {
                inorderSuccessorParent = inorderSuccessor
                inorderSuccessor = inorderSuccessor.Left
            }
            root.Val = inorderSuccessor.Val
            if inorderSuccessorParent == root {
                root.Right = deleteNode(root.Right, root.Val)
            } else {
                inorderSuccessorParent.Left = deleteNode(inorderSuccessor, root.Val)
            }
        }
    }
    return root
}