LeetCode Freedom Flashcards

Question

# @572 Subtree of Another Tree Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself. Ex1: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true Ex2: Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false | Can have nodes with the same value in a tree. ## Footnote The number of nodes in the root tree is in the range [1, 2000]. The number of nodes in the subRoot tree is in the range [1, 1000]. -10^4 <= root.val <= 10^4 -10^4 <= subRoot.val <= 10^4

Answer 1

Do the following recursively until the base case: Check if a root and a subRoot is a the same tree. If the root is not the same tree as the subRoot, check if any of the children is the same tree as the subRoot. ``` func isSubtree(root *TreeNode, subRoot *TreeNode) bool { if root == nil && subRoot == nil { return true } if root == nil && subRoot != nil { return false } if root != nil && subRoot == nil { return false } return isSameTree(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot) } func isSameTree(p, q *TreeNode) bool { if p == nil && q == nil { return true } if p == nil && q != nil { return false } if p != nil && q == nil { return false } return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right) } ```

Answer 2

Utilize the traits of a **binary tree**. If p and q are both smaller than the root, the lowest common ancestor is on the left side. If p and q are both greater than the root, the lowest common ancestor is on the right side. Otherwise, it is the root. ``` func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { switch { case (p.Val < root.Val && q.Val > root.Val), (p.Val > root.Val && q.Val < root.Val): return root case p.Val == root.Val: return p case q.Val == root.Val: return q case p.Val < root.Val && q.Val < root.Val: return lowestCommonAncestor(root.Left, p, q) case p.Val > root.Val && q.Val > root.Val: return lowestCommonAncestor(root.Right, p, q) default: return nil } } ``` ## Footnote The Lowest Common Ancestor happens when p and q are on separate sides, or either p or q equals to the root.

Answer 3

**Breadth First Search**. Use a **queue** to go through every possible node. Use the queue size to know the number of nodes in the current level. First Level: [3], queueLength = 1, levelSize = 1 Do once: 1. Dequeue once and enqueue the children. => [9, 20] Second Level: [9, 20], queueLength = 2, levelSize =2 Do twice: 1.Dequeue once and enqueue the children. =>[20, 4, 6] 2.Dequeue once and enqueue the children. => [4, 6, 15,7] Third Level: Do four times: 1. Dequeue once and enqueue the children. =>[6, 15, 7] 2. Dequeue once and enqueue the children. =>[15, 7] 3. Dequeue once and enqueue the children. =>[7] 4. Dequeue once and enqueue the children. =>[] ``` func levelOrder(root *TreeNode) [][]int { result := make([][]int, 0) if root == nil { return result } // Use a queue for bfs q := make(queue, 0) q.Enqueue(root) var first *TreeNode for len(q) != 0 { // Determine the number of nodes in the current level (levelSize) by using len(q). levelSize := len(q) currLevel := make([]int, 0, levelSize) // Iterate over exactly those nodes in the current level without processing nodes from subsequent levels. // Once we have processed all nodes at the current level, we know that we've finished that level and can move on to the next level for i := 0; i < levelSize; i++ { first = q.Dequeue() currLevel = append(currLevel, first.Val) if first.Left != nil { q.Enqueue(first.Left) } if first.Right != nil { q.Enqueue(first.Right) } } result = append(result, currLevel) } return result } type queue []*TreeNode func (q *queue) Enqueue(element *TreeNode) { *q = append(*q, element) } func (q *queue) Dequeue() *TreeNode { if len(*q) != 0 { first := (*q)[0] (*q) = (*q)[1:] return first } return nil } ``` ## Footnote Track level size to know when to stop in the queue.

Answer 4

**Breadth First Search**. Get nodes in every level. The right most element of every level is the right side view. ``` func rightSideView(root *TreeNode) []int { sideView := make([]int, 0) if root == nil { return sideView } levels := make([][]int, 0) q := []*TreeNode{root} var levelSize int var first *TreeNode var currLevel []int for len(q) != 0 { levelSize = len(q) currLevel = make([]int, 0, levelSize) for i := 0; i < levelSize; i++ { first = q[0] currLevel = append(currLevel, first.Val) q = q[1:] if first.Left != nil { q = append(q, first.Left) } if first.Right != nil { q = append(q, first.Right) } } levels = append(levels, currLevel) } for _, level := range levels { sideView = append(sideView, level[len(level) - 1]) } return sideView } ```

Answer 5

Use DFS (**Depth First Search**) to traverse the tree, and constantly keep track of the **current path maximum** at every recursion level. ``` func goodNodes(root *TreeNode) int { count := 0 var dfs func(node *TreeNode, localMax int) dfs = func(node *TreeNode, currMax int){ if node == nil { return } if node.Val >= currMax { currMax = node.Val count++ } dfs(node.Left, currMax) dfs(node.Right, currMax) } dfs(root, root.Val) return count } ```

Answer 6

Keep **count** when using InOrder Traversal. When count reaches k, return the value of the node. * Use an array to store k elements before k and return the last element ``` func kthSmallest(root *TreeNode, k int) int { resultArr := make([]int, 0, k) count := 0 var inOrder func(node *TreeNode) inOrder = func(node *TreeNode) { if node == nil { return } if count < k { inOrder(node.Left) } if count < k { resultArr = append(resultArr, node.Val) count++ } if count < k { inOrder(node.Right) } } inOrder(root) return resultArr[len(resultArr)-1] } ``` * Keep count and a parameter result (saved the array) ``` func kthSmallest(root *TreeNode, k int) int { var result int count := 0 var inOrder func(node *TreeNode) inOrder = func(node *TreeNode) { if node == nil || count >= k { return } inOrder(node.Left) count++ if count == k { result = node.Val return } inOrder(node.Right) } inOrder(root) return result } ``` * Use channels to keep count, read only k - 1 elements from channel. ``` func kthSmallest(root *TreeNode, k int) int { // Inorder and read from channel c := make(chan int) go inOrderWalk(root, c) for i := 0; i < k - 1; i++ { <-c } return <-c } func inOrderWalk(node *TreeNode, c chan int){ if node == nil { return } inOrderWalk(node.Left, c) c <- node.Val inOrderWalk(node.Right, c) } ``` ## Footnote InOrder Traversal: **Left** -> **Root** -> **Right**

Answer 7

Use the traits of a binary search tree. Carry **the lower and upper bound** for each node when validating. ``` func isValidBST(root *TreeNode) bool { if root == nil { return true } var validate func(node *TreeNode, lower int, upper int) bool validate = func(node *TreeNode, lower int, upper int) bool { if node == nil { return true } if node.Val > lower && node.Val < upper { // Update upper for left and update lower for right return validate(node.Left, lower, node.Val) && validate(node.Right, node.Val, upper) } return false } maxInt := int(^uint(0) >> 1) minInt := -maxInt - 1 return validate(root, minInt, maxInt) } ``` ## Footnote For a Binary Search Tree, a left child's value would be at -INF < node.Left < node.Val, a right child's value would be at node.Val < node.Right < INF

Answer 8

**Depth First Search** and **Dynamic Programming**. PathSum = node.Val + maxLeftPath +maxRightPath. maxLeftPath is the maximum sum for the left path. maxRightPath is the maximum sum for the right path. Compare all the way down using **DFS** since maxPathSum might not happen at root (could happen anywhere). Use a **DP map** that stores the maximum left or right sum to avoid repeated calculation on sum. ``` func maxPathSum(root *TreeNode) int { result := -int(^uint(0)>>1) - 1 dp := make(map[*TreeNode]int) var pathMax func(node *TreeNode) int pathMax = func(node *TreeNode) int { if node == nil { return 0 } var result int if val, ok := dp[node]; !ok { result = node.Val leftPathMax := pathMax(node.Left) rightPathMax := pathMax(node.Right) if max(leftPathMax, rightPathMax) >= 0 { result += max(leftPathMax, rightPathMax) } dp[node] = result } else { result = val } return result } var dfs func(node *TreeNode) dfs = func(node *TreeNode) { if node == nil { return } leftPathMax := max(0, pathMax(node.Left)) rightPathMax := max(0, pathMax(node.Right)) result = max(result, node.Val + leftPathMax + rightPathMax) dfs(node.Left) dfs(node.Right) } dfs(root) return result } ``` ## Footnote Break the problem down and find the base problem.

Answer 9

Find the root location and divide the preorder and inorder array to three parts: * The root **preorder[0]**. * The sub-array of left sub-tree **buildTree(preorder[1:rootLocation+1], inorder[:rootLocation])**. * The sub-array of right sub-tree **buildTree(preorder[rootLocation+1:], inorder[rootLocation + 1:])**. ``` func buildTree(preorder []int, inorder []int) *TreeNode { // Base case. if len(preorder) == 0 { return nil } // The first value of preorder is always the root of the result. // Find where the root is at in the inorder array. The left part is the left child, right part is the right child. var rootLocation int for inorder[rootLocation] != preorder[0] { rootLocation++ } return &TreeNode{ Val: preorder[0], Left: buildTree(preorder[1:rootLocation+1], inorder[:rootLocation]), Right: buildTree(preorder[rootLocation+1:], inorder[rootLocation + 1:]), } } ``` ## Footnote Inorder is left -> root -> right. Preorder is root -> left -> right

Answer 10

Create a minHeap. Compare the head with the new value. If the new value is greater than the head of the min heap, remove the head (which is the smallest value in the heap). Insert the new value to the heap. ``` type KthLargest struct { MinHeap []int HeapSize int K int } func Constructor(k int, nums []int) KthLargest { sort.Ints(nums) var minHeap []int var heapSize int if len(nums) == 0 { minHeap = make([]int, 0) heapSize = 0 } else if len(nums) < k { minHeap = nums heapSize = len(nums) } else { minHeap = nums[len(nums)-k:] heapSize = k } return KthLargest{ MinHeap: minHeap, HeapSize: heapSize, K: k, } } func ParentIdx(childIdx int) int { return (childIdx - 1) / 2 } func LeftChildIdx(parentIdx int) int { return parentIdx<<1 + 1 } func RightChildIdx(parentIdx int) int { return (parentIdx + 1) << 1 } func (this *KthLargest) MinHeapify(idx int) { lowestIdx := idx leftChildIdx := LeftChildIdx(idx) rightChildIdx := RightChildIdx(idx) if leftChildIdx < this.HeapSize && this.MinHeap[leftChildIdx] < this.MinHeap[lowestIdx] { lowestIdx = leftChildIdx } if rightChildIdx < this.HeapSize && this.MinHeap[rightChildIdx] < this.MinHeap[lowestIdx] { lowestIdx = rightChildIdx } if lowestIdx != idx { this.MinHeap[idx], this.MinHeap[lowestIdx] = this.MinHeap[lowestIdx], this.MinHeap[idx] this.MinHeapify(lowestIdx) } } func (this *KthLargest) Add(val int) int { if this.HeapSize < this.K { this.Insert(val) } else if this.HeapSize == this.K && val > this.MinHeap[0] { this.Delete() this.Insert(val) } return this.MinHeap[0] } func (this *KthLargest) Insert(val int) { this.HeapSize++ this.MinHeap = append(this.MinHeap, val) for parentIdx := len(this.MinHeap) - 1; parentIdx >= 0; parentIdx = ParentIdx(parentIdx) { this.MinHeapify(parentIdx) if parentIdx == 0 { return } } } func (this *KthLargest) Delete() { this.MinHeap[0], this.MinHeap[len(this.MinHeap)-1] = this.MinHeap[len(this.MinHeap)-1], this.MinHeap[0] this.MinHeap = this.MinHeap[:len(this.MinHeap)-1] this.HeapSize-- this.MinHeapify(0) } /** * Your KthLargest object will be instantiated and called as such: * obj := Constructor(k, nums); * param_1 := obj.Add(val); */ ```

Answer 11

Backtracking. Use every possible element in the array. Store the susbset and pass it on the the next backtracking function. Change dimension by moving the startIdx in the array, this naturally doesn't look back. ``` func subsets(nums []int) [][]int { result := [][]int{[]int{}} var backtrack func(subset []int, current int) backtrack = func(subset []int, current int){ if len(subset) == len(nums) { return } // Create a copy of the subset so that we don't update the underlying slices within result temp := make([]int, len(subset)) copy(temp, subset) temp = append(temp, nums[current]) result = append(result, temp) // Change dimension // This naturally doesn't look back, won't pick a used one for current = current + 1;current <= len(nums) - 1; current++ { backtrack(temp, current) } } for start := range nums { backtrack([]int{}, start) } return result } ```

Answer 12

**Backtracking.** Go through every scenario, elminate the one that doesn't fit the condition, in this case it is when the local sum is greater than the target. Append to combination when the local sum is equal to the target. ``` func combinationSum(candidates []int, target int) [][]int { combinations := make([][]int, 0) var backtrack func(currentCandidates []int, currSum int, start int) backtrack = func(currentCandidates []int, currSum int, start int) { currSum += candidates[start] currentCandidates = append(currentCandidates, candidates[start]) if currSum > target { return } else if currSum == target { combinations = append(combinations, currentCandidates) return } else { // keep on backtracking when currSum < target temp := make([]int, len(currentCandidates)) copy(temp, currentCandidates) for i := start; i < len(candidates); i++ { backtrack(temp, currSum, i) } } } for i := range candidates { backtrack([]int{}, 0, i) } return combinations } ```

Answer 13

Backtracking. Search every adjacent board blocks. **Mark blocks that have already been to "*" and restore it later**. Use **word indexing** for comparison (If we use string comparison it takes too long). ``` func exist(board [][]byte, word string) bool { rows, columns := len(board), len(board[0]) found := false var dfs func(row, col, idx int) dfs = func(row, col, idx int){ // 1. Out of bound if row < 0 || row >= rows || col < 0 || col >= columns { return } // 2. Invalid element if board[row][col] != word[idx] { return } // 3. If passed if board[row][col] == '*' { return } // 4. Word Found if board[row][col] == word[idx] && idx == len(word) - 1 { found = true return } temp := board[row][col] board[row][col] = '*' dfs(row - 1, col, idx + 1) dfs(row + 1, col, idx + 1) dfs(row, col - 1, idx + 1) dfs(row, col + 1, idx + 1) board[row][col] = temp } for row := 0; row < rows; row ++ { for col := 0; col < columns; col ++ { k := 0 // start index dfs(row, col, k) } } return found } ```

Answer 14

Create a **MinHeap** of size k. **The kth largest is the head of the MinHeap**. Insert when the size is smaller than k or the new element is greater than the head. ``` func findKthLargest(nums []int, k int) int { mh := New(k) for _, num := range nums { if mh.HeapSize < mh.K { mh.Insert(num) continue } if num > mh.Heap[0] && mh.HeapSize == mh.K { mh.Delete() mh.Insert(num) } } return mh.Heap[0] } type MinHeap struct { Heap []int HeapSize int K int } func New(k int) *MinHeap { return &MinHeap{ Heap: make([]int, 0), HeapSize: 0, K: k, } } func ParentIdx(childIdx int) int { return (childIdx - 1) / 2 } func LeftChildIdx(parentIdx int) int { return (parentIdx << 1) + 1 } func RightChildIdx(parentIdx int) int { return (parentIdx + 1) << 1 } func (m *MinHeap) MinHeapify(idx int) { lowest := idx leftChildIdx := LeftChildIdx(idx) rightChildIdx := RightChildIdx(idx) if leftChildIdx < m.HeapSize && m.Heap[leftChildIdx] < m.Heap[lowest] { lowest = leftChildIdx } if rightChildIdx < m.HeapSize && m.Heap[rightChildIdx] < m.Heap[lowest] { lowest = rightChildIdx } if lowest != idx { m.Heap[idx], m.Heap[lowest] = m.Heap[lowest], m.Heap[idx] m.MinHeapify(lowest) } } // Delete removes the head from the MinHeap. func (m *MinHeap) Delete() { if m.HeapSize > 0 { // Update size. m.HeapSize-- // Swap the head with the end. m.Heap[0], m.Heap[len(m.Heap)-1] = m.Heap[len(m.Heap)-1], m.Heap[0] // Trim the end. m.Heap = m.Heap[:len(m.Heap)-1] // MinHeapify the root. m.MinHeapify(0) } } // Insert adds an element into the MinHeap. func (m *MinHeap) Insert(val int) { if m.HeapSize < m.K { m.HeapSize++ m.Heap = append(m.Heap, val) for parent := ParentIdx(len(m.Heap) - 1); parent >= 0; parent = ParentIdx(parent) { m.MinHeapify(parent) if parent == 0 { break } } } } ```

Answer 15

Create a **MaxHeap** with a size len(stones). Compare the two left most stones (by deleting twice), and insert the remains back to the max heap. Do it repeatedly until there's 1 or none elements left in the heap. ``` func lastStoneWeight(stones []int) int { var h1, h2, remain int mh := BuildMaxHeap(stones) for mh.HeapSize > 1 { h1, h2 = mh.Delete(), mh.Delete() remain = Compare(h1, h2) if remain != 0 { mh.Insert(remain) } } if mh.HeapSize == 0 { return 0 } return mh.Heap[0] } func Compare(a, b int) int { var left int switch { case a > b: left = a - b case b > a: left = b - a } return left } func ParentIdx(childIdx int) int { return (childIdx - 1) / 2 } func LeftChildIdx(parentIdx int) int { return (parentIdx << 1) + 1 } func RightChildIdx(parentIdx int) int { return (parentIdx + 1) << 1 } type MaxHeap struct { Heap []int HeapSize int } func BuildMaxHeap(nums []int) *MaxHeap { mh := &MaxHeap{ Heap: nums, HeapSize: len(nums), } for i := mh.HeapSize / 2; i >= 0; i-- { mh.MaxHeapify(i) } return mh } func (m *MaxHeap) MaxHeapify(idx int) { largest := idx leftChildIdx := LeftChildIdx(idx) rightChildIdx := RightChildIdx(idx) if leftChildIdx < m.HeapSize && m.Heap[leftChildIdx] > m.Heap[largest] { largest = leftChildIdx } if rightChildIdx < m.HeapSize && m.Heap[rightChildIdx] > m.Heap[largest] { largest = rightChildIdx } if largest != idx { m.Heap[idx], m.Heap[largest] = m.Heap[largest], m.Heap[idx] m.MaxHeapify(largest) } } func (m *MaxHeap) Delete() int { var head int if m.HeapSize > 0 { head = m.Heap[0] m.Heap[0], m.Heap[len(m.Heap)-1] = m.Heap[len(m.Heap)-1], m.Heap[0] m.HeapSize-- m.Heap = m.Heap[:len(m.Heap)-1] m.MaxHeapify(0) } return head } func (m *MaxHeap) Insert(val int) { m.HeapSize++ m.Heap = append(m.Heap, val) for parent := ParentIdx(len(m.Heap) - 1); ; parent = ParentIdx(parent) { m.MaxHeapify(parent) if parent == 0 { break } } } ```

Answer 16

* **MaxHeap** that removes and add according to the logic(complicated, not recommended) * **Greedy**. The least interval is determined by the frequency(**maxFrequency**) element that occurs the most. There might be multiple elements that have maximum frequency(**elementsThatHaveMaxFrequency**).The Minimum require time can be calculated by function** (maxFrequency - 1) * (n + 1) + elementsThatHaveMaxFrequency**. Example: A = 5, B = 2, C = 1, n = 2 |---| --> This here is n + 1 A _ _ A _ _ A _ _ A _ _ A |<------------------- >| --> (maxFrequency - 1) * (n+ 1) Since the tail element doesn't need to add any more intervals, we greedily use (maxFrequency - 1) * (n+ 1). Add the tail elements, for this case it's A as the tail element (Which is the count of most occured element). Example2: A=5, B = 5, n = 3 A _ _ _ A _ _ _ A _ _ _ A _ _ _ A _ B _ _ _ B _ _ _ B _ _ _ B _ _ _ B |<---------------------------->| --> (maxFrequency - 1) * (n+ 1) || -> The count of two most elements. ``` func leastInterval(tasks []byte, n int) int { var maxFrequency, elementsThatHaveMaxFrequency int frequencyArray := [26]int{} for _, task := range tasks { frequencyArray[task-'A']++ maxFrequency = max(maxFrequency, frequencyArray[task-'A']) } for _, frequencyCount := range frequencyArray { if frequencyCount == maxFrequency { elementsThatHaveMaxFrequency++ } } // Greedy. 算出最少需要多少格剩下就是隨便塞。 // n + 1 indicates interval + 1 element (which is where the maxFrequency occur). lengthWithoutLast := (maxFrequency - 1) * (n + 1) // len(tasks) is where n(interval) = 0. return max(len(tasks), lengthWithoutLast + elementsThatHaveMaxFrequency) } ``` ## Footnote Greedy. 算出最少需要多少格剩下就是隨便塞。

Answer 17

Create a MaxHeap that stores and update when input new coordinate. Add coordinate to heap only when the heap size is smaller than k or when the heap is full and the new coordinate distance is closer to origin. ``` func kClosest(coordinates [][]int, k int) [][]int { mh := New(k) var point Point for _, coordinate := range coordinates { point = Point{ Coordinate: coordinate, DistanceSquared: coordinate[0]*coordinate[0] + coordinate[1]*coordinate[1], } if mh.HeapSize < mh.K || point.DistanceSquared < mh.Head() { mh.Add(point) } } result := make([][]int, 0) for _, p := range mh.Points { result = append(result, p.Coordinate) } return result } type Point struct { Coordinate []int DistanceSquared int } // Use a MaxHeap type MaxHeap struct { Points []Point HeapSize int K int } func ParentIdx(childIdx int) int { return (childIdx - 1) / 2 } func LeftChildIdx(parentIdx int) int { return (parentIdx << 1) + 1 } func RightChildIdx(parentIdx int) int { return (parentIdx + 1) << 1 } func New(k int) *MaxHeap { return &MaxHeap{ Points: make([]Point, 0), HeapSize: 0, K: k, } } func (m *MaxHeap) MaxHeapify(idx int) { largest := idx leftChildIdx := LeftChildIdx(idx) rightChildIdx := RightChildIdx(idx) if leftChildIdx < m.HeapSize && m.Points[leftChildIdx].DistanceSquared > m.Points[largest].DistanceSquared { largest = leftChildIdx } if rightChildIdx < m.HeapSize && m.Points[rightChildIdx].DistanceSquared > m.Points[largest].DistanceSquared { largest = rightChildIdx } if largest != idx { m.Points[idx], m.Points[largest] = m.Points[largest], m.Points[idx] m.MaxHeapify(largest) } } func (m *MaxHeap) Head() int { if len(m.Points) > 0 { return m.Points[0].DistanceSquared } return int(math.Inf(1)) } func (m *MaxHeap) Add(point Point) { if m.HeapSize == m.K { // Heap full. m.Delete() } m.Points = append(m.Points, point) m.HeapSize++ for parent := m.HeapSize - 1; parent != 0; parent = ParentIdx(parent) { m.MaxHeapify(ParentIdx(parent)) } } func (m *MaxHeap) Delete() { if len(m.Points) > 0 { m.Points[0], m.Points[m.HeapSize-1] = m.Points[m.HeapSize-1], m.Points[0] m.Points = m.Points[:m.HeapSize-1] m.HeapSize-- m.MaxHeapify(0) } } ```

Answer 18

**Backtracking**. The backtrack condition is where the length of the local permutation reaches the length of nums. **Copy** the local permutation and current number pool so that we don't modify the original number array. ``` func permute(nums []int) [][]int { result := make([][]int, 0) size := len(nums) var backtrack func(numbers []int, permutation []int) backtrack = func(numbers []int, permutation []int){ if len(permutation) == size { result = append(result, permutation) return } for i := range numbers { currentPermutation := make([]int, len(permutation)) copy(currentPermutation, permutation) currentPermutation = append(currentPermutation, numbers[i]) currentPool := make([]int, len(numbers)) copy(currentPool, numbers) currentPool = append(currentPool[:i], currentPool[i+1:]...) backtrack(currentPool, currentPermutation) } } backtrack(nums, []int{}) return result } ```

Answer 19

**Backtracking.** Sort the array first (so that we can compare duplicates). Note that we allow duplicates as different element in the result. Use a **decision tree** to think of the conditions to eliminate. ``` func combinationSum2(candidates []int, target int) [][]int { result := make([][]int, 0) sort.Ints(candidates) var backtrack func(start int, combination []int, currentSum int) backtrack = func(start int, combination []int, currentSum int) { if currentSum > target { return } if currentSum == target { result = append(result, combination) return } for i := start + 1; i < len(candidates); i++ { // The duplicate can only be at the start. if i-1 != start && candidates[i-1] == candidates[i] { continue } temp := make([]int, len(combination)) copy(temp, combination) temp = append(temp, candidates[i]) backtrack(i, temp, currentSum+candidates[i]) } } backtrack(-1, []int{}, 0) return result } ``` ## Footnote Use a decision tree for the thinking process.

Answer 20

**Backtracking.** Loop through the digit (which naturally doesn't look back) as start, and pick from the corresponding letter pool. ``` func letterCombinations(digits string) []string { letterMap := map[byte]string{ '2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz", } result := make([]string, 0) var backtrack func(currentString string, start int) backtrack = func(currentString string, start int) { if len(currentString) == len(digits) { result = append(result, currentString) return } if start >= len(digits) { return } letterPool := letterMap[digits[start]] for _, letter := range letterPool { backtrack(currentString+string(letter), start+1) } } for start := 0; start < len(digits); start++ { backtrack("", start) } return result } ``` ## Footnote Use a decision tree for the thinking process.

Answer 21

Backtracking. Append currSubset (which in Go we need to **copy**) at every function call. Eliminate duplicates by **sorting** the array first then compare the element with the previous element. If the element is the same, continue. ``` func subsetsWithDup(nums []int) [][]int { result := make([][]int, 0) sort.Ints(nums) var backtrack func(start int, currSusbset []int) backtrack = func(start int, currSubset []int) { // Copy the currSubset so that further modifications to the currSubset won't effect the result temp := make([]int, len(currSubset)) copy(temp, currSubset) result = append(result, temp) for i := start; i < len(nums); i++ { if i > start && nums[i] == nums[i-1] { continue } backtrack(i+1, append(currSubset, nums[i])) } } backtrack(0, []int{}) return result } ```

Answer 22

**Depth first search**. When we encounter a '1' and it is not connected with any other land, itself is a start of a new island, add one to count. Then **exhaust** every adjacent lands by marking them as '*'. ``` func numIslands(grid [][]byte) int { var islands int // Walk exhausts the island area. var walk func(row, col int, isConnected bool) walk = func(row, col int, isConnected bool){ // Out of range. if row < 0 || row >= len(grid) { return } if col < 0 || col >= len(grid[0]){ return } // Been there, mark as island. // If a land is marked, it's already considered as a part of one of the counted island. if grid[row][col] == '*' { return } // Is land. if grid[row][col] == '1' { if !isConnected { islands++ isConnected = true } grid[row][col] = '*' walk(row - 1, col, isConnected) walk(row + 1, col, isConnected) walk(row, col - 1, isConnected) walk(row, col + 1, isConnected) } isConnected = false } for row := range grid { for col := range grid[0] { walk(row, col, false) } } return islands } ```

Answer 23

Create an array that has 26 slots with the value of the children trie address. ``` type Trie struct { Children []*Trie IsEnd bool } // Constuctor is simply a wrapper. Normally I don't prefer returning a copy. func Constructor() Trie { return *New() } func New() *Trie { return &Trie{ Children: make([]*Trie, 26), IsEnd: false, } } func (this *Trie) Insert(word string) { var position byte temp := this for i := range word { position = word[i] - 'a' if temp.Children[position] == nil { temp.Children[position] = New() } temp = temp.Children[position] } temp.IsEnd = true } func (this *Trie) Search(word string) bool { var position byte temp := this for i := range word { position = word[i] - 'a' if temp.Children[position] == nil { return false } temp = temp.Children[position] } return temp.IsEnd } func (this *Trie) StartsWith(prefix string) bool{ var position byte temp := this for i := range prefix { position = prefix[i] - 'a' if temp.Children[position] == nil { return false } temp = temp.Children[position] } return true } ```

Answer 24

Depth First Search. If encounter land "1", exhaust all ajacent land and update the local area. After finishing with the node, compare to the max area. ``` func maxAreaOfIsland(grid [][]int) int { maxArea := 0 var walk func(row, col int, localArea *int) walk = func(row, col int, localArea *int) { if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] != 1 { return } (*localArea)++ grid[row][col] = -1 walk(row-1, col, localArea) walk(row+1, col, localArea) walk(row, col-1, localArea) walk(row, col+1, localArea) } for row := range grid { for col := range grid[0] { area := 0 // Initialize area for each new island walk(row, col, &area) // Update maxArea after traversing the island maxArea = max(maxArea, area) } } return maxArea } ```

Answer 25

* **Iterative**, traverse the graph first and create a clone map. Copy the cloned neighbors in the next loop. ``` /** * Definition for a Node. * type Node struct { * Val int * Neighbors []*Node * } */ func cloneGraph(node *Node) *Node { if node == nil { return nil } cloneMap := make(map[*Node]*Node) been := make(map[*Node]struct{}) queue := []*Node{node} for len(queue) != 0 { head := queue[0] if _, ok := been[head]; !ok { been[head] = struct{}{} cloneMap[head] = &Node{ Val: head.Val, Neighbors: make([]*Node, 0), } } queue = queue[1:] for _, neighbor := range head.Neighbors { if _, ok := been[neighbor]; !ok { queue = append(queue, neighbor) } } } been = make(map[*Node]struct{}) queue = []*Node{node} for len(queue) != 0 { head := queue[0] if _, ok := been[head]; !ok { been[head] = struct{}{} for _, neighbor := range head.Neighbors { cloneMap[head].Neighbors = append(cloneMap[head].Neighbors, cloneMap[neighbor]) } } queue = queue[1:] for _, neighbor := range head.Neighbors { if _, ok := been[neighbor]; !ok { queue = append(queue, neighbor) } } } return cloneMap[node] } ``` * **Recursive**. Clone the neighbors recursively. ``` /** * Definition for a Node. * type Node struct { * Val int * Neighbors []*Node * } */ func cloneGraph(node *Node) *Node { clonedNodes := make(map[*Node]*Node) var clone func(node *Node) *Node clone = func(node *Node) *Node { if node == nil { return nil } cloned, ok := clonedNodes[node] if ok { return cloned } clonedNode := &Node{ Val: node.Val, Neighbors: make([]*Node, 0), } clonedNodes[node] = clonedNode for _, neighborNode := range node.Neighbors { clonedNode.Neighbors = append(clonedNode.Neighbors, clone(neighborNode)) } return clonedNode } return clone(node) } ```

Answer 26

**Breath first search**. Use a **coordinates queue** to keep rotten oranges at every minute. Exhaust all rotten orange at from the queue and append adjacent contaminated rotten orange to the queue. The new queue length is the oranges we need to go through at the next minute. Do this till there's no more rotten orange in the queue. Since there might be fresh oranges that are never contaminated, we'll apply another check at the end. ``` func orangesRotting(grid [][]int) int { queue := make([][]int, 0) // Coordinates queue. // Find the rotten tomatos. for row := range grid { for col := range grid[0] { if grid[row][col] == 2 { queue = append(queue, []int{row, col}) } } } // Breadth first search, contaminate and push to queue. var contaminate func(coordinate []int) contaminate = func(coordinate []int) { row, col := coordinate[0], coordinate[1] if row > 0 && grid[row-1][col] == 1 { grid[row-1][col] = 2 queue = append(queue, []int{row - 1, col}) } if row < len(grid)-1 && grid[row+1][col] == 1 { grid[row+1][col] = 2 queue = append(queue, []int{row + 1, col}) } if col > 0 && grid[row][col-1] == 1 { grid[row][col-1] = 2 queue = append(queue, []int{row, col - 1}) } if col < len(grid[0])-1 && grid[row][col+1] == 1 { grid[row][col+1] = 2 queue = append(queue, []int{row, col + 1}) } } var count int // rottenOranges is the numbers of rotten orange within the minute. rottenOranges := len(queue) for rottenOranges != 0 { // Pop all rotten oranges from the current image. for i := 0; i < rottenOranges; i++ { head := queue[0] queue = queue[1:] contaminate(head) } // The current queue is the rotten orange at the next minute. rottenOranges = len(queue) if rottenOranges != 0 { count++ } } // Check if there's still fresh orange. for row := range grid { for col := range grid[0] { if grid[row][col] == 1 { return -1 } } } return count } ```

Answer 27

It's a Fibonacci List. * **Iterative Bottom Up Dynamic Programming**. ``` func climbStairs(n int) int { fibTable := make([]int, n) fibTable[0] = 1 if len(fibTable) > 1 { fibTable[1] = 2 } for i := 2; i < n; i++ { fibTable[i] = fibTable[i - 1] + fibTable[i - 2] } return fibTable[n - 1] } ``` ## Footnote It's a Fibonacci Series.

Answer 28

Dynamic Programming. Calculate the last two cost first. Then **look backwards**, cost is adding current cost with the minimum from the next two cost. Pick the minimum between the first or second cost in the table (since we can start at step 1 or step 2). ``` func minCostClimbingStairs(cost []int) int { stairs := len(cost) costTable := make([]int, stairs) costTable[stairs - 1] = cost[stairs - 1] costTable[stairs - 2] = min(cost[stairs - 1] + cost[stairs - 2], cost[stairs - 2]) for i := stairs - 3; i >= 0; i-- { costTable[i] = cost[i] + min(costTable[i+1], costTable[i+2]) } return min(costTable[0], costTable[1]) } ```

Answer 29

Dynamic Programming. Form a dp table that stores the local max amount. Every new house needs to adds onto the max amount from max(dpTable[i-2], dpTable[i-3]), meaning that we're checking which house has more amount, 2 house before or 3 house before. 1 _ 2 => 2 + 1 1, 8 _ 2 => 2 + 8 1, 3 , 100 _ 2 => 2 + 100 or 2 + 3, wouldn't jump directly to 1 because we miss a viable number 100 in between. ``` func rob(nums []int) int { houses := len(nums) dpTable := make([]int, houses) dpTable[0] = nums[0] maxAmount := dpTable[0] for i := 1; i < houses; i++ { switch i { case 1: dpTable[i] = nums[i] case 2: dpTable[i] = dpTable[0] + nums[i] default: dpTable[i] = nums[i] + max(dpTable[i-2], dpTable[i-3]) } maxAmount = max(maxAmount, dpTable[i]) } return maxAmount } ```

Answer 30

Since House[1] and House[n] are adjacent, they cannot be robbed together. Therefore, the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the **House Robber**, which is already been solved. ``` func rob(nums []int) int { houses := len(nums) if houses == 1 { return nums[0] } return max(houseRob(nums[:houses-1]), houseRob(nums[1:houses])) } func houseRob(nums []int) int { houses := len(nums) if houses == 0 { return 0 } dpTable := make([]int, houses) dpTable[0] = nums[0] maxAmount := dpTable[0] for i := 1; i < houses; i++ { switch i { case 1: dpTable[i] = nums[i] case 2: dpTable[i] = nums[i] + nums[i-2] default: dpTable[i] = nums[i] + max(dpTable[i-2], dpTable[i-3]) } maxAmount = max(maxAmount, dpTable[i]) } return maxAmount } ```

Answer 31

* Dynamic Programming( Slower ). Keep a table that stores whether the location can reach the end. ``` func canJump(nums []int) bool { canReachEnd := make([]bool, len(nums)) for i := len(nums) - 1; i >= 0; i-- { if i + nums[i] >= len(nums) - 1 { canReachEnd[i] = true } else { for step := 1; step <= nums[i]; step++ { if i + step < len(nums) { if canReachEnd[i + step] { canReachEnd[i] = true } } } } } return canReachEnd[0] } ```

Answer 32

Greedy. If the **carryOn** is negative, discard the previous array. Otherwise add the carryOn to the current number and compare to the previously-stored maxSum. It is greedy because there could be a negative carryOn in the middle of the array and might corrupt the previous max. We wouldn't know if there's another max after the negative carryOn, thus we should compare all the way to the end of the list. ``` func maxSubArray(nums []int) int { maxSum := -math.MaxInt carryOn := 0 for i := range nums { // max(carryOn, 0) checks if the carryOn is negative. // if the carryOn is negative, discard the carryOn. carryOn = max(carryOn, 0) + nums[i] maxSum = max(maxSum, carryOn) } return maxSum } ```

Answer 33

Greedy. Calculate the difference betweem cost and gas.(**gas-cost = diff**). If diff[i] is smaller or equal to 0, we can't start at that point. Check every diff[i] that is greater than 0. Every positive cost can possibly complete the circuit, thus we have to check every costs spent on each round, and if we reached the start and the total is still greater than 0, we have a valid answer. gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] diff = [-2, -2, -2, 3, 3] // The surplus of gas. ``` func canCompleteCircuit(gas []int, cost []int) int { diff := make([]int, len(gas)) for i := 0; i < len(diff); i++ { diff[i] = gas[i] - cost[i] } if len(diff) == 1 && diff[0] >= 0 { return 0 } for start := 0; start < len(diff); start++ { if diff[start] <= 0 { continue } total := diff[start] next := start for { next++ if next == len(gas) { next -= len(gas) } if next == start { break } total += diff[next] if total < 0 { break } } if total >= 0 { return start } } return -1 } ```

Answer 34

A palindrome has two forms: One with a single core 'aba' and another with a two-element core 'abba'. By expanding left and right around the cores, we can know if the expanded string is a palindrome. Compare all possible palindromes, return the longest palindromic substring. ``` func longestPalindrome(s string) string { if len(s) == 1 { return s } var longestSubstring string // Check palindrome that has core with 1 element. for i := 0; i < len(s); i++ { longestSubstring = maxSubstring(longestSubstring, string(s[i])) left, right := i-1, i+1 for left >= 0 && right <= len(s)-1 { if s[left] == s[right] { longestSubstring = maxSubstring(longestSubstring, s[left:right+1]) left-- right++ } else { break } } } // Check palindrome that has core with 2 element. for i := 1; i < len(s); i++ { if s[i] != s[i-1] { continue } longestSubstring = maxSubstring(longestSubstring, s[i - 1: i + 1]) left, right := i - 2, i + 1 for left >= 0 && right <= len(s) - 1 { if s[left] == s[right] { longestSubstring = maxSubstring(longestSubstring, s[left: right + 1]) left-- right++ } else { break } } } return longestSubstring } func maxSubstring(a, b string) string { if len(a) > len(b) { return a } return b } ``` ## Footnote A palindrome has two forms: One with a single core 'aba' and another with a two-element core 'abba'

Answer 35

Expand the substring around possible palindrome cores. Add 1 to count when encounter a valid palindrome. ``` func countSubstrings(s string) int { if len(s) == 1 { return 1 } var count int for i := 0; i < len(s); i++ { count++ left, right := i-1, i+1 for left >= 0 && right <= len(s)-1 { if s[left] == s[right] { count++ left-- right++ } else { break } } } for i := 1; i < len(s); i++ { if s[i] == s[i-1] { count++ left, right := i-2, i+1 for left >= 0 && right <= len(s)-1 { if s[left] == s[right] { count++ left-- right++ } else { break } } } } return count } ``` ## Footnote A palindrome has two forms: One with a single core 'aba' and another with a two-element core 'abba'

Answer 36

**Filter invalid triplets.** We will never pick a triplet that it's triplet[i] is greater than the target[i]. => If picked, the target can never be formed. * Elegant way ``` func mergeTriplets(triplets [][]int, target []int) bool { res := make([]int, 3) for _, triplet := range triplets { // Ignore triplets that have any value greater than the target. if triplet[0] > target[0] || triplet[1] > target[1] || triplet[2] > target[2] { continue } res[0] = max(triplet[0], res[0]) res[1] = max(triplet[1], res[1]) res[2] = max(triplet[2], res[2]) } // The formed res should equal to the target. return res[0] == target[0] && res[1] == target[1] && res[2] == target[2] } ``` * Ugly Way ``` func mergeTriplets(triplets [][]int, target []int) bool { // Filter invalid triplets. // We will never pick a triplet that it's triplet[i] is greater than the target[i]. => If picked, the target can never be formed. toBeRemoved := make(map[int]struct{}) for i, num := range target { for j, triplet := range triplets { if triplet[i] > num { toBeRemoved[j] = struct{}{} } } } filteredTriplets := make([][]int, 0) for i, triplet := range triplets { if _, ok := toBeRemoved[i]; !ok { filteredTriplets = append(filteredTriplets, triplet) } } first, second, third := make(map[int]struct{}), make(map[int]struct{}), make(map[int]struct{}) for _, triplet := range filteredTriplets { for j, num := range triplet { switch j { case 0: first[num] = struct{}{} case 1: second[num] = struct{}{} case 2: third[num] = struct{}{} } } } for i, num := range target { var ok bool switch i { case 0: _, ok = first[num] case 1: _, ok = second[num] case 2: _, ok = third[num] } if !ok { return false } } return true } ```

Answer 37

Back tracking and dynamic programming. Figure out the brute force way and store the result. If 0, return 0, if at the end string, return 1. ``` func numDecodings(s string) int { dpTable := make(map[int]int) var exhaust func(start int) int exhaust = func(start int) int { if start < len(s) && s[start] == '0' { return 0 } if start >= len(s)-1 { return 1 } // If already calculated, return the calculated result. if _, ok := dpTable[start]; ok { return dpTable[start] } switch s[start] { case '1': // If encounter 1, jumping by 1 and by 2 are both valid. dpTable[start] = exhaust(start + 1) + exhaust(start + 2) case '2': // If encounter 2, jumping by 1 is valid. dpTable[start] = exhaust(start + 1) // Need to check if the next value is smaller than 7. if start+1 < len(s) { if s[start+1] < 55 { dpTable[start] += exhaust(start + 2) } } default: // Anything that aren't 1 or 2 should jump 1. dpTable[start] = exhaust(start + 1) } return dpTable[start] } return exhaust(0) } ```

Answer 38

Separate string into groups by mod(%), add all the numbers and replace the original one with the calculated result. Loop until the length of the digits is smaller or equal to k. ``` func digitSum(s string, k int) string { for len(s) > k { var newString string var currentGroup string for i := 0; i < len(s); i++ { if i%k != 0 { currentGroup += string(s[i]) } else { if len(currentGroup) != 0 { newString += add(currentGroup) } currentGroup = string(s[i]) } } newString += add(currentGroup) s = newString } return s } func add(sGroup string) string { var result int for i := 0; i < len(sGroup); i++ { num, _ := strconv.Atoi(string(sGroup[i])) result += num } return strconv.Itoa(result) } ```

Answer 39

Create a stack that stores the location of idle brackets. During the first loop, remove from stackLeft when encounter right bracket; If length of stackLeft is 0, append right bracket location to stackRight. At the second loop, check the location of the asterisk and pop from stacks. Asterisk location should be smaller than the head of stackLeft, and should be greater than the head of stackRight. At the end, both stack should be empty. ``` func checkValidString(s string) bool { // Stack that stores the location of idle brackets. stackLeft := make([]int, 0) stackRight := make([]int, 0) for i, ch := range s { if ch == '(' { stackLeft = append(stackLeft, i) } if ch == ')' { if len(stackLeft) > 0 { stackLeft = stackLeft[:len(stackLeft)-1] } else { stackRight = append(stackRight, i) } } } if len(stackLeft) > 0 || len(stackRight) > 0 { for i := len(s) - 1; i >= 0; i-- { if s[i] == '*' { if len(stackLeft) > 0 && i > stackLeft[len(stackLeft)-1] { // 12 27 // ( * => can pop // Pop from stack left if current i is greater than where the left paranthesis happen. stackLeft = stackLeft[:len(stackLeft)-1] } else if len(stackRight) > 0 && i < stackRight[len(stackRight)-1] { // 12 27 // * ) => can pop // Pop from stack right if current i is smaller than where the left paranthesis happen. stackRight = stackRight[:len(stackRight)-1] } if len(stackLeft) == 0 && len(stackRight) == 0 { break } } } } return len(stackLeft) == 0 && len(stackRight) == 0 } ```

Answer 40

Dynamic Programming. ``` func runningSum(nums []int) []int { dpTable := make([]int, len(nums)) dpTable[0] = nums[0] for i := 1; i < len(nums); i++ { dpTable[i] = nums[i] + dpTable[i - 1] } return dpTable } ```

Answer 41

* Use the **AND** operator. Anything AND with 1(0001) returns 1(0001) if the right most bit is 1, else 0. ``` func countBits(n int) []int { ones := make([]int, n + 1) for n != 0 { var count int for k := n; k > 0; k >>= 1 { count += int(k & 1) } ones[n] = count n-- } return ones } ``` * Use **dynamic programming**. The idea here is to use the number of 1's in i >> 1 (i.e., i **divided by 2**) and the **last bit** in i to find the number of 1's in i. Initialization: Create an array ans of length n + 1, initialized with zeros. Main Algorithm: Iterate from 1 to n, and for each i, set ans[i] = ans[i >> 1] + (i & 1). 0(0000), 1(0001), 2(0010), 3(0011), 4(0100), 5(0101), 6(0110) 5(0101) = 2(010) + last bit (i & 1) 6(0110) = 3(011) + lastbit (i & 1) ``` func countBits(n int) []int { ones := make([]int, n + 1) for i := 1; i <= n; i++ { ones[i] = ones[i>>1] + (i & 1) } return ones } ```

Answer 42

Use the OR(|) operator to copy the last bit. Fetch the last bit by the AND(&) operator. ``` func reverseBits(num uint32) uint32 { var reversed uint32 // Have to move 32 times. for i := 0; i < 32; i++ { reversed |= num & 1 // Copy the last bit to 'reversed' last bit. num >>= 1 // Discard the last bit. if i < 31 { // After we copy the last, we don't want to shift left. reversed <<= 1 // Shift 'reversed' left, now we have a placeholder (last bit 0) to write copied last bit to it. } } return reversed } ```

Answer 43

* HashMap * Utilize the concept of XOR cancelling out each other, and the order doesn't matter. Start with missing = 0, XOR the original array first, then XOR the entire range. We will have the missing number at the end. // Cancelling 0001 ^ 0001 = 0000 0010 ^ 0010 = 0010 // XOR 0 with any number is any number. 0000 ^ 0001 = 0001 ``` func missingNumber(nums []int) int { size := len(nums) var missing int // XOR cancels identical numbers. for i := 0; i < size; i++ { missing ^= nums[i] } for i := 0; i <= size; i++ { missing ^= i } return missing } ``` * The missing number is ( 等差級數的合 ) - (sum of nums) ``` func missingNumber(nums []int) int { size := len(nums) sumOfSeries := ((1 + size) * size) / 2 var sumOfNums int for i := 0; i < size; i++ { sumOfNums += nums[i] } return sumOfSeries - sumOfNums } ```

Answer 44

Use **XOR** for keeping the 1's, cancelling out the same (1 and 1, 0 and 0). Use **AND** and **Left Shift** to calculate the carries. Add the sum and carry until the carry is 0. ``` func getSum(a int, b int) int { var sum, carry int for { // Four scenarios: // 1. Bit in a and b are both 0 => sum = 0 // 2, 3. Either one of a or b is 1 => sum = 1 // 4. Bit in a and b are both 1 => sum = 0, carry = 10 // Use XOR to check the difference. sum = a ^ b // Use AND to get carry, 01 + 01 = 10, which is AND first then shift left. carry = (a & b) << 1 if carry == 0 { break } // We want to add the current sum and carry, thus casting value sum and curry to a and b. a, b = sum, carry } return sum } ```

Answer 45

Count the difference between the two integers. Use **XOR** to get the difference, then count the 1's by using **AND** with 0001. ``` func hammingDistance(x int, y int) int { var distance int diff := x ^ y for diff != 0 { distance += diff & 1 diff >>= 1 } return distance } ```

Answer 46

Use AND with 1 to check the last bit, loop until current == leading (return fasle) or when n == 0. ``` func hasAlternatingBits(n int) bool { leading := n & 1 n >>= 1 for n != 0 { if (n & 1) == leading { return false } leading = n & 1 n >>= 1 } return true } ```

Answer 47

Create a dynamic programming table that has the size len(s) + 1. Set dp[len(s)] = true, meaning that any word that reaches this position by calling dp[len(s)] is a successful word break. Use a decision tree to visualize the process. ``` func wordBreak(s string, wordDict []string) bool { dpTable := make([]bool, len(s) + 1) dpTable[len(s)] = true // Loop reversely: Bottom Up. for i := len(s) - 1; i >= 0; i -- { // Decision Tree: Check every word in wordDict. for _, word := range wordDict { if i + len(word) <= len(s) && s[i: i + len(word)] == word { // The segment of the word has a match in the dictionary. // 1. neetcode, ["nee"], i = 0 has a match, but i = 4 doesn't have a match. dpTable[i] = dpTable[i + len(word)] // Check whether the rest of the word segment have a match. } if dpTable[i] { break } } } return dpTable[0] } ```

Answer 48

Use Mod. ``` func reverse(x int) int { digits := make([]int, 0) for x != 0 { digits = append(digits, x % 10) x /= 10 } var result int for i, j := 0, len(digits) - 1; j >= 0; j-- { result += digits[i] * int(math.Pow(10, float64(j))) i++ } if result > int(math.Pow(2, 31)) - 1 || result < -int(math.Pow(2, 31)) { result = 0 } return result } ```

Answer 49

* Use math.Pow() from the standard library. ``` func myPow(x float64, n int) float64 { return math.Pow(x, float64(n)) } ``` * Use the trait of power. ``` func myPow(x float64, n int) float64 { // Early end. if n == 0 || x == 1 { return 1 } var negative bool if n < 0 { negative = true n = -n } result := float64(1) for n != 0 { if n%2 != 0 { n-- result *= x continue } x *= x n >>= 1 } if negative { result = 1 / result } return result } ```

Answer 50

Running Sum and Local Max. ``` func largestAltitude(gain []int) int { var largest int largest = max(largest, gain[0]) // Running Sum. for i := 1; i < len(gain); i++ { gain[i] += gain[i-1] largest = max(largest, gain[i]) } return largest } ```

Answer 51

Sliding Window. Subtract one if head is vowel; add one if tail is vowel. Compare the stored largest vowels and the local. ``` func maxVowels(s string, k int) int { var vowels int vowelsMap := map[byte]struct{}{ 'a': struct{}{}, 'e': struct{}{}, 'i': struct{}{}, 'o': struct{}{}, 'u': struct{}{}, } for i := 0; i < k; i++ { _, ok := vowelsMap[s[i]] if ok { vowels++ } } localVowels := vowels for i := k; i < len(s); i++ { if _, ok := vowelsMap[s[i-k]]; ok { localVowels-- } if _, ok := vowelsMap[s[i]]; ok { localVowels++ } vowels = max(vowels, localVowels) } return vowels } ```

Answer 52

Two Pointers. Sort the array first, pick from the head and the tail. Compare the sum of the head and the tail. Add 1 to pairs if the sum is equal to k. ``` func maxOperations(nums []int, k int) int { sort.Ints(nums) var pairs int i, j := 0, len(nums) - 1 for i < j { sum := nums[i] + nums[j] switch { case sum > k: j-- case sum < k: i++ default: pairs++ i++ j-- } } return pairs } ```

Answer 53

Use a stack. Push when the character isn't a star, otherwise pop from it. ``` func removeStars(s string) string { stack := make([]byte, 0) // Push to stack when the char is a letter. // Pop from the stack when the char is a '*'. for i := range s { switch s[i]{ case '*': stack = stack[:len(stack) - 1] default: stack = append(stack, s[i]) } } // Join the byte array. return string(stack) } ```

Answer 54

PreOrder traversal, root-> left -> right. Check Left then check right. ``` func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool { leaves1, leaves2 := getLeaves(root1), getLeaves(root2) return compareLeaves(leaves1, leaves2) } func getLeaves(root *TreeNode) []int { leaves := make([]int, 0) var dfs func(node *TreeNode) dfs = func(node *TreeNode) { if node == nil { return } if node.Left == nil && node.Right == nil { leaves = append(leaves, node.Val) return } if node.Left != nil { dfs(node.Left) } if node.Right != nil { dfs(node.Right) } } dfs(root) return leaves } func compareLeaves(leaves1, leaves2 []int) bool { if len(leaves1) != len(leaves2) { return false } for i := 0; i < len(leaves1); i++ { if leaves1[i] != leaves2[i] { return false } } return true } ```

Answer 55

Backtracking. Return if we already visited the room. Otherwise loop through all the keys and visit the room. Keep track of all the rooms that are visited. Go through the visited array, return false if there's room that isn't visited. ``` func canVisitAllRooms(rooms [][]int) bool { visited := make([]int, len(rooms)) var visit func(roomIdx int) visit = func(roomIdx int) { if visited[roomIdx] == 1 { return } visited[roomIdx] = 1 for _, nextRoom := range rooms[roomIdx] { visit(nextRoom) } } visit(0) for _, beenTo := range visited { if beenTo == 0 { return false } } return true } ```

Answer 56

Maintain the BST property. * Iterative ``` func insertIntoBST(root *TreeNode, val int) *TreeNode { // Empty BST. if root == nil { return &TreeNode {Val: val} } temp := root for { if val < temp.Val { if temp.Left == nil { temp.Left = &TreeNode{Val:val} break } else { temp = temp.Left } } if val > temp.Val { if temp.Right == nil { temp.Right = &TreeNode{Val: val} break } else { temp = temp.Right } } } return root } ``` * Recursive ``` func insertIntoBST(root *TreeNode, val int) *TreeNode { // Empty BST. if root == nil { return &TreeNode {Val: val} } if val < root.Val { root.Left = insertIntoBST(root.Left, val) } else { root.Right = insertIntoBST(root.Right, val) } return root } ```

Answer 57

* Swap in-place (slow). ``` func moveZeroes(nums []int) { // Swapping in place? // Swap with a non-zero element when looping in place. for i := 0; i < len(nums); i++ { if nums[i] == 0 { for j := i + 1; j < len(nums); j++ { if nums[j] != 0 { nums[i], nums[j] = nums[j], nums[i] break } } } } } ``` * Keep a zero pointer and swap in-place (fast). ``` func moveZeroes(nums []int) { zeroPointer := 0 for idx, num := range nums { if num != 0 { nums[idx], nums[zeroPointer] = nums[zeroPointer], nums[idx] zeroPointer++ } } } ```

Answer 58

Find the node before the middle and change the next node to the next.next. Find the middle with the below ways: * Tortoise and the Hare (Fast Slow pointer) ``` func deleteMiddle(head *ListNode) *ListNode { if head.Next == nil { return nil } slow, fast := head, head.Next.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } slow.Next = slow.Next.Next return head } ``` * Count length ``` func deleteMiddle(head *ListNode) *ListNode { var length int // Count length, get the middle index. temp := head for temp != nil { length++ temp = temp.Next } if length == 1 { return nil } temp = head // Perform delete on the middle index. count := 0 for count != (length / 2) - 1 { temp = temp.Next count++ } temp.Next = temp.Next.Next return head } ```

Answer 59

Breadth First Search. Use the queue length to keep track of the nodes in a level. Only update the maxLevel when a sum greater than maxLevelSum occurs. When a maxSum occurs the second time, don't do anything: we already have a lower level that has a maxSum. ``` func maxLevelSum(root *TreeNode) int { maxLevelSum := root.Val maxLevel := 1 queue := []*TreeNode{root} currLevel := 0 levelNodes := len(queue) for len(queue) != 0 { currLevel++ localLevelSum := 0 for i := 0; i < levelNodes; i++ { localLevelSum += queue[0].Val // Append children to the queue. if queue[0].Left != nil { queue = append(queue, queue[0].Left) } if queue[0].Right != nil { queue = append(queue, queue[0].Right) } // Pop current node from the queue. queue = queue[1:] } // Only update when localLevelSum > maxLevelSum. if localLevelSum > maxLevelSum { maxLevelSum = localLevelSum maxLevel = currLevel } // We reached the next level. levelNodes = len(queue) } return maxLevel } ```

Answer 60

Find the successor of the node we want to delete. Copy the successor value to the node we want to delete. Traverse the subtree and delete the successor node. ``` func deleteNode(root *TreeNode, key int) *TreeNode { // Case 0, key not found. if root == nil { return nil } // Find the node to be deleted if key < root.Val { root.Left = deleteNode(root.Left, key) } else if key > root.Val { root.Right = deleteNode(root.Right, key) } else { // Node found. if root.Left == nil { return root.Right } else if root.Right == nil { return root.Left } // Node with two children: Get the inorder successor (smallest in the right subtree) successor := minValueNode(root.Right) // Copy the successor value to the current value. root.Val = successor.Val // The problem is now reduces to the upper case. // Now we only have to delete the original successor node in the subtree. // This also handles the scenario where there's no children root.Right = deleteNode(root.Right, successor.Val) } return root } // Helper function to find the minimum value node in a given BST func minValueNode(node *TreeNode) *TreeNode { current := node for current.Left != nil { current = current.Left } return current } ```

Answer 61

Brute Force. ``` func numberOfPairs(nums1 []int, nums2 []int, k int) int { var count int for i := range nums1 { for j := range nums2 { if nums1[i] % (nums2[j] * k) == 0 { count++ } } } return count } ```

Answer 62

Two Pointers that meets the requirements. * Elegant way. ``` func compressedString(word string) string { comp := make([]byte, 0) i, j := 0, 0 for i < len(word) { var count int for j < len(word) && word[i] == word[j] && count < 9 { j++ count++ } // Append to comp. comp = append(comp, []byte(strconv.Itoa(count))[0]) comp = append(comp, word[i]) // Update i to j. i = j } return string(comp) } ``` * My Way. ``` func compressedString(word string) string { comp := make([]byte, 0) for i := 0; i < len(word); i++ { var j int start := word[i] count := 1 for j = i + 1; j < len(word); j++ { if count == 9 || word[j] != start { break } count++ } // Append to comp. comp = append(comp, []byte(strconv.Itoa(count))...) comp = append(comp, start) // Update i to j. i = j - 1 } return string(comp) } ```

Answer 63

Running Sum. Calculate the running sum from left and right and store the results in an array separately. Compare the left and right from the left. ``` func pivotIndex(nums []int) int { left := make([]int, len(nums)) left[0] = 0 for i := 1; i < len(nums); i++ { left[i] = left[i-1] + nums[i-1] } right := make([]int, len(nums)) right[len(nums) - 1] = 0 for i := len(nums) - 2; i >= 0; i-- { right[i] = right[i + 1] + nums[i + 1] } for i := range nums { if left[i] == right[i] { return i } } return -1 } ```

Answer 64

Sliding window. Store the absolute distance as a table. Slide through the window and see what window sum fits the budget (maxCost). ``` func equalSubstring(s string, t string, maxCost int) int { var maxLength int // Sliding Window. var distance int costTable := make([]int, len(s)) for i := range s { distance = int(t[i]) - int(s[i]) if distance < 0 { distance *= -1 } costTable[i] = distance } var i int var currSum int for j := 0; j < len(costTable); j++ { currSum += costTable[j] for currSum > maxCost && i <= j { currSum -= costTable[i] i++ } if maxCost >= currSum { maxLength = max(maxLength, j - i + 1) } } return maxLength } ```

Answer 65

* carry = 0 and current = 0, number is even, have to divide it by 2, step + 1 * carry = 0 and current = 1, number is odd, have to add 1 and divide it by 2, step + 2 * carry = 1 and current = 1, number is even, divide it by 2, step + 1 * carry = 1 and current = 0, number is odd, have to add 1 and divide it by 2, step + 2 ``` func numSteps(s string) int { var steps, carry int for i := len(s) - 1; i > 0; i-- { switch s[i] { case '0': if carry == 0 { // When carry is 0 and current is 0, divide. steps++ } else { // When carry is 1 and current is 0 => new current is 1, need another two steps. // Flip 1 to 0, divide. // And the carry is also carried on. steps += 2 } case '1': if carry == 0 { // When carry is 0, flip 1 to 0, divide. steps+=2 } else { // When current is 1 and carry is 1, flip. steps++ } carry = 1 } } // If carry is not zero when we reach the head of the string, we have an overflow. // Need to divide it by two once more. Hence adding 1. if carry != 0 { return steps + 1 } return steps } ```

Answer 66

Dynamic Programming. Create a table that stores the result. ``` func uniquePaths(m int, n int) int { table := make([][]int, m) for i := 0; i < m; i++ { table[i] = make([]int, n) } table[m-1][n-1] = 1 // Bottom Up approach. for row := len(table) - 1; row >= 0; row-- { for col := len(table[0]) - 1; col >=0; col-- { if table[row][col] != 0 { continue } // Border if row != len(table) - 1 && col == len(table[0]) - 1 { table[row][col] += table[row + 1][col] } else if row == len(table) - 1 && col != len(table[0]) - 1 { table[row][col] += table[row][col + 1] } else { table[row][col] = table[row + 1][col] + table[row][col + 1] } } } return table[0][0] } ```

Answer 67

Find the zigzag pattern of a string and jump the index respectively. ``` func convert(s string, numRows int) string { if numRows == 1 || len(s) == 1 { return s } original := make([]byte, 0) fullGap := (numRows - 1) * 2 gap := fullGap var i int // First Row. j := i for j < len(s) { original = append(original, s[j]) j += fullGap } gap -= 2 // Row in middle. for i = 1; i < numRows-1; i++ { // Jump gap respectively. j = i for j < len(s) { if j < len(s) { original = append(original, s[j]) } j += gap if j < len(s) { original = append(original, s[j]) } j += fullGap - gap } gap -= 2 } // Last Row j = i for j < len(s) { original = append(original, s[j]) j += fullGap } return string(original) } ```

Answer 68

Use XOR to fetch a ^ b. Find the different bit from the found result. Use the different bit to organize the nums into two separate groups: At the different bit the number is either 1 or either 0. XOR the two groups to get the two unique numbers. ``` func singleNumber(nums []int) []int { var xor int // The XOR result of the two single number/ for i := range nums { xor ^= nums[i] } // Find the location first different number in a and b from xor. bitDiffLocation := 0 for (xor >> bitDiffLocation) & 1 != 1{ bitDiffLocation++ } var uniqueA, uniqueB int // Now we can separate nums into two groups // 1. A group at bitDiffLocation has the same bit as xor (which is 1) // 2. A group at bitDiffLocation is different from xor (which is 0) for i := range nums { if (nums[i] >> bitDiffLocation) & 1 == 1 { uniqueA ^= nums[i] } else { uniqueB ^= nums[i] } } return []int{uniqueA, uniqueB} } ```

Answer 69

Loop through two strings alternatively. ``` func mergeAlternately(word1 string, word2 string) string { result := make([]byte, 0) var i, j int for i < len(word1) || j < len(word2) { if i < len(word1) { result = append(result, word1[i]) i++ } if j < len(word2) { result = append(result, word2[j]) j++ } } return string(result) } ```

Answer 70

Two Pointers. Jump the pointer(i) in t when reached a location in s where s[j] == t[i]. ``` func appendCharacters(s string, t string) int { var i int for j := 0; j < len(s); j++ { if s[j] == t[i] { i++ } if i == len(t) { break } } return len(t) - i } ```

Answer 71

Store the row and col string separately in a rowMap and a colMap. The count of an identical pair is the multiplcation of both the values with the same key. ``` func equalPairs(grid [][]int) int { var count int rowMap := make(map[string]int) colMap := make(map[string]int) n := len(grid) for i := 0; i < n; i++ { var colKey string var rowKey string for j := 0; j < n; j++ { rowKey += (strconv.Itoa(grid[i][j]) + ",") colKey += (strconv.Itoa(grid[j][i]) + ",") } rowMap[rowKey]++ colMap[colKey]++ } fmt.Println(rowMap, colMap) for key, val := range rowMap { // If we have two identical rows and two identical cols // The total pair is 2 * 2 = 4. count += val * colMap[key] } return count } ```

Answer 72

Form a hashset that stores the frequencies of characters. If we have an odd number, we have a palindrome that can have core with one character. Add the all the odd number - 1 and all the even number to the maxLength. ``` func longestPalindrome(s string) int { count := make(map[byte]int) for i := range s { count[s[i]] += 1 } var maxLength int var haveSingle bool for _, v := range count { switch v % 2 { case 0: maxLength += v case 1: haveSingle = true maxLength += v - 1 } } if haveSingle { maxLength++ } return maxLength } ```

Answer 73

Two Pointers. Reverse accordingly when going through the string. ``` func reverseVowels(s string) string { byteStr := []byte(s) i, j := 0, len(byteStr)-1 for i < j { for i < len(s) && !isVowel(byteStr[i]) { i++ } for j >= 0 && !isVowel(byteStr[j]) { j-- } if i < j { byteStr[i], byteStr[j] = byteStr[j], byteStr[i] i++ j-- } } return string(byteStr) } func isVowel(char byte) bool { switch char { case 'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u': return true default: return false } } ```

Answer 74

Depth First Search. Add 1 to the return value when the node value is equal to the remains. Each pathSum function calculates from that node till the end. ``` func pathSum(root *TreeNode, targetSum int) int { if root == nil { return 0 } var dfs func(node *TreeNode, remains int) int dfs = func(node *TreeNode, remains int) int { if node == nil { return 0 } var pair int remains -= node.Val if remains == 0 { // A pair occurred pair++ } return pair + dfs(node.Left, remains) + dfs(node.Right, remains) } return dfs(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum); } ```

Answer 75

Create hashsets and compare the frequencies. ``` func commonChars(words []string) []string { common := make([]string, 0) arrs := make([][]int, 0) for _, word := range words { arrs = append(arrs, createHashSet(word)) } for i := 0; i < 26; i++ { currChar := i + 'a' minFrequency := 101 for j := 0; j < len(arrs); j++ { minFrequency = min(minFrequency, arrs[j][i]) } if minFrequency != 101 { for k := minFrequency; k > 0; k-- { common = append(common, string(currChar)) } } } return common } func createHashSet(word string) []int { hashSet := make([]int, 26) for i := range word { hashSet[word[i] - 'a']++ } return hashSet } ```

Answer 76

Parse the original string. Append to the word list when encounter space. Read the word list reversely. ``` func reverseWords(s string) string { resultArr := make([]string, 0) currStr := make([]byte, 0) for i := range s { switch s[i] { case ' ': if len(currStr) != 0 { resultArr = append(resultArr, string(currStr)) currStr = make([]byte, 0) } default: currStr = append(currStr, s[i]) } } if len(currStr) != 0 { resultArr = append(resultArr, string(currStr)) } var result string for i := len(resultArr) - 1; i >= 0; i-- { if len(result) != 0 { result += " " } result += resultArr[i] } return result } ```

Answer 77

Keep the used card and the currHand as queue. Only clear the queue when it reached the desired group size. Check if the next card is a valid card to put to hand. If equal, jump. If is valid card, append. If it's a jumped card, return false. At the end the currHand should be empty(since all card appended to the hand is at valid size and discarded.). ``` func isNStraightHand(hand []int, groupSize int) bool { // 1. CurrHand empty, append to it // 2. CurrHand not empty, check if we can append to it // a. hand[i] is the sequence of the last element of currhand // b. hand[i] is not the sequence of the last element // 1. Equals to the last element // 2. Jumped, return false sort.Ints(hand) used := make([]bool, len(hand)) // Store the index. currHand := make([]int, 0) for i := 0; i < len(hand); i++ { if used[i] { continue } j := i for len(currHand) < groupSize && j < len(hand) { if used[j] { j++ continue } // CurrHand empty, append anything that comes after. if len(currHand) == 0 { currHand = append(currHand, j) used[i] = true j++ continue } // CurrHand not empty, check if the next card is valid. if hand[j] == hand[currHand[len(currHand)-1]] { j++ } else if hand[j] == hand[currHand[len(currHand)-1]]+1 { currHand = append(currHand, j) used[j] = true j++ } else { return false } } // Only clear the currHand if the hand size equals to the group size. if len(currHand) == groupSize { currHand = make([]int, 0) } } // Meaning that the hand didn't reached the group size, didn't renew. if len(currHand) != 0 { return false } return true } ```

Answer 78

2D Dynamic Programming. Find the relationship between the strings. Concept here is ``` if len(text1) == 0 || len(text2) == 0, return 0 if text1[0] == text[0], return 1 + lcs(text1[1:], text2[1:]) else, return max(lcs(text1[1:], text2), lcs(text1, text2[1:])) ``` // abcde // ace // head match => find the longest common subsequence of 1 + lcs("bcde", "ce") // bcde // ce // head doesn't match => find the longest common subsequence by max(lcs("bcde", "ce"), lcs("cde", "ce")) // if any string is empty, return 0 // e // e // head match => find the longest subsequence of 1 + lcs("", "") => 1 // e // "" // head match => return 0 ``` func longestCommonSubsequence(text1 string, text2 string) int { // Add one more row and column as boundaries. dpTable := make([][]int, len(text1) + 1) for i := range dpTable { dpTable[i] = make([]int, len(text2) + 1) } // Bottom-up approach. // // Start from the last second row and column within the dpTable. for i := len(text1) - 1; i >= 0; i-- { for j := len(text2) - 1; j >= 0; j-- { if text1[i] == text2[j] { dpTable[i][j] = 1 + dpTable[i + 1][j + 1] } else { dpTable[i][j] = max(dpTable[i][j + 1], dpTable[i + 1][j]) } } } return dpTable[0][0] } ```

Answer 79

* Brute Force ``` func replaceWords(dictionary []string, sentence string) string { resultSlice := make([]string, 0) sort.Strings(dictionary) // Brute force => O(n^3) words := strings.Split(sentence, " ") for _, word := range words { replacement := word for _, option := range dictionary { // if option in replacement and option.length < replacement if in(replacement, option) { replacement = option } } resultSlice = append(resultSlice, replacement) } var result string for i, word := range resultSlice { if i != len(resultSlice) - 1 { result += word + " " } else { result += word } } return result } func in(word1, word2 string) bool { if len(word2) >= len(word1) { return false } var i int for j := 0; j < len(word2); j++ { if word2[j] != word1[i] { return false } i++ } return true } ``` * HashSet. Put all words in the dictionary into a map. Compare and replace the words if we found a match in the map. ``` func replaceWords(dictionary []string, sentence string) string { dic := make(map[string]struct{}) for _, word := range dictionary { dic[word] = struct{}{} } resultSlice := make([]string, 0) words := strings.Split(sentence, " ") for _, word := range words { replacement := word for j := 0; j < len(word); j++ { if _, ok := dic[string(word[:j])]; ok && len(string(word[:j])) < len(replacement){ replacement = string(word[:j]) } } resultSlice = append(resultSlice, replacement) } return strings.Join(resultSlice, " ") } ``` * Trie

Answer 80

Store the first location of the prefix mod in a hashset. Utilize the fact that mod cycles. If a mode cycles, it either is adding 0 to the previous number, or adding a number that equals to k. So if a prefix mod is already in the hashset, check the location difference. If the location difference is greater than 1, we got our answer. ``` func checkSubarraySum(nums []int, k int) bool { // Utilize the trait of a mod: it Cycles. // Store prefix mod in a hashset. If the prefix mod is in the hashset // It means that we either added 0 or a multiple of k to the sum // Check the size of the subarray // If the size is not 1, return true => we got a valid subarray. // prefixMod = (nums[i] +prefixMod[i - 1]) % k modSet := make(map[int]int) // mod: locationIdx modSet[0] = -1 prefixMod := 0 for i := 0; i < len(nums); i++ { prefixMod = (nums[i] + prefixMod) % k if prevLocation, ok := modSet[prefixMod]; ok { if i - prevLocation > 1 { return true } } else { modSet[prefixMod] = i } } return false } ```

Answer 81

Recursion. Trim the assumes gcd from the longest one until either of situtations: 1. The two string equals each other, gcd is the shorter string. 2. First few letters that of the longer string doesn't equal to the divisor. ``` func gcdOfStrings(str1 string, str2 string) string { if str1 == str2 { return str1 } if len(str2) > len(str1) { str1, str2 = str2, str1 // so that str1 is always longer. } // Recursion if str1[:len(str2)] != str2 { return "" } // Assume that str2 is the gcd and trim str2 from str1. return gcdOfStrings(str1[len(str2):], str2) } ```

Answer 82

Utilize the trait of cycled modulo. Given r is smaller than i and j, i is also smaller than j. If prefixSum[r: i] % k = s and prefixSum[r: j] % k = s, then prefixSum[i + 1:j] % k = s. ``` func subarraysDivByK(nums []int, k int) int { remainderMap := make([]int, k) remainderMap[0] = 1 var count int var prefixMod int for _, num := range nums { prefixMod = (prefixMod + num) % k if prefixMod < 0 { prefixMod += k // Handling negative mod } count+= remainderMap[prefixMod] remainderMap[prefixMod]++ } return count } ```

Answer 83

Sort and compare the difference. ``` func heightChecker(heights []int) int { // Sort and compare the difference sortedHeights := make([]int, len(heights)) copy(sortedHeights, heights) sort.Ints(sortedHeights) var diff int for i := range heights { if heights[i] != sortedHeights[i] { diff++ } } return diff } ```

Answer 84

* Sort in-place ``` func relativeSortArray(arr1 []int, arr2 []int) []int { var sortedIdx int // Sort relatively first. for i := 0; i < len(arr2); i++ { for j := sortedIdx; j < len(arr1); j++ { if arr1[j] == arr2[i] { arr1[j], arr1[sortedIdx] = arr1[sortedIdx], arr1[j] sortedIdx++ } } } // Start sorting the rest in ascending from index == sortedIdx bubbles := len(arr1[sortedIdx:]) for i := 0; i < bubbles; i++ { for j := len(arr1) - 1; j > sortedIdx; j-- { if arr1[j] < arr1[j-1] { arr1[j], arr1[j-1] = arr1[j-1], arr1[j] } } sortedIdx++ } return arr1 } ``` * Counting Sort. Create buckets that stores the frequency of an element. ``` func relativeSortArray(arr1 []int, arr2 []int) []int { existSet := make(map[int]int) for i := range arr2 { existSet[arr2[i]] = 0 } notExistMap := make([]int, 1001) for i := range arr1 { if _, ok := existSet[arr1[i]]; ok { existSet[arr1[i]]++ } else { notExistMap[arr1[i]]++ } } sortArr := make([]int, 0) for _, num := range arr2 { count := existSet[num] for count > 0 { sortArr = append(sortArr, num) count-- } } for num, freq := range notExistMap { count := freq for count > 0 { sortArr = append(sortArr, num) count-- } } return sortArr } ```

Answer 85

Sorting in place with constant space: Bubble sort. ``` func sortColors(nums []int) { // Bubble sort. for j := len(nums) - 1; j >= 0; j-- { for i := 0; i < j; i++ { if nums[i] > nums[i + 1] { nums[i], nums[i + 1] = nums[i + 1], nums[i] } } } } ```

Answer 86

* Greedily compare sorted array. ``` func minMovesToSeat(seats []int, students []int) int { // Greedily move to the position closest? sort.Ints(seats) sort.Ints(students) var moves int for i := range seats { move := seats[i] - students[i] if move < 0 { move *= -1 } moves += move } return moves } ``` * Counting bucket. Get the difference between the current position and the desired position. ``` func minMovesToSeat(seats []int, students []int) int { // Counting bucket. // 1. Find max within the two arrays. var largestSeat int for i := range seats { if seats[i] > largestSeat { largestSeat = seats[i] } } for i := range students { if students[i] > largestSeat { largestSeat = students[i] } } // 2. Create a table indicating where the seat is located and which student (at where) is inneed of a seat. seatsDifference := make([]int, largestSeat) // Provide seat. for i := range seats { seatsDifference[seats[i] - 1]++ } // Sit on the seat. for i := range students { seatsDifference[students[i] - 1]-- } // Walk through the seat difference table and make sure that all negatives (students who needs a seat) moves to a location that can cancel out the positive seat (vacancy). var moves int var unmatched int for i := range seatsDifference { // Abslute number of unmatched is also the number of students moving. moves += abs(unmatched) // Substrackt students who found their seat. unmatched += seatsDifference[i] } return moves } func abs(num int) int { if num < 0 { return num * -1 } return num } ```

Answer 87

Sliding Window. Keep track of the available k's to flip. If the k is still valid and encounter 1, expand. If k is valid but encounter 0, subtract k by 1. If k isn't valid, shrink the window until a zero leaves the window. ``` func longestOnes(nums []int, k int) int { var longest int remains := k var i, j int for j < len(nums) { if nums[j] == 0 { remains-- for remains < 0 { // Add to remains when a zero exits. if nums[i] == 0 { remains++ } // Shrink the window. i++ } } // Check the window length. longest = max(longest, j-i+1) // Expand the window. j++ } return longest } ```

Answer 88

Hashmap. ``` func uniqueOccurrences(arr []int) bool { count := make(map[int]int) for i := range arr { count[arr[i]]++ } occurrences := make(map[int]struct{}) for _, v := range count { if _, ok := occurrences[v]; ok { return false } occurrences[v] = struct{}{} } return true } ```

Answer 89

Create a difference bucket and add the carry to moves each loop // 0, 1, 2, 3 // [0, 1, 2] // [0, 1, 1] // [0, -1, 1] // 0, 1, 2, 3, 4, 5, 6, 7 // [0, 2, 2, 1, 0, 0, 0, 1] // [0, 1, 1, 1, 0, 0, 0, 1] // [0, 1, 1, -1, 0, 0, 0, 1] At index 0, moves = 0, carry = 0 At index 1, moves = 0, carry = 1 At index 2, moves += carry == 1 , then carry += currDiff == 2 At index 3, occupied, moves += carry = 3 At index 4, moves += carry = 5, carry -= 1== 1 At index 5, moves += carry = 6, carry -= 1 == 0 ``` func minIncrementForUnique(nums []int) int { var arrMax int for i := range nums { if nums[i] > arrMax { arrMax = nums[i] } } bucket := make([]int, arrMax + 1) suppose := make([]int, arrMax + 1) for _, num := range nums { bucket[num]++ suppose[num] = 1 } diff := make([]int, arrMax + 1) for i := range bucket { if bucket[i] == 1 && bucket[i] == suppose[i] { diff[i] = -1 // occupied } else { diff[i] = bucket[i] - suppose[i] } } var moves int var carry int for i, num := range diff { // Add all carry to moves => all non-unique number must move once to this position. if carry > 0 { moves += carry } // Difference is 1, there's another non-unique number. if num >= 1 { carry += num } // No difference, put 1 non-unique number here. if num == 0 && carry > 0 { carry-- diff[i] = -1 } } // Deal with the left non-unique numbers. // If carry is 3, then we need to move 3, then 2, then 1 for i := carry; i > 0; i-- { moves += i } return moves } ```

Answer 90

Backtracking. ``` func combinationSum3(k int, n int) [][]int { combinations := make([][]int, 0) var backtracking func(lastNum, localSum ,currk int, currCombination []int) backtracking = func(lastNum, localSum, currk int, currCombination []int){ if currk == 0 { if localSum == n { combinations = append(combinations, currCombination) } return } for i := lastNum + 1; i <= 9; i++ { nextCombination := make([]int, len(currCombination)) copy(nextCombination, currCombination) nextCombination = append(nextCombination, i) backtracking(i, localSum + i, currk - 1, nextCombination) } } for i := 1; i <= 9; i++ { backtracking(i, i, k - 1, []int{i}) } return combinations } ```

Answer 91

Max Heap. Sort Projects by capital, ensuring we look at the cheapest project first. Loop through the projects every round, pushing all projects whose capital is smaller or equal to the current capital to the MaxHeap (where the MaxHeap properity is determined by the profit). This way we have a quick access to the project with the highest available profit for the current round. Loop up to k rounds: Pop the highest project from the MaxHeap, add the profit to the capital ( w ), break if there is no more available project in the heap ( no more projects can be pushed to the heap, either empty projects or the projects left are too expensive). [Max Heap](https://leetcode.com/problems/ipo/solutions/5315041/easy-to-understand-fast-maxheap-sorting) ``` type Project struct { Capital int Profit int } // Inorder to use the heap package in Go, we have to fit the interface // If we were to use a max heap property, the less in the sort should be in descending order. // type Interface interface { // sort.Interface // Push(x any) // add x as element Len() // Pop() any // remove and return element Len() - 1. // } type PriorityQueue []Project func (pq PriorityQueue) Len() int {return len(pq)} func (pq PriorityQueue) Less(i, j int) bool {return pq[i].Profit > pq[j].Profit} // Descending order. func (pq PriorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]} // Push pushes project to the tail of the Priority Queue. func (pq *PriorityQueue) Push(x interface{}) { item := x.(Project) *pq = append(*pq, item) } // Pop removes the tail from the Pririty Queue. func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] *pq = old[:n-1] return item } func findMaximizedCapital(k int, w int, profits []int, capital []int) int { // Create the priority queue first. projects := make([]Project, len(profits)) for i := 0; i < len(profits); i++ { projects[i] = Project{ Capital: capital[i], Profit: profits[i], } } // projects is now sorted in ascending order determined by capital. // This allows us to iterate through the projects array in a linear fashion, // this way we won't have to go through the entire list every time looking for capitals that are smaller then the current capital(w). sort.Slice(projects, func(i, j int) bool { return projects[i].Capital < projects[j].Capital }) // Create a max heap. pq now fits the interface heap in Go. pq := make(PriorityQueue, 0) i := 0 for k > 0 { // Push all projects whose capital is smaller or equal to the current w (capital) to the MaxHeap. for i < len(projects) && projects[i].Capital <= w { heap.Push(&pq, projects[i]) i++ } // Break when there's no more available item in the priority queue. // 1. All projects are exhausted. // 2. We can't afford the projects that are left. if len(pq) == 0 { break } // Pick the head from the MaxHeap, that will be the profit for the current round. currProject := heap.Pop(&pq).(Project) w += currProject.Profit // Decrease k after successfully getting profit for the current round. k-- } return w } ```

Answer 92

Find the pattern when added missing number or add existing number from current array. For array [1], we can form sum within [0, 2) For array [1, 2], we can form sum within [0, 4) For array [1, 2, 4], we can form sum within [0, 8) If our array have (or smaller than )the next missing number, we add it to the missing number, then we can form sum within [0, miss + nums[i]) If our array doesn't have the next missing number, add the missing number to array, then we can form sum within [0, miss + miss) [Find pattern](https://leetcode.com/problems/patching-array/solutions/78488/solution-explanation) ``` Using the given numbers 1, 2 and 4, we can already build all sums from 0 to 7, i.e., the range [0,8). But we can't build the sum 8, and | the next given number (13) is too large. So we insert 8 into the array. Then we can build all sums in [0,16). Do we need to insert 16 into the array? No! We can already build the sum 3, and adding the given 13 gives us sum 16. We can also add the 13 to the other sums, extending our range to [0,29). And so on. The given 43 is too large to help with sum 29, so we must insert 29 into our array. This extends our range to [0,58). But then the 43 becomes useful and expands our range to [0,101). At which point we're done. ``` ``` func minPatches(nums []int, n int) int { var patches int // miss means that we can have a series of sum in range [0, miss) // We start from 1 (You need a 1 to form a 1). miss := 1 var i int // The loop breaks when the missing number is greater than n. // Means that at the breaking point, our array can form a series of [0, miss), where miss >= n. for miss <= n { // Loop in nums. if i < len(nums) && nums[i] <= miss { // if the current nums[i] is smaller than or equal to miss, ex: [1, 2, 4, 8, 13], miss = 16 (meaning that the miss is formed from our previous added number) // we add the next number 13 directly to the miss, 16 + 13 = 29, expanding range of sum our array can form. miss += nums[i] i++ } else { // Using the numbers 1, 2 and 4, we can already build all sums from 0 to 7, i.e., the range [0,8). // But we can't build the sum 8, and if the next given number is greater than 8, then there's no way we can build 8. // Thus we add the missing 8 to the array. Now the range of sum our array can cover is [0, 16), and our next missing number is 16. miss += miss patches++ } } return patches } ``` | Example: Let's say the input is nums = [1, 2, 4, 13, 43] and n = 100. We need to ensure that all sums in the range [1,100] are possible.

Answer 93

Two Pointers. Start with pointer a at 0 and b at the sqrt of c (since when a ==0, b ^2 == c, b == sqrt(c)). If the sum of a ^ 2 and b ^ 2 is greater than c, decrease b, else if it is smaller than c, increase a. Return true when the local square sum is equal to c, false when a exceeds b. ``` func judgeSquareSum(c int) bool { // Two Pointers. If a == 0, b == sqrt(c). // Let's start with the ceiling number of b. a, b := 0, int(math.Ceil(math.Sqrt(float64(c)))) var currSquareSum int for a <= b { currSquareSum = a * a + b * b if currSquareSum > c { b-- } else if currSquareSum < c { a++ } else { return true } } return false } ```

Answer 94

Two Pointers. Swap in-place. ``` func reverseString(s []byte) { // Two pointers. i, j := 0, len(s) - 1 for i <= j { s[i], s[j] = s[j], s[i] i++ j-- } } ```

Answer 95

Sliding Window. Check if the false is tolerable (smaller than or equal to 1). If the false is not tolerable, slide the head until a zero exits the window. Do this repeatedly until the right side of the window reaches the end of the array. ``` func longestSubarray(nums []int) int { var maxLength int tolerableFalse := 0 haveDeleted := false var i, j int for j < len(nums) { if nums[j] == 0 { haveDeleted = true tolerableFalse++ } for tolerableFalse > 1 { if nums[i] == 0 { tolerableFalse-- } i++ } maxLength = max(maxLength, j - i + 1 - tolerableFalse) j++ } if haveDeleted { return maxLength } else { return maxLength - 1 } } ```

Answer 96

Sort the tasks and the workers. The workers who have greater ability can also achieve the maximum profit job done by previous workers. Pick through the task list in ascending order. Add the profit to maxProfit after every selection. ``` func maxProfitAssignment(difficulty []int, profit []int, workers []int) int { tasks := make(Tasks, len(difficulty)) for i := range difficulty { tasks[i] = Task{Difficulty: difficulty[i], Profit: profit[i]} } sort.Sort(tasks) // If workers are sorted by ability then more capable workers are able to take any job the previous workers were capable of. sort.Ints(workers) var maxProfit int var currProfit int var j int for _, worker := range workers { for j < len(tasks) && worker >= tasks[j].Difficulty { currProfit = max(currProfit, tasks[j].Profit) j++ } maxProfit += currProfit } return maxProfit } type Task struct { Difficulty int Profit int } type Tasks []Task func (t Tasks) Len() int {return len(t)} func (t Tasks) Swap(i, j int) {t[i], t[j] = t[j], t[i]} func (t Tasks) Less(i, j int) bool {return t[i].Difficulty < t[j].Difficulty} ```

Answer 97

Find the max candies first. Add extraCandies to the each candy and compare it to the max candies. ``` func kidsWithCandies(candies []int, extraCandies int) []bool { var greatest int for _, candy := range candies { greatest = max(greatest, candy) } result := make([]bool, len(candies)) for i, candy := range candies { if candy + extraCandies >= greatest { result[i] = true } else { result[i] = false } } return result } ```

Answer 98

Find the day where you can create m bouquets using Binary Search. If a mid is valid, there might be a valid day on the left side (we dicard the right). If a mid in invalid, all the day prior to the mid is invalid, we discard the left part and consider the right part. Check adjacent by looping over the bloomDay and keep track of made bouquets. ``` func minDays(bloomDay []int, m int, k int) int { // The BSA usage here is not a classic "value at middle index of the sorted array", cause problem requires adjacency. // Instead, BSA must be used to find number of days, between the "slowest" bloom (maximum bloomDay value) and "fastest" (minimum bloomDay value). if m * k > len(bloomDay) { return -1 } // 1 <---------------------| (someday in between when we can get all bouquets) |------------------------------> 1e9 left, right := 1, int(1e9) // Where the min bloom day and the max bloom day might occur. var day int var mid int for left <= right { mid = (left + right) / 2 var consecutive int var bouquets int // Loop through the entire bloomDay array and see whether we can create enough bouquets. for i := range bloomDay { // That day has blossom. if bloomDay[i] <= mid { consecutive++ if consecutive == k { consecutive = 0 bouquets++ } } else { // Reset the consecutive if the current bloom day is greater than mid => Hasn't bloom yet. consecutive = 0 } } if bouquets >= m { // Mid is a valid bloom day. day = mid right = mid - 1 // Search on the left side seeing if there's any bloom day lesser that is valid. } else { // Mid day is not a valid bloom day => The left part of all possible bloom days are discarded. left = mid + 1 } } return day } ```

Answer 99

Binary Search. If mid is a bad version, check the left side to see if there's lower bad version ( discard right ). If mid is not a bad version, check the right side to try find a valid bad version. ``` /** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */ func firstBadVersion(n int) int { var bad int left, right := 1, n var mid int for left <= right { mid = (left + right) / 2 if isBadVersion(mid) { bad = mid right = mid - 1 } else { left = mid + 1 } } return bad } ```

Answer 100

Find an element using binary search where it fits the peak element condition using Binary Search. When we encounter an element that isn't a peak element, we assume that the peak element will be somewhere at the side of it's larger neighbor. Move left or right accordingly. 1, 2, 3, 0 If our current mid is 2, it isn't a peak element. Now we know there must be some element greater on the right side, it could be the peak. 1,2,3,4,5 5,4,3,2,1 If it is monotonically increasing/decreasing, then the last/first element in the array is the peak. ``` func findPeakElement(nums []int) int { left, right := 0, len(nums) - 1 var peak int var mid int for left <= right { mid = (left + right) / 2 if mid + 1 < len(nums) && nums[mid] < nums[mid + 1] { left = mid + 1 } else if mid - 1 >= 0 && nums[mid] < nums[mid - 1] { right = mid - 1 } else if (mid == 0 || (mid - 1 >= 0 && nums[mid] > nums[mid - 1])) && (mid == len(nums) -1 || (mid + 1 < len(nums) && nums[mid] > nums[mid + 1])) { peak = mid break } } return peak } ```

Answer 101

Min available gap is 1. Maximum available gap is highestPosition/(m-1). Find the maximum available gap between the minimum and the maximum gap using Binary Search. Check if the gap is available by looping through the entire array and see if all balls can be placed. ``` func maxDistance(position []int, m int) int { // Sort the position for each bucket. sort.Ints(position) minGap, maxGap := 1, position[len(position)-1]/(m-1) var maxDist int var currGap int for minGap <= maxGap { currGap = (minGap + maxGap) / 2 if canPlaceBalls(position, m, currGap) { // If can place ball, currGap is a valid gap. // There might be larger gaps that are valid => Discard left. maxDist = currGap minGap = currGap + 1 } else { // If cannot place ball, larger gaps aren't valid => Discard right. maxGap = currGap - 1 } } return maxDist } func canPlaceBalls(position []int, ballsToPlace int, gap int) bool { prevBallPosition := position[0] ballsToPlace-- for i := 1; i < len(position) && ballsToPlace >= 0; i++ { if position[i] - prevBallPosition >= gap { ballsToPlace-- prevBallPosition = position[i] } } return ballsToPlace <= 0 } ```

Answer 102

Sliding Window. Check the max altered mood for customers in window. ``` func maxSatisfied(customers []int, grumpy []int, minutes int) int { // Sliding Window. var maxAlteredCustomers int for i := 0; i < minutes; i++ { if grumpy[i] == 1 { maxAlteredCustomers += customers[i] } } windowStart := 0 localMaxAltered := maxAlteredCustomers for i := minutes; i < len(customers); i++ { if grumpy[i - minutes] == 1 { localMaxAltered -= customers[i - minutes] } if grumpy[i] == 1 { localMaxAltered += customers[i] } if localMaxAltered > maxAlteredCustomers { windowStart = i - minutes + 1 maxAlteredCustomers = localMaxAltered } } var satisfied int for i := 0; i < windowStart; i++ { if grumpy[i] == 0 { satisfied += customers[i] } } for i := windowStart; i < windowStart + minutes; i++ { satisfied += customers[i] } for i := windowStart + minutes; i < len(customers); i++ { if grumpy[i] == 0 { satisfied += customers[i] } } return satisfied } ```

Answer 103

MinHeap. Push forward and backward first. Then use two pointers to store the next location of next element on the left and on the right. If popped element is on the right side, add the next element on the right to the heap, otherwise the next element on the left. Do it until there's no element left to be pushed (where the next element of on the left exceeds the next element on the right). ``` func totalCost(costs []int, k int, candidates int) int64 { minHeap := make(Workers, 0) for i := 0; i < candidates; i++ { heap.Push(&minHeap, Worker{Cost: costs[i], Location: 0}) // Location 0 means it's on the left side. } // Counting backwards might overlap with the candidates counting forward. for i := max(candidates, len(costs)-candidates); i < len(costs); i++ { heap.Push(&minHeap, Worker{Cost: costs[i], Location: 1}) // Location 1 means it's on the right side. } left, right := candidates, len(costs)-candidates-1 // right is the next of the right part of the candidate var total int for i := 0; i < k; i++ { nextWorker := heap.Pop(&minHeap).(Worker) total += nextWorker.Cost // When left exceeds right, there's no more worker to push to the heap. if left <= right { if nextWorker.Location == 0 { heap.Push(&minHeap, Worker{Cost: costs[left], Location: 0}) left++ } else { heap.Push(&minHeap, Worker{Cost: costs[right], Location: 1}) right-- } } } return int64(total) } type Worker struct { Cost int Location int // 0 on the left, 1 on the right. } type Workers []Worker func (w Workers) Swap(i, j int) { w[i], w[j] = w[j], w[i] } func (w Workers) Len() int { return len(w) } func (w Workers) Less(i, j int) bool { if w[i].Cost == w[j].Cost { return w[i].Location < w[j].Location } return w[i].Cost < w[j].Cost } // MinHeap. func (w *Workers) Push(x any) { (*w) = append(*w, x.(Worker)) } func (w *Workers) Pop() any { old := *w n := len(old) x := old[n-1] *w = old[0 : n-1] return x } ```

Answer 104

Maintain a montonic queue when sliding the window. Pop the head from the window when the head is out of range (outside the window). Iterate through the queue from the back and remove elements that are smaller than or equal to the current element, the removed element aren't relevant anymore (since for the next few slides the newer element will always be greater than the removed elements (which will also leave the window earlier than the current element) ). Do this repeatedly until all max elements in window are stored. ``` func maxSlidingWindow(nums []int, k int) []int { result := make([]int, 0) q := make([]int, 0) for i := 0; i < k; i++ { for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] { q = q[:len(q)-1] } q = append(q, i) } result = append(result, nums[q[0]]) for i := k; i < len(nums); i++ { // Maintain the window by popping the head. for len(q) > 0 && q[0] <= i-k { q = q[1:] } // Iterate through the array from the back. // Remove elements that are smaller than or equal to the current element. for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] { q = q[:len(q)-1] } // Add the current element to the window. q = append(q, i) result = append(result, nums[q[0]]) } return result } ```

Answer 105

Utilize the concept of both a monotonically increasing and a monotonically decreasing queue to keep track of the difference that are smaller than limit. Since we can only have length from range 1 to len(nums), binary search the max possible window length we can have. ``` func longestSubarray(nums []int, limit int) int { var longest int minPossibleWindow, maxPossibleWindow := 1, len(nums) var windowLength int for minPossibleWindow <= maxPossibleWindow { windowLength = minPossibleWindow + (maxPossibleWindow - minPossibleWindow) / 2 if haveMaxSlidingWindowSmallerThanLimit(nums, limit, windowLength) { longest = windowLength minPossibleWindow = windowLength + 1 } else { maxPossibleWindow = windowLength - 1 } } return longest } func haveMaxSlidingWindowSmallerThanLimit(nums []int, limit int, windowLength int) bool { decreasingQ := make([]int, 0) // 8, 4, 2 increasingQ := make([]int, 0) // 2, 4, 8 for i := 0; i < len(nums); i++ { // Maintain window, pop invalid head. for len(decreasingQ) > 0 && decreasingQ[0] <= i-windowLength { decreasingQ = decreasingQ[1:] } for len(increasingQ) > 0 && increasingQ[0] <= i-windowLength { increasingQ = increasingQ[1:] } for len(decreasingQ) > 0 && nums[i] > nums[decreasingQ[len(decreasingQ)-1]] { decreasingQ = decreasingQ[:len(decreasingQ)-1] } for len(increasingQ) > 0 && nums[i] < nums[increasingQ[len(increasingQ)-1]] { increasingQ = increasingQ[:len(increasingQ)-1] } decreasingQ = append(decreasingQ, i) increasingQ = append(increasingQ, i) if i - windowLength + 1 >= 0 { if nums[decreasingQ[0]]-nums[increasingQ[0]] <= limit { return true } } } return false } ```

Answer 106

Sliding Window. Loop until window touches the end: Count the front and the back of a nice subarray. The total mutations will be front * back. Reset front and back when an odd number is removed from the nice subarray, recalculate the front and back. ``` func numberOfSubarrays(nums []int, k int) int { var total int // Continuous => Sliding Window. front, back := 1, 1 var start int for start = 0; start < len(nums); start++ { if nums[start]%2 == 0 { front++ } else { break } } var localOdd int end := start for end < len(nums) { switch nums[end] % 2 { case 0: if localOdd == k { back++ } case 1: localOdd++ if localOdd > k { total += front * back front = 1 back = 1 for nums[start]%2 != 1 { start++ } start++ localOdd-- } for start < len(nums) && nums[start]%2 != 1 { start++ front++ } } end++ } // Deal with the last front and back. if localOdd == k { total += front * back } return total } ```

Answer 107

* Sliding Window - Keep track of the valid flips in the current window. ``` func minKBitFlips(nums []int, k int) int { var totalFlips int // Tracks the total number of flips. var currentFlips int // Tracks the current number of flips in window. for i := 0; i < len(nums); i++ { if i - k >= 0 && nums[i - k] == 2 { // One current flip left the window => Not effective anymore. currentFlips-- } if currentFlips % 2 == nums[i] { // Current flip is odd (flip once before in window) and number is 1 // Current flip is even (didn't flip or flip twice in window) and number is 0. // Now we need flipping, we need to ensure that the rest of the window is not out of bound and can be flipped. if i + k > len(nums) { return -1 } // Flip: Set current number to 2 as an indicator. nums[i] = 2 currentFlips++ totalFlips++ } } return totalFlips } ``` * Brute Force and Greedy (TLE) - When encounter a zero, flip the entire window. ``` func minKBitFlips(nums []int, k int) int { var flips int for i := 0; i <= len(nums) - k; i++ { if nums[i] == 0 { // Flip flips++ for j := i; j < i + k; j++ { if nums[j] == 0 { nums[j] = 1 } else { nums[j] = 0 } } } } for i := range nums { if nums[i] != 1 { return -1 } } return flips } ```

Answer 108

* Sliding Window - Keep track of the valid flips in the current window. ``` func minOperations(nums []int) int { var totalFlips int var currentFlips int // Sliding Window => Keep track of the flips valid within the window. for i := 0; i < len(nums); i++ { if i - 3 >= 0 && nums[i - 3] == 2 { // A flip left the window. currentFlips-- } if (currentFlips % 2 == 0 && nums[i] == 0) || (currentFlips % 2 == 1 && nums[i] == 1) { if i + 3 > len(nums) { return -1 } nums[i] = 2 currentFlips++ totalFlips++ } } return totalFlips } ``` * Brute Force: Greedy ``` func minOperations(nums []int) int { var flips int for i := 0; i <= len(nums) - 3; i++ { if nums[i] == 0 { // Flip flips++ for j := i; j < i + 3; j++ { if nums[j] == 0 { nums[j] = 1 } else { nums[j] = 0 } } } } for i := range nums { if nums[i] != 1 { return -1 } } return flips } ```

Answer 109

* Reversed InOrder Traversal. ``` func bstToGst(root *TreeNode) *TreeNode { if root == nil { return nil } var runningSum int // Add successors value to the current value. var reversedInOrderTraverse func(node *TreeNode) reversedInOrderTraverse = func(node *TreeNode) { if node == nil { return } // Right -> Root -> Left. reversedInOrderTraverse(node.Right) runningSum += node.Val node.Val = runningSum reversedInOrderTraverse(node.Left) } reversedInOrderTraverse(root) return root } ```

Answer 110

Traverse the binary tree to get the sorted array of values. Create a new BST by dividing the sorted array into half recursively. ``` func balanceBST(root *TreeNode) *TreeNode { // Inorder traverse the tree then put it in an array. // Create a balanced tree from the middle. var inOrder func(node *TreeNode, nums *[]int) inOrder = func(node *TreeNode, nums *[]int) { if node == nil { return } inOrder(node.Left, nums) *nums = append(*nums, node.Val) inOrder(node.Right, nums) } var convertSortedArrToBST func(nums []int, start int, end int) *TreeNode convertSortedArrToBST = func(nums []int, start int, end int) *TreeNode { mid := (start + end) / 2 if start > end { return nil } return &TreeNode{ Val: nums[mid], Left: convertSortedArrToBST(nums, start, mid - 1), Right: convertSortedArrToBST(nums, mid + 1, end), } } sortedArr := make([]int, 0) inOrder(root, &sortedArr) return convertSortedArrToBST(sortedArr, 0, len(sortedArr) - 1) } ```

Answer 111

Sort the cities by the amount of roads connected to it (where it has higher importance). Assign the heavier weight to the higher importance cities. ``` func maximumImportance(n int, roads [][]int) int64 { countMap := make(map[int]int) for _, road := range roads { countMap[road[0]]++ countMap[road[1]]++ } keys := make([]int, n) for i := 0; i < n; i++ { keys[i] = i } sort.SliceStable(keys, func(i, j int) bool { return countMap[keys[i]] > countMap[keys[j]] }) weightMap := make(map[int]int) for _, key := range keys { weightMap[key] = n n-- } var totalImportance int for _, road := range roads { totalImportance += weightMap[road[0]] totalImportance += weightMap[road[1]] } return int64(totalImportance) } ```

Answer 112

Since there will be only one center, find the duplicate node between edges. ``` func findCenter(edges [][]int) int { set := make(map[int]struct{}) for _, edge := range edges { for _, node := range edge { if _, ok := set[node]; ok { return node } set[node] = struct{}{} } } return -1 } ```

Answer 113

Create an **Adjacency Matrix**. Find ancestors from the adjacency matrix. Depth First Search the ancestors of the current vertex, then copy the ancestors of the ancestor to the current vertex. ``` func getAncestors(n int, edges [][]int) [][]int { // Adjacency Matrix. // Edges[1, 0] puts 1 at Adjacency Matrix[0, 1]. // From // 0, 1, 2, 3, 4, 5 // 0 [0, 1, 0, 0, 0, 0] // 1 // To 2 // 3 // 4 // 5 adjacentMatrix := make([][]int, n) for i := 0; i < n; i++ { adjacentMatrix[i] = make([]int, n) } for _, edge := range edges { adjacentMatrix[edge[1]][edge[0]] = 1 } // Create an array with a set for every vertex. ancestors := make([]map[int]struct{}, n) var dfs func(vertex int) map[int]struct{} dfs = func(vertex int) map[int]struct{} { // If ancestors[vertex] is empty, we haven't visited the vertex yet. if ancestors[vertex] == nil { ancestors[vertex] = make(map[int]struct{}) for otherVertex, isAdjacent := range adjacentMatrix[vertex] { if isAdjacent == 1 { // Add the connected vertex to the vertex's ancestor. ancestors[vertex][otherVertex] = struct{}{} // Add the ancestors of the connected vertex to the vertex's ancestor. for k, v := range dfs(otherVertex) { ancestors[vertex][k] = v } } } } return ancestors[vertex] } // Run dfs() and transribe it to the result. result := make([][]int, n) for i := 0; i < n; i++ { for key, _ := range dfs(i) { result[i] = append(result[i], key) } sort.Ints(result[i]) } return result } ```

Answer 114

**Union Find Algorithm**. If cannot unite, the nodes in the current edge already have the same boss. Any edge that tries uniting two nodes that have the same boss is redundant. ``` func findRedundantConnection(edges [][]int) []int { // Read this paragraph first: https://hackmd.io/@CLKO/rkRVS_o-4?type=view // Union Find Algorithm - By Rank. // By rank: If a size of a union is greater than the other union, unite the union that is smaller in size to the greater union. // Set every node to be a separate union at first. // Connect each union when traversing the edges. // boss: [0, 1, 2, 3, 4] // rank: [1, 1, 1, 1, 1] boss := make([]int, len(edges) + 1) for i := 0; i < len(boss); i++ { boss[i] = i } rank := make([]int, len(edges) + 1) for i := 0; i < len(rank); i++ { rank[i] = 1 } // find returns the boss of a union. var find func(node int) int find = func(node int) int { if boss[node] == node { return node } // Find the boss of the boss. root := find(boss[node]) boss[node] = root // Set the boss of the boss to your boss. return root } // unite two unions by rank. var unite func(node1 int, node2 int) bool unite = func(node1 int, node2 int) bool { boss1, boss2 := find(node1), find(node2) if boss1 == boss2 { // Do nothing, they already have the same boss(parent). return false } if rank[boss1] >= rank[boss2] { // Merge union 2 to 1. // Add the size of the smaller-sized union to the greater one. rank[boss1] += rank[boss2] // The new boss for boss2 is now boss1 => Unite 2 to 1. boss[boss2] = boss1 } else { rank[boss2] += rank[boss1] boss[boss1] = boss2 } return true } for _, edge := range edges { // If cannot unite, the nodes in the current edge already have the same boss. // Any edge that tries unite two nodes that have the same boss is redundant. if !unite(edge[0], edge[1]) { return edge } } return []int{-1, -1} // Placeholder, we're guranteed that we'll have a redundant edge. } ```

Answer 115

Create UnionFind structures for Alice and Bob seperately. Go through the edges where they can both traverse. Add the failed unite result to the nodes to remove (failing to unite means that the edge is redundant). ``` func maxNumEdgesToRemove(n int, edges [][]int) int { // Traversable => All nodes have same parent. // Start from the edges that can be traversed by both Alice and Bob. sort.Slice(edges, func(i, j int) bool { return edges[i][0] > edges[j][0] }) // Bob needs to finish the traverse by himself -> Perform Union Find on Bob's graph. // Alice needs to finish the traverse by herself -> Perform Union Find on Alice's graph. // Traverse all edges again and see which node is neither in Bob's graph and Alice's graph (having different union parents). aliceUnion, bobUnion := Union{ Rank: make([]int, n+1), Parent: make([]int, n+1), }, Union{ Rank: make([]int, n+1), Parent: make([]int, n+1), } for i := 0; i <= n; i++ { aliceUnion.Parent[i] = i aliceUnion.Rank[i] = 1 bobUnion.Parent[i] = i bobUnion.Rank[i] = 1 } var edgesToRemove int for _, edge := range edges { switch edge[0] { case 1: edgesToRemove += aliceUnion.Unite(edge[1], edge[2]) case 2: edgesToRemove += bobUnion.Unite(edge[1], edge[2]) case 3: edgesToRemove += (aliceUnion.Unite(edge[1], edge[2]) | bobUnion.Unite(edge[1], edge[2])) } } // Check if Alice and Bob can fully traverse the graph. if aliceUnion.IsConnected(n) && bobUnion.IsConnected(n) { return edgesToRemove } return -1 } type Union struct { Parent []int Rank []int } // Unite two unions. Return 0 if success, 1 otherwise. func (u *Union) Unite(node1 int, node2 int) int { parent1, parent2 := u.Find(node1), u.Find(node2) if parent1 == parent2 { return 1 } if u.Rank[parent1] >= u.Rank[parent2] { u.Parent[parent2] = parent1 u.Rank[parent1] += u.Rank[parent2] } else { u.Parent[parent1] = parent2 u.Rank[parent2] += u.Rank[parent1] } return 0 } func (u *Union) Find(node int) int { if u.Parent[node] == node { return node } root := u.Find(u.Parent[node]) u.Parent[node] = root return root } func (u *Union) IsConnected(n int) bool { for _, rank := range u.Rank { if rank == n { return true } } return false } ```

Answer 116

Check the window consecutively. ``` func threeConsecutiveOdds(arr []int) bool { for i := 0; i <= len(arr) - 3; i++ { if arr[i] % 2 == 1 { count := 1 for j := i + 1; j < len(arr); j++ { if arr[j] % 2 == 1 { count++ } else { break } if count == 3 { return true } } } } return false } ```

Answer 117

Keep track of the location of the critical nodes. ``` func nodesBetweenCriticalPoints(head *ListNode) []int { prevNode := head temp := head.Next // The first node cannot be a critical node. maxDistance, minDistance := 0, int(1e5) firstCriticalIdx, lastCriticalIdx, currNodeIdx := 0, 0, 1 // We are currently at the first possible critical. for temp.Next != nil { // Critical Point: Strictly greater/ smaller than the previous node and the next node. if (temp.Val > prevNode.Val && temp.Val > temp.Next.Val) || (temp.Val < prevNode.Val && temp.Val < temp.Next.Val) { if firstCriticalIdx == 0 { // Do nothing when there isn't any previous critical node. // Store the position of the first critical. firstCriticalIdx = currNodeIdx } else { // MaxDistance is the distance between the rightmost critical and the first (leftmost) critical. maxDistance = currNodeIdx - firstCriticalIdx // MinDistance is the difference between the nodes. minDistance = min(minDistance, currNodeIdx-lastCriticalIdx) } lastCriticalIdx = currNodeIdx } currNodeIdx++ prevNode = temp temp = temp.Next } // When there's no critical node in the list (firstCriticalIdx == 0) or only have one critical node (maxDistance == 0, not updated). if firstCriticalIdx == 0 || maxDistance == 0 { return []int{-1, -1} } return []int{minDistance, maxDistance} } ```

Answer 118

Count the turns. If turns is odd, count from the start with the modulo. If turns is even, count from the back. ``` func passThePillow(n int, time int) int { gap := n - 1 turns := time / gap var person int switch turns % 2 { case 0: person = 1 + time % gap case 1: person = n - time % gap } return person } ```

Answer 119

Simple math. ``` func numWaterBottles(numBottles int, numExchange int) int { var bottlesDrank int for numBottles >= numExchange { bottlesDrank += (numBottles / numExchange) * numExchange numBottles = numBottles / numExchange + numBottles % numExchange } bottlesDrank += numBottles return bottlesDrank } ```

Answer 120

* Use mod. Keep a list and remove accordingly. ``` func findTheWinner(n int, k int) int { // 1. Circular Linked List: Time O(n), Space O(n). // 2. Go directly through the integer list. friends := make([]int, 0) for i := 1; i <= n; i++ { friends = append(friends, i) } toRemove := 0 for len(friends) > 1 { toRemove = (toRemove + k - 1) % len(friends) // Remove the element at start. friends = append(friends[:toRemove], friends[toRemove+1:]...) } return friends[0] } ``` * Solve with formula, read [Josephus Prolem](https://en.wikipedia.org/wiki/Josephus_problem) ``` func findTheWinner(n int, k int) int { var winner int for i := 1; i <= n; i++ { winner = (winner + k) % i } return winner + 1 } ```

Answer 121

* Two Pointers ``` func pairSum(head *ListNode) int { // Two pointers? // Traverse from the start and from the end. nums := make([]int, 0) temp := head for temp != nil { nums = append(nums, temp.Val) temp = temp.Next } var maxSum int i, j := 0, len(nums)-1 for i < j { maxSum = max(maxSum, nums[i]+nums[j]) i++ j-- } return maxSum } ``` * Dequeue

Answer 122

Count accordingly. ``` func averageWaitingTime(customers [][]int) float64 { totalCustomers := len(customers) end := customers[0][0] + customers[0][1] totalWaitTime := customers[0][1] for i := 1; i < len(customers); i++ { if customers[i][0] <= end { totalWaitTime += ((end - customers[i][0]) + customers[i][1]) end += customers[i][1] } else { totalWaitTime += customers[i][1] end = customers[i][0] + customers[i][1] } } return float64(totalWaitTime) / float64(totalCustomers) } ```

Answer 123

* Add or subtract operations accordinginly. ``` func minOperations(logs []string) int { var operations int for _, log := range logs { switch log { case "./": // do nothing continue case "../": // only go back when we are not at root. if operations > 0 { operations-- } default: operations++ } } return operations } ``` * Keep a stack, but no need.

Answer 124

Split path by "/". Append to stack when element is not empty. Pop from stack when encoutner ".." and when stack is not empty. Join the stack with a leading "/". ``` func simplifyPath(path string) string { parts := strings.Split(path, "/") stack := make([]string, 0) for _, part := range parts { if part == "" { continue } switch part { case ".": continue case "..": if len(stack) > 0 { stack = stack[:len(stack) - 1] } default: stack = append(stack, part) } } return "/" + strings.Join(stack, "/") } ```

Answer 125

Stack. Break the string into segments. When encounter "(", create a new segment and append it to the stack. When encounter ")", reverse the top element on the stack, pop it and append to the current latest segment. ``` func reverseParentheses(s string) string { stack := make([][]byte, 0) var last []byte // Initial segment in case we have any before the first parentheses. stack = append(stack, make([]byte, 0)) for i := 0; i < len(s); i++ { switch s[i] { case '(': // Start next segment. stack = append(stack, make([]byte, 0)) case ')': // End of a segment; // Pop the last segment, reverse it, and append it to the previous segment last = stack[len(stack)-1] stack = stack[:len(stack)-1] reverse(last) stack[len(stack)-1] = append(stack[len(stack)-1], last...) default: // Append to current segment stack[len(stack)-1] = append(stack[len(stack)-1], s[i]) } } return string(stack[0]) } func reverse(segment []byte) { i, j := 0, len(segment)-1 for i < j { segment[i], segment[j] = segment[j], segment[i] i++ j-- } } ```

Answer 126

Find lowest common ancestor by comparing path. Find the path from root to start and path from root to destintation separately. Contruct the path from start to dest using the two paths. ``` /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func getDirections(root *TreeNode, startValue int, destValue int) string { // Find lowest common ancestor. // Go from start to LCA. // Go from LCA to dest. var dfs func(node *TreeNode, value int, path *[]byte) bool dfs = func(node *TreeNode, value int, path *[]byte) bool { if node == nil { return false } if value == node.Val { return true } *path = append(*path, 'L') if dfs(node.Left, value, path) { return true } *path = (*path)[:len(*path)-1] *path = append(*path, 'R') if dfs(node.Right, value, path) { return true } *path = (*path)[:len(*path)-1] // This will not happen. // The node definitely exists. return false } pathToStart, pathToDest := make([]byte, 0), make([]byte, 0) dfs(root, startValue, &pathToStart) dfs(root, destValue, &pathToDest) // Find where the difference start. var commonLength int for commonLength < len(pathToStart) && commonLength < len(pathToDest) && pathToStart[commonLength] == pathToDest[commonLength] { commonLength++ } startToDest := make([]byte, 0) for i := 0; i < len(pathToStart) - commonLength; i++ { startToDest = append(startToDest, 'U') } startToDest = append(startToDest, pathToDest[commonLength:]...) return string(startToDest) } ```

Answer 127

Create a map storing the references of each node. Create another set for all the kids. Loop through the map and see which node isn't a kid. That one's the root. ``` func createBinaryTree(descriptions [][]int) *TreeNode { var root *TreeNode nodeMap := make(map[int]*TreeNode) kidMap := make(map[*TreeNode]struct{}) for _, description := range descriptions { if _, ok := nodeMap[description[0]]; !ok { nodeMap[description[0]] = &TreeNode{Val: description[0]} } currNode := nodeMap[description[0]] if _, ok := nodeMap[description[1]]; !ok { nodeMap[description[1]] = &TreeNode{Val: description[1]} } kid := nodeMap[description[1]] kidMap[kid] = struct{}{} if description[2] == 1 { // Left currNode.Left = nodeMap[description[1]] } else { // Right currNode.Right = nodeMap[description[1]] } } for _, description := range descriptions { if _, ok := kidMap[nodeMap[description[0]]]; !ok { root = nodeMap[description[0]] break } } return root } ```

Answer 128

Create two stacks. One for the dominant one when parsing through the original string, the other for parsing the first stack. Count the stack when encounter a 'ab' or 'ba' in the stacks. ``` func maximumGain(s string, x int, y int) int { var dominant, subordinate string var greater, lower int if x > y { dominant, subordinate = "ab", "ba" greater, lower = x, y } else { dominant, subordinate = "ba", "ab" greater, lower = y, x } var score int stack := make([]byte, 0) for i := 0; i < len(s); i++ { if len(stack) > 0 && stack[len(stack) - 1] == dominant[0] && s[i] == dominant[1] { // Pop when encounter a pair of dominant. score += greater stack = stack[:len(stack) - 1] } else { stack = append(stack, s[i]) } } // Read the current stack to another stack and do the same. newStack := make([]byte, 0) for i := 0; i < len(stack); i++ { if len(newStack) > 0 && newStack[len(newStack) - 1] == subordinate[0] && stack[i] == subordinate[1] { score += lower newStack = newStack[:len(newStack) - 1] } else { newStack = append(newStack, stack[i]) } } return score } ```

Answer 129

Create a stack that consumes from the string. When encounter a '(', create a new element to the stack. When encounter a ')', reverse the last element in the stack and append it to the second less element in the stack. Do this until there's only one element in the stack. ``` func reverseParentheses(s string) string { stack := make([][]byte, 0) var last []byte // Initial segment in case we have any before the first parentheses. stack = append(stack, make([]byte, 0)) for i := 0; i < len(s); i++ { switch s[i] { case '(': // Start next segment. stack = append(stack, make([]byte, 0)) case ')': // End of a segment; // Pop the last segment, reverse it, and append it to the previous segment last = stack[len(stack)-1] stack = stack[:len(stack)-1] reverse(last) stack[len(stack)-1] = append(stack[len(stack)-1], last...) default: // Append to current segment stack[len(stack)-1] = append(stack[len(stack)-1], s[i]) } } return string(stack[0]) } func reverse(segment []byte) { i, j := 0, len(segment)-1 for i < j { segment[i], segment[j] = segment[j], segment[i] i++ j-- } } ```

Answer 130

Sort the robot by it's position. Put it to the stack when a robot is going right. Pop element from the stack when collide. Sort the result by order. ``` func survivedRobotsHealths(positions []int, healths []int, directions string) []int { // See: https://leetcode.com/problems/asteroid-collision // Form the bot objects and sort it. robots := make(Bots, 0) for i := 0; i < len(positions); i++ { robots = append(robots, Bot{Position: positions[i], Health: healths[i], Direction: string(directions[i]), Order: i}) } sort.Sort(robots) stack := make(Bots, 0) for i := 0; i < len(robots); i++ { currRobot := robots[i] succeeded := true for len(stack) != 0 && currRobot.Direction == "L" && stack[len(stack)-1].Direction == "R" { if currRobot.Health > stack[len(stack)-1].Health { currRobot.Health-- stack = stack[:len(stack)-1] } else if currRobot.Health < stack[len(stack)-1].Health { stack[len(stack)-1].Health-- succeeded = false break } else { stack = stack[:len(stack)-1] succeeded = false break } } if succeeded { stack = append(stack, currRobot) } } sort.Slice(stack, func(i, j int) bool { return stack[i].Order < stack[j].Order }) health := make([]int, 0) for _, bot := range stack { health = append(health, bot.Health) } return health } type Bots []Bot type Bot struct { Position int Health int Direction string Order int } func (b Bots) Len() int { return len(b) } func (b Bots) Less(i, j int) bool { return b[i].Position < b[j].Position } func (b Bots) Swap(i, j int) { b[i], b[j] = b[j], b[i] } ```

Answer 131

* A parent node receives the distance list of children, then every parent node will validate the condition of left_distance + right_distance <= distance. The base case: When reach to leaf node, we return [1]. ``` ``` * Start DFS from each leaf node. stop the DFS when the number of steps done > distance. Note that all pairs will be counted twice so divide the answer by 2. ``` /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func countPairs(root *TreeNode, distance int) int { var pairs int leaves := make(map[*Tree]struct{}) var findLeaves func(node *Tree) findLeaves = func(node *Tree) { if node == nil { return } if node.Left == nil && node.Right == nil { leaves[node] = struct{}{} return } findLeaves(node.Left) findLeaves(node.Right) } // Start DFS from each leaf node. stop the DFS when the number of steps done > distance. var dfs func(node *Tree, currDist int, visited map[*Tree]struct{}) dfs = func(node *Tree, currDist int, visited map[*Tree]struct{}) { if node == nil { return } if _, ok := visited[node]; ok { return } if currDist > distance { return } if _, ok := leaves[node]; ok && currDist != 0 && currDist <= distance { pairs++ return } visited[node] = struct{}{} dfs(node.Parent, currDist + 1, visited) dfs(node.Left, currDist + 1, visited) dfs(node.Right, currDist + 1, visited) } // Form a tree with parent. t := newTree(root, nil) findLeaves(t) for leaf, _ := range leaves { visited := make(map[*Tree]struct{}) dfs(leaf, 0, visited) } return pairs / 2 } type Tree struct { Val int Parent *Tree Left *Tree Right *Tree } func newTree(node *TreeNode, parent *Tree) *Tree { if node == nil { return nil } t := &Tree{ Parent: parent, Val: node.Val, } t.Left = newTree(node.Left, t) t.Right = newTree(node.Right, t) return t } ```

LeetCode Freedom Flashcards

Getting into Google