Still working from home, let’s pratice more Leetcode problems for July LeetCoding Challenge.

Week 1: July 1st - July 7th

Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Explanation

We can also use binary search to solve this problem. Initialize left = 1, right = n, mid is the row we guess. From row 1 to row mid inclusive, there are total mid * (mid+1)/2 elements. While left <= right. If the sum == n, we return mid rows; else if sum < n, then we update left = mid + 1; else if sum > n, then we update right = mid -1. So outside the while loop, we return right.

Solution

func arrangeCoins(n int) int {
    left, right := 0, n
    for left <= right {
        mid := left + (right - left) / 2
        sum := (mid * (mid + 1)) / 2
        if sum == n {
            return mid
        } else if sum < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Explanation

Similar to 102. Binary Tree Level Order Traversal. This time, instead of adding the sublist to the end of the result list, we should add the sublist at the beginning of the result list.

Solution

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

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        sub := make([]int, 0)
        for i := len(queue) - 1; i >= 0; i-- {
            cur := queue[0]
            queue = queue[1:]
            sub = append(sub, cur.Val)
            if cur.Left != nil { queue = append(queue, cur.Left) }
            if cur.Right != nil { queue = append(queue, cur.Right) }
        }
        res = append(res, []int{})
        copy(res[1:], res)
        res[0] = sub
    }

    return res
}

Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation:
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

cells.length == 8
cells[i] is in {0, 1}
1 <= N <= 10^9

Explanation

We notice that from day 1, the first index and the last index will always be 0, and only the middle 6 numbers will always be changed. Since the each element can only be either 0 or 1, the total possibility of the middle 6 elements will be 2^6=64. No matter how large the N is, it will have the chance to repeat. We can even reduce from these 64 possibilities further. Among these 64 possibilities, only the possibility that satisfy two adjacent neighbors are same, then the middle number will be 1, else the middle number will be 0. For example, (0)111000(0) is not satisfy this requirement, in other words, we will not have the chance to transform the array to this number. So the total possibility array that we can transform the input array to is far less than 64.
Now we know that there is a chance of repeating transform the same cells array, we can use a HashMap to store the key as the cell array in string representation, the value is the current i day. Loop i from day 0 to N-1 inclusive, if the HashMap contains the key of the i day’s array, that means we are repeating to transform the same cell array. We can calculate the loop length loopLen = i - hm[array]. Since in day 0, we may start from an invalid array like (0)111000(0), we can’t just return prisonAfterNDays(cells, N % loopLen), instead, we return prisonAfterNDays(cells, (N-i) % loopLen).
If the HashMap does’t contains the current array as the key, then we brute force to transform the cell array. Initialize pre = 0, Loop j from 1 to 6 inclusive, next = cells[j + 1], cur = cells[j], then update cells[j] to 1 if pre == next else 0, pre = cur.

Solution

func prisonAfterNDays(cells []int, N int) []int {
    hm := make(map[string]int, 0)

    for i := 0; i < N; i++ {
        kArr := fmt.Sprint(cells)

        if _, ok := hm[kArr]; ok {
            loopLen := i - hm[kArr]
            return prisonAfterNDays(cells, (N - i) % loopLen)
        } else {
            hm[kArr] = i
            pre := cells[0]
            for j := 1; j <= 6; j++ {
                next := cells[j + 1]
                cur := cells[j]
                cells[j] = 1 - (pre ^ next)
                pre = cur
            }
            cells[0] = 0
            cells[7] = 0
        }
    }

    return cells
}

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

Hint 1:

The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.

Hint 2:

An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

Hint 3:

The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.

Hint 4:

Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

Explanation

Ugly number is equal to ugly number multiple by ugly number.
First we initialize 3 index pointers (ptrInd2, ptrInd3, ptrInd5) pointing to index 0. We know that in index 0, the number is 1, which is the first ugly number.
Then, the next ugly number will be the minimum of min(res[ptrInd2]*2, res[ptrInd3]*3, res[ptrInd5]*5)., which is min(1*2, 1*3, 1*5), so the minimum is 2, then we add 2 to be the next ugly number, then we increase ptrInd2 by 1, now ptrInd2=0+1=1. Since the old ptrInd2 multiple by 2 is already added to the result list, we don’t want it in the future. Similarly, if the min is 1*3, we increase the ptrInd3 by 1, same as ptrInd5.
When the size of the result list is n, we finish the loop, and resturn the last element of the result list.

Solution

func nthUglyNumber(n int) int {
    res := make([]int, n)
    res[0] = 1
    ptrTwo, ptrThree, ptrFive := 0, 0, 0

    for i := 1; i < n; i++ {
        nextTwo := res[ptrTwo] * 2
        nextThree := res[ptrThree] * 3
        nextFive := res[ptrFive] * 5

        nextUgly := min(nextTwo, min(nextThree, nextFive))
        if nextUgly == nextTwo { ptrTwo += 1 }
        if nextUgly == nextThree { ptrThree += 1 }
        if nextUgly == nextFive { ptrFive += 1 }

        res[i] = nextUgly
    }

    return res[n-1]
}

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

Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:

0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Explanation

The problem asks us to find the number of different bit between these two numbers. We can use XOR these two numbers and get the result a. In a’s binary form, the number of bit 1 is the number of different bits between x and y. In other words, this problem asks us to find the number of set bits in x XOR y.
We can do a AND 1 to get the most right bit. If the result is 1, then the right most bit of a is 1. If the result is 0, then the right most bit of a is 0.

Solution

func hammingDistance(x int, y int) int {
    res := 0
    a := x ^ y
    for (a > 0) {
        res += a & 1
        a >>= 1
    }
    return res
}

Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Explanation

Loop through the array from the last index element, if it is less than 9, then we can add one to it, and return;
1
[1, 2, 3] => [1, 2, 4]
Else if it is 9, then we set this element to 0, and continue to check the next element.
1
[1, 2, 9] => [1, 3, 0]
After the loop, meanning that it’s still not returning and the first index element is 0. Then, we create a new array have the first element set to 1, and starts from the second elment, it has all the same elements as the digits array.
1
[9, 9, 9] => [1, 0, 0, 0]

Solution

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] == 9 {
            digits[i] = 0
        } else {
            digits[i] += 1
            return digits
        }
    }
    return append([]int{1}, digits...)
}

Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

Explanation 1

We can loop through all cells. For each cell, if the cell is 0, then we ignore it. If the cell is 1, then we check this cell’s 4 sides: top, bottom, left, right cell.
If it doens’t have top cell, that means this cell’s top line is on the edge, so we add 1 to res; or this cell’s top cell is 0, then we add 1 to res. Then, we check bottom current cell’s bottom cell. If it doesn’t have bottom cell or its bottom cell is 0, then we add 1 to res. Similarlly for current cell’s left and right cells.

Solution 1

func islandPerimeter(grid [][]int) int {
    res := 0

    for r := 0; r < len(grid); r++ {
        for c := 0; c < len(grid[0]); c++ {
            if grid[r][c] == 0 { continue }

            if r == 0 || grid[r-1][c] == 0 { res += 1 }
            if r == len(grid)-1 || grid[r+1][c] == 0 { res += 1 }
            if c == 0 || grid[r][c-1] == 0 { res += 1 }
            if c == len(grid[0])-1 || grid[r][c+1] == 0 { res += 1 }
        }
    }

    return res
}

Explanation 2

For each cell that is 1, we can first add 4 to res. Then check the current cell’s top cell, if the top cell is also 1, we subtract res by 2. Also we check the current cell’s left cell, if the left cell is also 1, we subtract res by 2.

Solution 2

func islandPerimeter(grid [][]int) int {
    res := 0

    for r := 0; r < len(grid); r++ {
        for c := 0; c < len(grid[0]); c++ {
            if grid[r][c] == 0 { continue }
            res += 4
            if r > 0 && grid[r-1][c] == 1 { res -= 2 }
            if c > 0 && grid[r][c-1] == 1 { res -= 2 }
        }
    }

    return res
}

Week 2: July 8th - July 14th

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Hint 1:

So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!

Hint 2:

For the two-sum problem, if we fix one of the numbers, say

, we have to scan the entire array to find the next number

which is

1	`value - x`

where value is the input parameter. Can we change our array somehow so that this search becomes faster?

Hint 3:

The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Explanation

Sort the array.
If the first element is greater than 0 or the last element is less than 0, we know that we can’t form a 0.
Loop through the array start from the first element, we fix the first element, then use two pointers technique to find two elements that sum to targetVal-fixVal until break out the left < right condition. While looping, we need to ignore the same fix number and left and right values.
We can actually convert this problem to a nSum problem.

Solution

func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    sort.Ints(nums)

    if len(nums) < 3 || nums[0] > 0 || nums[len(nums)-1] < 0 {
        return res
    }

    return nSum(nums, 3, 0, 0)
}

func nSum(nums []int, n, start, target int) [][] int {
    res := make([][]int, 0)
    if n < 2 || start >= len(nums) { return res }
    if n == 2 { return twoSum(nums, start, target) }

    for i := start; i < len(nums); i++ {
        lst := nSum(nums, n-1, i+1, target-nums[i])
        for _, sub := range lst {
            sub = append([]int{nums[i]}, sub...)
            res = append(res, sub)
        }
        for i < len(nums) - 1 && nums[i] == nums[i+1] { i += 1}
    }

    return res
}

func twoSum(nums []int, start, target int) [][]int {
    res := make([][]int, 0)

    left, right := start, len(nums)-1

    for left < right {
        sum := nums[left] + nums[right]
        if sum < target {
            left += 1
        } else if sum > target {
            right -= 1
        } else {
            res = append(res, []int{nums[left], nums[right]})
            for left < right && nums[left] == nums[left+1] { left += 1}
            for left < right && nums[right] == nums[right-1] { right -= 1}
            left += 1
            right -= 1
        }
    }

    return res
}

Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input:

           1
         /   \
        3     2
       / \     \
      5   3     9

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input:

          1
         /
        3
       / \
      5   3

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input:

          1
         / \
        3   2
       /
      5

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input:

          1
         / \
        3   2
       /     \
      5       9
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note: Answer will in the range of 32-bit signed integer.

Explanation

Another BFS method is to make a custom class NodeIdx with property TreeNode and the position of the node. If the root node position is 0, then its left child has position 0 * 2 + 1, its right child has position 0 * 2 + 2 = 2.
In BFS, we need to create a queue to hold the current level’s TreeNodes and their position. So we can calculate the current level’s width as queue.getFirst().idx; - queue.getLast().idx;.
Initially, we put the root node and its position 0 to the queue. While the queue is not empty, we calculate the width using step2’s method. Then pop the current level’s nodes and push their left child and right child with their respective position to the queue. Repeat step 2 and step 3 until the queue is empty.
Return the maximum width.

Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func widthOfBinaryTree(root *TreeNode) int {
    if root == nil { return 0 }
    res := 1

    queue := make([]NodeIdx, 0)
    queue = append(queue, NodeIdx{root, 0})

    for len(queue) > 0 {
        start := queue[0].Idx
        end := queue[len(queue)-1].Idx
        res = max(res, end - start + 1)

        for i := len(queue)-1; i >= 0; i-- {
            cur := queue[0]
            queue = queue[1:]
            curNode := cur.Node
            curIdx := cur.Idx - start // each curIdx subtract start to avoid overflow
            if curNode.Left != nil { queue = append(queue, NodeIdx{curNode.Left, curIdx * 2 + 1})}
            if curNode.Right != nil { queue = append(queue, NodeIdx{curNode.Right, curIdx * 2 + 2})}
        }
    }

    return res
}

type NodeIdx struct {
    Node *TreeNode
    Idx int
}

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

Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

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

The multilevel linked list in the input is as follows:

1	`After flattening the multilevel linked list it becomes:`

Example 2:

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

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

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

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

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

Merging the serialization of each level and removing trailing nulls we obtain:

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

Constraints:

Number of Nodes will not exceed 1000.
1 <= Node.val <= 10^5

Explanation

We can make a flattern helper function to return the last node of the child list so we don’t need to iterat to the last node. We need the last node because we want to connect current node’s child list’s last node with current node’s next node lastNode.next = cur.next.
We pass the head node to the helper function. Inside the helper function, we create two pointers cur and tail. While cur != NULL, we record current node’s next node and child node as next and child respectively.
If child is not NULL, we recursively call the helper function with child as the argument. We update tail to be this recursive helper function’s return node. Then, we connect tail with next. Then connect cur and child. Then update cur.child is NULL. Then we update cur = tail so we don’t need to iterate all child list’s node.
If child is NULL, we simply update tail to be cur and cur be next. At the end, return tail.

Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
    if root == nil { return root }
    helper(root)
    return root
}

func helper(root *Node) *Node {
    cur, tail := root, root

    for cur != nil {
        next, child := cur.Next, cur.Child
        if child != nil {
            tail = helper(child)
            tail.Next = next
            if next != nil { next.Prev = tail }

            cur.Next = child
            child.Prev = cur

            cur.Child = nil
            cur = tail
        } else {
            tail = cur
            cur = next
        }
    }

    return tail
}

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Explanation 1

Backtracking.
The output is: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]].

Solution 1

func subsets(nums []int) [][]int {
    res := make([][]int, 0)
    cur := make([]int, 0)
    helper(nums, 0, cur, &res)
    return res
}

func helper(nums []int, start int, cur []int, res *[][]int) {
    *res = append(*res, append([]int{}, cur...))
    for i := start; i < len(nums); i++ {
        cur = append(cur, nums[i])
        helper(nums, i + 1, cur, res)
        cur = cur[:len(cur)-1]
    }
}

Explanation 2

Recursive method.

solve([1, 2, 3]):
    extract 1 out, solve([2, 3]):
        extract 2 out, solve([3]):
            extract 3 out, solve([]):
                return [[]]
            append 3: [[], [3]]
        append 2: [[], [3], [2], [3, 2]]
    append 1: [[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]

Solution 2

func subsets(nums []int) [][]int {
    res := make([][]int, 0)
    helper(nums, 0, &res)
    return res
}

func helper(nums []int, idx int, res *[][]int) {
    if idx == len(nums) {
        *res = append(*res, []int{})
    } else {
        helper(nums, idx+1, res)
        n := len(*res)
        for i := 0; i < n; i++ {
            cur := (*res)[i]
            *res = append(*res, append([]int{nums[idx]}, cur...))
        }
    }
}

Explanation 3

Iterative method.

init: [[]]
index0: [[], [1]]
index1: [[],[1],[2],[1,2]]
index2: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution 3

func subsets(nums []int) [][]int {
    res := make([][]int, 0)
    res = append(res, []int{})
    for _, num := range nums {
        n := len(res)
        for i := 0; i < n; i++ {
            cur := res[i]
            res = append(res, append([]int{num}, cur...))
        }
    }
    return res
}

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

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

Follow up:

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

Explanation

Loop through 32 times. In each iteration, left shift res.
Get the right most bit using n & 1 and add it to res.
Right shift n.
Outside the loop, return res.

Solution

func reverseBits(num uint32) uint32 {
    var res uint32
    for i := 0; i < 32; i++ {
        res <<= 1
        res += num & 1
        num >>= 1
    }
    return res
}

Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Explanation 1

We can use recursion method to solve this problem. If two tree are the same, then their root.val are the same, and root.left.val are the same, and root.right.val are the same.
The base case is if two trees are NULL, then they are the same, else if one tree is NULL another is not NULL, then we return false.

Solution 1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil { return true }
    if p == nil || q == nil { return false }
    if p.Val != q.Val { return false }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

Explanation 2

We can also use BFS (level-order traversal) to solve this problem. The difference is we can’t pop the nodes from both queue and compare them because in the problem’s Example 2, the second level have the same values 2, but one of them is belongs to the left child, and another one belongs to the right child. So before we push the node into the queue, we need to compare both current nodes’ left childs and right childs.
First, we make a helper function to compare 2 root nodes if they both are NULL or they both have the same value, then return true, else return false.
Initialize two queues q1 to hold the TreeNodes for Tree p, q2 to hold the TreeNodes for Tree q. Then, we push root node p to q1 and push root node q to q2.
While both queue are not empty, we poll out the nodes curP and curQ from both queues. Then we pass their left childs to the helper function, and pass their right childs to the helper function to compare curP.left is the same as curQ.left, and curP.right is the same as curQ.right. If one of the helper function return false, we immediately return false. Else, we push their left child and right child to the queue. Repeat until one of the queue is empty.
Outside the while loop, we can return true.

Solution 2

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if !helper(p, q) { return false }
    q1 := make([]*TreeNode, 0)
    q2 := make([]*TreeNode, 0)
    if p != nil { q1 = append(q1, p) }
    if q != nil { q2 = append(q2, q) }

    for len(q1) > 0 && len(q2) > 0 {
        curP := q1[0]
        q1 = q1[1:]
        curQ := q2[0]
        q2 = q2[1:]
        if !helper(curP.Left, curQ.Left) || !helper(curP.Right, curQ.Right) { return false }
        if curP.Left != nil { q1 = append(q1, curP.Left) }
        if curQ.Left != nil { q2 = append(q2, curQ.Left) }
        if curP.Right != nil { q1 = append(q1, curP.Right) }
        if curQ.Right != nil { q2 = append(q2, curQ.Right) }
    }

    return len(q1) == len(q2)
}

func helper(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil { return true }
    if p == nil || q == nil { return false }
    if p.Val != q.Val { return false }
    return true
}

Angle Between Hands of a Clock

Given two numbers, hour and minutes. Return the smaller angle (in degrees) formed between the hour and the minute hand.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Example 4:

Input: hour = 4, minutes = 50
Output: 155

Example 5:

Input: hour = 12, minutes = 0
Output: 0

Constraints:

1 <= hour <= 12
0 <= minutes <= 59

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

Hint 1:

The tricky part is determining how the minute hand affects the position of the hour hand.

Hint 2:

Calculate the angles separately then find the difference.

Explanation

We know that one hour has 30 degree and one minute has 5 degree, so we need to count how many hour and minute we have. The angel will be the difference between minute degree and hour degree.
If hour is 12, it’s the same as 0, so we can update hour = hour % 12. We know that 30 minutes is 0.5 hour, so the total hour we has is totalHour = hour % 12 + (float)minutes/60. Then we can calculate the hour degree is totalHour * 30. The total minute is the same as the input minute, so the minute degree is minutes * 6.
The angel degree res is equal to the absolute value of the difference between minute degree and hour degree. The result will be the minimum between res and 360-res.

Solution

func angleClock(hour int, minutes int) float64 {
    hDegree := 30 * (float64(hour%12) + float64(minutes)/60)
    mDegree := 6 * float64(minutes)
    res := math.Abs(mDegree - hDegree)
    return math.Min(res, 360-res)
}

Week 3: July 15th - July 21st

Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Explanation 1

If we do this problem without programming, first we would split each word no matter how many spaces in between each word. We can use strings.Fields to get all the words into an array, then reverse this array, and finally use strings.Join to convert this array back to string.

Solution 1

func reverseWords(s string) string {
    arr := strings.Fields(s)
    revArr := reverse(arr)
    return strings.Join(revArr, " ")
}

func reverse(arr []string) []string {
    for i := 0; i < len(arr)/2; i++ {
        arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
    }
    return arr
}

Explanation 2

We can create two pointers start and end point to a word’s beginning index and end index (exclusive), and define n is the length of the string.
While start < n && s[start] == ' ', then we keep increase start. Now, start is pointing to the beginning of the word. Then update end = start + 1, while end < n && s[end] != ' ', then we keep increase end. Now, end is pointing to the ending of the word (exlusive).
If res is empty, we simply update res to s[start, end]. Else, we append s[start, end] + " " to the beginning of the res. After updating res, we then update start = end + 1. Repeat step 2 and step 3 while start < n. If start is equal to n, we need to stop and return the result.

Solution 2

func reverseWords(s string) string {
    start, end, n := 0, 0, len(s)
    res := ""

    for start < n {
        for start < n && string(s[start]) == " " { start += 1 }
        if start == n { return res }
        end = start + 1
        for end < n && string(s[end]) != " " { end += 1 }
        if res == "" {
            res = s[start:end]
        } else {
            res = s[start:end] + " " + res
        }
        start = end + 1
    }

    return res
}

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

Explanation

Let’s see an example first, $2^4 = 4^2 = 16^1$.
We can divide the power by 2 and multiple the base by itself until power is 1.
Default the res equal 1, if the power is an odd number, we can multiple the res by base, then power subtract 1 to become even.
If power is a negative number, we can revert power to positive then after we get the final res, we use 1 to divide the res.
The corner case is the minimum of integer is -2147483648 and the maximum of integer is 2147483647, which is 1 less than the revert of minimum integer. In order to fix it, before we revert the negative power, we add 1 to it, and res multiple by the base because $-2147483648 + 1 = -2147483647$, when we revert it can be a maximum integer now, but we multiple the base one time less, so that is why we multiple the res by base.

Solution

func myPow(x float64, n int) float64 {
    if n == 0 { return 1 }
    if x == 0 { return 0 }
    if n < 0 { return 1 / (x * myPow(x, -n-1)) }

    res := float64(1)

    for n > 1 {
        if n % 2 == 1 {
            res *= x
            n -= 1
        }
        x *= x
        n /= 2
    }

    return res * x
}

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.

Explanation 1

First, create a hashmap to store the number and its frequency.
Next, create a min heap or priority queue, loop through the hashmap, store the hashmap’s entry into the priority queue, and sort by the entry’s value. If the queue has size more than k, we can poll. Since it’s a min heap, the poll entry will be the smallest entry value or frequency.
Now our queue has the k most frequency entry. We can loop through the queue, poll them out add into a res list. Now our res list will have frequency from smallest to largest. At the end, we can reverse the res list and return it.

Solution 1

func topKFrequent(nums []int, k int) []int {
    h := &MinHeap{}
	heap.Init(h)

    hm := make(map[int]int, 0)
    for _, num := range nums {
        hm[num]++
    }
    for ele, freq := range hm {
        heap.Push(h, &EleFreq{ele, freq})
        if h.Len() > k { heap.Pop(h) }
    }

//     sort.Ints(nums)
//     curEle := nums[0]
//     curIdx := 0
//     for i := 0; i < len(nums); i++ {
//         if nums[i] != curEle {
//             heap.Push(h, &EleFreq{curEle, i-curIdx})
//             if h.Len() > k { heap.Pop(h) }
//             curEle = nums[i]
//             curIdx = i
//         }
//     }
//     heap.Push(h, &EleFreq{curEle, len(nums)-curIdx})
//     if h.Len() > k { heap.Pop(h) }

    res := make([]int, k)
    for i := 0; i < k; i++ {
        res[i] = heap.Pop(h).(*EleFreq).Ele
    }

    return res
}

type EleFreq struct {
    Ele int
    Freq int
}

type MinHeap []*EleFreq

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Freq < h[j].Freq }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(*EleFreq))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

Explanation 2

We can use bucket sort with $O(n)$ runtime to solve this problem.
First, we create a hashmap to store each number and its frequency. Then, we find out the maximum frequency, and use the maximum frequency as the length of a new array. The array will have length maximum frequency plus one, since we want the maximum frequency is the last index of this array.
Each array element will be a new array list. Then, we loop through the HashMap, put the entry’s frequency as the array’s index, number will add it to the list arr[i].
Now, we can loop from the back of the array to front, for each arraylist arr[i], we store their number into our res list until the res list has size k.

Solution 2

func topKFrequent(nums []int, k int) []int {
    maxFreq := 0

    hm := make(map[int]int, 0)
    for _, num := range nums {
        hm[num]++
        if hm[num] > maxFreq { maxFreq = hm[num] }
    }

    freqLst := make([][]int, maxFreq+1)

    for ele, freq := range hm {
        freqLst[freq] = append(freqLst[freq], ele)
    }

    res := make([]int, k)
    idx := 0
    for i := maxFreq; i >= 0; i-- {
        for _, ele := range freqLst[i] {
            res[idx] = ele
            idx += 1
            if idx == k { return res }
        }
    }
    return res
}

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

Hint 1:

This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

Hint 2:

Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

Hint 3:

Topological sort could also be done via BFS.

Explanation 1

We can solve this problem by topological sort. First, loop through the edges, create an adjacent list which is prerequisite course points to target course. Also create an array inDegree[i] to record the number of prerequisite course that course i has.
Loop through all the courses, if course i doesn’t need any prerequisite, in other word, inDegree[i] is 0, then we push this course to the queue.
While the queue is not empty, we pop one course cur out. Put this course to the result list. Loop through this course’s neighbor course, and subtract each neighbor’s prerequisite or inDegree by 1. If any neighbor course’s inDegree is 0, then we push it to the queue.
If the result list has the size of numCourses, then we return this result list. Otherwise, we can’t finish all the course, so return an empty result.

Solution 1

func findOrder(numCourses int, prerequisites [][]int) []int {
    inDegree := make([]int, numCourses)
    adjLst := make([][]int, numCourses)

    for _, prereq := range prerequisites {
        target := prereq[0]
        pre := prereq[1]
        inDegree[target] += 1
        adjLst[pre] = append(adjLst[pre], target)
    }

    queue := make([]int, 0)

    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    res := make([]int, 0)

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        res = append(res, cur)
        for _, nextCourse := range adjLst[cur] {
            inDegree[nextCourse] -= 1
            if inDegree[nextCourse] == 0 {
                queue = append(queue, nextCourse)
            }
        }
    }

    if len(res) == numCourses {
        return res
    } else {
        return []int{}
    }
}

Explanation 2

We can also use DFS topological sort to solve this problem. First, create an adjacent list which is prerequisite course points to target course. In the main function, loop through all the courses. Each iteration, we pass the current course into the helper function.
In the helper function, we DFS the current course’s deepest target course, then push this deepest target course into the stack. At the end, we return the reverse stack’s courses as the result.
We also need to create an array visited to have cycle detection. For example, initially visited[i] = 0 means course i is unvisited; if visited[i] = -1 that means course i is visiting and not finish; if course[i] = 1 that means course i is finish visiting. If there’s a cycle, we return false from the helper function. In the main function, if the we got false from the helper function, then we return an empty result.

Solution 2

func findOrder(numCourses int, prerequisites [][]int) []int {
    adjLst := make([][]int, numCourses)

    for _, prereq := range prerequisites {
        target := prereq[0]
        pre := prereq[1]
        adjLst[pre] = append(adjLst[pre], target)
    }

    res := make([]int, 0)
    visited := make([]int, numCourses)

    for i := 0; i < numCourses; i++ {
        if !helper(i, adjLst, visited, &res) {
            return []int{}
        }
    }

    return res
}

func helper(curCourse int, adjLst [][]int, visited []int, res *[]int) bool {
    if visited[curCourse] == -1 { return false }
    if visited[curCourse] == 1 { return true }

    visited[curCourse] = -1
    for _, nextCourse := range adjLst[curCourse] {
        if !helper(nextCourse, adjLst, visited, res) { return false }
    }
    *res = append([]int{curCourse}, *res...)
    visited[curCourse] = 1
    return true
}

Add Binary

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn’t contain any leading zero.

Explanation

Similar to 2. Add Two Numbers. First, we need to create a stringbuilder res to hold the result. We need a pointer pointing at the end index of stringA, and another pointer pointing at the end index of stringB because we add these two numbers starting from the least significant digit.
While either of the pointer is not negative, We can create a sum to hold the sum of two digit each time we add, and initialize the this sum equal to carry, where carry initialize to 0 before we start calculating.
After adding two digits to the sum, now the result digit’s value will be sum % 2 and we added it to the stringbuilder, and carry will be sum / 2. Repeat this while loop.
Outside of the while loop, if the carry is not zero, then we append it to the res, and we reverse the res and return its string representation.

Solution

func addBinary(a string, b string) string {
    sb := strings.Builder{}
    i, j := len(a)-1, len(b)-1
    carry := 0

    for i >= 0 || j >= 0 {
        sum := carry
        if i >= 0 {
            sum += int(a[i] - '0')
            i -= 1
        }
        if j >= 0 {
            sum += int(b[j] - '0')
            j -= 1
        }
        sb.WriteString(strconv.Itoa(sum % 2))
        carry = sum / 2
    }

    if carry > 0 {
        sb.WriteString(strconv.Itoa(carry))
    }

    return reverse(sb.String())
}

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

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Explanation 1

Iterative method way. While the head is not NULL and head.val equals val, then we move head forward. If the head is NULL, then we return NULL.
Create a previous pointer pre and pre.next = head, and create a current pointer cur points to head. While cur is not NULL, we check if cur.val != val, then we update pre = cur. Else if cur.val == val, then we update pre.next = cur.next. Both condition, we update cur = cur.next.
At the end, we return head.

Solution 1

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    for head != nil && head.Val == val { head = head.Next }
    if head == nil { return head }
    pre := &ListNode{-1, head}
    cur := head

    for cur != nil {
        if cur.Val == val {
            pre.Next = cur.Next
        } else {
            pre = cur
        }
        cur = cur.Next
    }

    return head
}

Explanation 2

Recursive way. While the head is not NULL and head.val equals val, then we move head forward. If the head is NULL, then we return NULL.
Recursivly call the main function with head.next and the input val, then update head.next to this recursive function;s return value.
At the end, return head.

Solution 2

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    for head != nil && head.Val == val { head = head.Next }
    if head == nil { return head }
    head.Next = removeElements(head.Next, val)
    return head
}

Word Search

Given a 2D board and a word, find if the word exists in the grid.

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

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

Explanation

First, we can iterate the board and find the character that is matched with the first character of the word. Then, think of this character as the middle, we recursivly check its top, bottom, left, right element if match with the second character of the word.
Special case is we cannot use the same character twice, so we create a isUsed table that have the same size as the board. If the character is used, then we mark it as true in the isUsed table. Or if the current word match, then we mark the current word as a random character such as #, after the recursive function, we backtrack the current word to its original character.

Solution

func exist(board [][]byte, word string) bool {
    for r := 0; r < len(board); r++ {
        for c := 0; c < len(board[0]); c++ {
            if helper(board, word, r, c, 0) { return true }
        }
    }
    return false
}

func helper(board [][]byte, word string, r, c, curIdx int) bool {
    if curIdx == len(word) { return true }
    if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) { return false }
    if board[r][c] != word[curIdx] { return false }

    temp := board[r][c]
    board[r][c] = '#'

    res := helper(board, word, r-1, c, curIdx+1) || helper(board, word, r+1, c, curIdx+1) || helper(board, word, r, c-1, curIdx+1) || helper(board, word, r, c+1, curIdx+1)

    board[r][c] = temp
    return res
}

Week 4: July 22nd - July 28th

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Explanation 1

Similar to 102. Binary Tree Level Order Traversal, but this time we need to add value from left to right, in the next level, we add values from right to left. Then next level, add values from left to right, next level from right to left.
When the current level is from left to right, we can normally pop value from the beginning and add its child to the end (left child first). When the current level is from right to left, we pop values from the end and add its child (right child first) to the beginning.

Solution 1

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

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    leftToRight := true

    for len(queue) > 0 {
        sub := make([]int, 0)
        for i := len(queue)-1; i >= 0; i-- {
            if leftToRight {
                cur := queue[0]
                queue = queue[1:]
                sub = append(sub, cur.Val)
                if cur.Left != nil { queue = append(queue, cur.Left) }
                if cur.Right != nil { queue = append(queue, cur.Right) }
            } else {
                cur := queue[len(queue)-1]
                queue = removeLast(queue)
                sub = append(sub, cur.Val)
                if cur.Right != nil { queue = addFirst(queue, cur.Right) }
                if cur.Left != nil { queue = addFirst(queue, cur.Left) }
            }
        }

        res = append(res, sub)
        leftToRight = !leftToRight
    }

    return res
}

func removeLast(queue []*TreeNode) []*TreeNode {
    res := make([]*TreeNode, len(queue)-1)
    copy(res, queue[:len(queue)-1])
    return res
}

func addFirst(queue []*TreeNode, ele *TreeNode) []*TreeNode {
    return append([]*TreeNode{ele}, queue...)
}

Explanation 2

We can also use DFS to solve this problem. Start from level 0, if the current level is even number, then we add the current root value to the end of sublist res[level], else add it to the front of the sublist res[level].

Solution 2

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

func helper(root *TreeNode, level int, res *[][]int) {
    if root == nil { return }

    if len(*res) == level {
        *res = append(*res, []int{})
    }

    if level % 2 == 0 {
        (*res)[level] = append((*res)[level], root.Val)
    } else {
        (*res)[level] = append([]int{root.Val}, (*res)[level]...)
    }

    helper(root.Left, level+1, res)
    helper(root.Right, level+1, res)
}

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

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

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Explanation

This problem asks us to find the two numbers (let say a and b) that are appear only once and they are different. If we want to use the XOR method by 136. Single Number, we need to seperate these two numbers into two different groups then apply the XOR method.
If we XOR all the numbers in the array, then the result will be xo = a ^ b because all other numbers are the same and appear twice and they will eventually become zero. Now, we want to seperate the array into two groups. Note, the xo cannot be zero here since a and b are different. We can use a bit as a seperate point, which is the xo right most non-zero bit as a seperate point. Because a and b on that bit will have different value. Note, the seperate point number will be only that bit is 1, other bit are 0. For example 00100.
We use this seperate number (let say diff) to AND all the numbers in the array. If the current iterated number AND this seperate number equals 0, then it’s one group; else equal 1, will be another group, since a and b on that bit are different.
We can use the XOR method to find that appeared only once number in a group to find a, and use the same method to find b in antoher group.
How do we find diff? After we XOR all numbers in the array to get xo, we use the formula diff = ~(xo-1) & xo or diff = (-xo) & xo to get diff. For example, if xo is 101100, then it subtract one equals 101011, not 101011 equals 010100. Then 010100 AND 101100 becomes 000100, which has only the right most 1 bit of xo.

Solution

func singleNumber(nums []int) []int {
    xorRes := 0
    for _, num := range nums {
        xorRes ^= num;
    }
    lowSetBit := xorRes & (-xorRes)

    res := make([]int, 2)
    for _, num := range nums {
        if num & lowSetBit == 0 {
            res[0] ^= num
        } else {
            res[1] ^= num
        }
    }

    return res
}

All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

Explanation

We can solve this problem using DFS method.
The input is the adjacent list. In the main function, we create a result list, and a current path list, then pass the graph, the result list, the current path list, and the starting node 0 to the helper function.
Inside the helper function, we push the current node to the current path list. Then if the current node is the target node, we create a copy of the current path list and add to the result list. Else, we loop through the current node’s neighbors, and call the helper function recursively. At the end of the helper function, we need to backtrack to pop the last element we just added from the current path list.

Solution

func allPathsSourceTarget(graph [][]int) [][]int {
    res := make([][]int, 0)
    cur := make([]int, 0)
    helper(graph, &res, cur, 0)
    return res;
}

func helper(graph [][]int, res *[][]int, cur []int, node int) {
    cur = append(cur, node)
    if node == len(graph) - 1 {
        sub := make([]int, len(cur))
        copy(sub, cur)
        *res = append(*res, sub)
    } else {
        for _, neighbor := range graph[node] {
            helper(graph, res, cur, neighbor)
        }
    }
    cur = cur[:len(cur)-1]
}

Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

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

Example 2:

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

Note:

This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?

Explanation

Similar to 153. Find Minimum in Rotated Sorted Array, this time there’s possibility that nums[left] == nums[mid] == nums[right], and we don’t know which side of the array need to be check.
To solve this, we can simply apply the same method as before, but this time, we add one more if condition, if nums[right] == nums[mid], then we move right to the left 1 step. This method doesn’t affect our solution since we just remove one repeated number.

Solution

func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right - left) >> 1
        if nums[mid] < nums[right] {
            right = mid
        } else if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right -= 1
        }
    }

    return nums[left]
}

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
             Since 2 has only one digit, return it.

Follow up:

Could you do it without any loop/recursion in O(1) runtime?

Hint 1:

A naive implementation of the above process is trivial. Could you come up with other methods?

Hint 2:

What are all the possible results?

Hint 3:

How do they occur, periodically or randomly?

Hint 4:

You may find this Wikipedia article useful.

Explanation

From the below pattern, we know the result will be num % 9. Special case is if num = 9, then the remainder will be 0. To avoid that, we can use a new formula (num-1) % 9 + 1. Now the special case is num = 0. In C++ and Java, -1 % 9, the quotient is 0, remainder is -1. But in Python, the quotient is -1, remainder is 8. So we can first check if num = 0, else apply the new formula.

 num -> res
-> 1
-> 2
-> 3
-> 4
-> 5
-> 6
-> 7
-> 8
-> 9
-> 1
-> 2
-> 3
-> 4
-> 5
-> 6
-> 7
-> 8
-> 9
-> 1
-> 2

Solution

func addDigits(num int) int {
    if num == 0 {
        return 0
    } else {
        return (num - 1) % 9 + 1
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Explanation

Similar to 105. Construct Binary Tree from Preorder and Inorder Traversal, this time, we know the root node is the end element of postorder array, and we can find the root element in the inorder array, then we can know the range of leftsubtree and rightsubtree. One example is below:

 Inorder:　　 　11　　4　　5　　13　　8　　9

 Postorder:　　11　　4　　13　　9　　8　　5　　

 11　　4　　5　　13　　8　　9　　　　　　=>　　　　　　　　　 5

 11　　4　　13　　9　　8　　5　　　　　　　　　　　　　　　　/　　\

 11　　4　　 　　13　　 8　　9　　　　　　=>　　　　　　　　　5

 11　　4　　　　 13　　 9　　8　　　　　　　　　　　　　　　/　　\

 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  4　　　8

 11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　　　　5

 11　　　　　　 13　　　　9　　　　 　　　　　　　　　　　　 /　　\

 　　　　　　　　　　　　　　　　　 　　　　　　　　　　　   4　　　8

 　　　　　　　　　　　　　　　　　　　　　　　　　　　　 /　　　 /     \

 　　　　　　　　　　　　　　　　　　　　　　　　　　　  11　　  13　　  9

Using the while loop to find the root value’s index in inorder[] in each recursion call make the time complexity be $O(n^2)$. We can reduce the time complexity to $O(n)$ by using a HashMap to record the key is the element, value is the element’s index.
We can also remove the postStart since we only need to find the root from postorder[] by using postEnd.

Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    hm := make(map[int]int)
    for i := range inorder {
        hm[inorder[i]] = i
    }
    return helper(inorder, postorder, 0, len(inorder)-1, len(postorder)-1, hm)
}

func helper(inorder []int, postorder []int, left, right, rootIdx int, hm map[int]int) *TreeNode {
    if left > right { return nil }
    root := &TreeNode{Val: postorder[rootIdx]}
    if left == right { return root }

    inorderRootIdx := hm[postorder[rootIdx]]
    root.Left = helper(inorder, postorder, left, inorderRootIdx-1, rootIdx-(right - inorderRootIdx + 1), hm)
    root.Right = helper(inorder, postorder, inorderRootIdx+1, right, rootIdx-1, hm)

    return root
}

Task Scheduler

You are given a char array representing tasks CPU need to do. It contains capital letters A to Z where each letter represents a different task. Tasks could be done without the original order of the array. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

You need to return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

Explanation

In this problem, n means two same tasks must have n different tasks or idle in between, so we first seperate the most frequent tasks, then assign the less frequent tasks in the gap of the most frequent tasks.

For example 1, if we have tasks = [AAAABBBEEFFGG] and n=3. First, we will seperate the A since it has the highest frequency, and we fill 3 space in between.

 A---A---A---A   (seperat A with n space in between)
 AB--AB--AB--A   (add B)
 ABE-ABE-AB--A   (add E)
 ABEFABE-ABF-A   (add F, fill it evently)
 ABEFABEGABFGA   (add G)

Another example 2, we have tasks = [ACCCEEE] and n=2. Since C and E has the same frequency 3, we can think of CE as a whole, and add n - (mxCnt - 1) = 2 - (2-1) = 1 space in between.
1
2
CE-CE-CE CEACE-CE (add A)
Notice from the above two examples, we have maxFreq-1 groups, and append the letter that has the most frequency at the end.
From the above example1, we consider A--- as one group, it appears 3=maxFreq-1=4-1 times, then add the last A at the end. The group size is 4=n+1=3+1.
From the above example2, the group CE- appears 2=maxFreq=3-1 times, then we add the last CE at the end. The group size is 3=n+1=2+1.
One corner case is n = 0. For example, we have tasks = [AAABBB] and n=0. The maximum frequency is 3, so we have 2=maxFreq-1=3-1 groups like ABAB. The group size is not n+1=0+1=1, instead, it should be 2 in this case. In other words, if the n=0, then any tasks can next to each other, so the result will be at least equals to the tasks.length.

Solution

func leastInterval(tasks []byte, n int) int {
    freq := make([]int, 26)
    maxFreq := 0
    for _, task := range tasks {
        freq[task - 'A'] += 1
        maxFreq = max(maxFreq, freq[task - 'A'])
    }

    maxFreqCnt := 0
    for _, f := range freq {
        if f == maxFreq {
            maxFreqCnt += 1
        }
    }

    numGroup := maxFreq - 1
    groupSize := n + 1

    return max(len(tasks), groupSize * numGroup + maxFreqCnt)
}

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

Week 5: July 29th - July 31st

Best Time to Buy and Sell Stock with Cooldown

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Explanation

We can represent this problem in 3 states.

    hold
    ----
    |  |
    v  |  hold
     S1 <------S3
       \       ^
    Buy \     /
         \   / Sell
          v /
          S2
         |  ^
         |__|
         hold

We can know that S1 can be only obtained by hold at itself or hold from S2; S2 can be only obtained by rest at itself or buy from S1; S3 can be obtained only by sell stock from S2.

So we will have:

 S1[i] = Math.max(S1[i-1], S3[i-1]);
 S2[i] = Math.max(S2[i-1], S1[i-1]-prices[i]);
 S3[i] = S2[i-1] + prices[i];

We know that S2 will never be the largest state, because it buy(cost money), and if it hold, it will stay the same and also smaller than S1. So, the maximum state must be either S1 or S3.

Base case

 s0[0] = 0; // At the start, we don't have any stock if we just rest
 s1[0] = -prices[0]; // After buy, we should have -prices[0] profit.
 s2[0] = INT_MIN; // At the start, we can't reach this state, can set to 0 or INT_MIN

Solution

func maxProfit(prices []int) int {
    if len(prices) <= 1 { return 0 }
    S1, S2, S3 := 0, -prices[0], 0
    for i := 1; i < len(prices); i++ {
        preS1 := S1
        S1 = max(S1, S3)
        S3 = S2 + prices[i]
        S2 = max(S2, preS1 - prices[i])
    }
    return max(S1, S3)
}

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

Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Explanation

When the question asks to return all different situation, we can usually use recursion to solve it.
First, we can think of how we solve it in a manual way. From the above example 1, we will find if any string from the wordDict can be the beginning of the s. We can check it using the length of string and if s[0:stringFromArr.length] == stringFromArr, then the stringFromArr can be the beginning of s. In example1, we find out cat and cats both can be the beginning of s. If we choose cat, then s becomes “sanddog”. We again find the beginning string from the wordDict, then we find out “sand” also from the beginning of the string, then s becomes “dog”, and it also inside the wordDict, this mean we find out result string.
This method can use recursion to solve it because when s is changed, the way to solve is the same. This is a brute force way, and we are doing repeated work. For example, when s becomes “sanddog”, we know it can split to “sand” and “dog”. If we face “sanddog” again, then we don’t want to recursive to solve again, we want to save this result. Because we have to save s and the its splitted strings at the same time, then we can use a hashmap<String, List<String>>.
In the recursion function, the base case will be if the map has key, then we just return the value.
In summary, we iterate the wordDict array, and check if a string word can be the beginning of s, then we pass its following string to the recursive function and save the result array as remain. Then, we iterate each result string in remain and concatnate word to form one string, and push this string to the result array.

Solution

func wordBreak(s string, wordDict []string) []string {
    hm := make(map[string][]string)
    return helper(s, wordDict, hm)
}

func helper(s string, wordDict []string, hm map[string][]string) []string {
    if _, ok := hm[s]; ok {
        return hm[s]
    }
    res := make([]string, 0)
    for _, word := range wordDict {
        if strings.Index(s, word) == 0 {
            if s == word {
                res = append(res, s)
            } else {
                remain := helper(s[len(word):], wordDict, hm)
                for _, str := range remain {
                    res = append(res, word + " " + str)
                }
            }
        }
    }
    hm[s] = res
    return res
}

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Hint 1:

To reach nth step, what could have been your previous steps? (Think about the step sizes)

Explanation

We can use dynamic programming to solve this problem. The base case is when n = 0, res = 0; when n = 1, res = 1; when n = 2, res = 2.
The way to reach the current i step is equal to the way to reach i-1 step plus the way to reach i-2 step.

Solution

func climbStairs(n int) int {
    if n <= 2 { return n }
    n1, n2 := 1, 2
    for i := 3; i <= n; i++ {
        n1, n2 = n2, n1+n2
    }
    return n2
}