1
Q
@242. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.
A
- Count with hashmap. Substract counts when traverse second string. All value of hashmap should eventually be 0.
- Use byte - ‘a’ to create an indexed array indicating the frequencies. Compare the two arrays.
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
var sArr, tArr [26]int
for i := 0; i < len(s); i++ {
// index in sArr is s[i] - 'a'
sArr[s[i] - 'a']++
// index in tArr is t[i] - 'a'
tArr[t[i] - 'a']++
}
return sArr == tArr
}
2
Q
@424. Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
1 <= s.length <= 10^5
s consists of only uppercase English letters.
0 <= k <= s.length
A
Sliding window. (WindowSize - Most frequent Element count in window) = Characters that need to be replaced. If Characters that need to be replaced is greater than k, move left pointer of window.
3
Q
@11. Container with most water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
A
Two Pointers. Compare left height and right height. Move the lower height one step forward. Compare the previous stored maxArea with the new area.
The logic for moving the pointers:
Scenario A: Moving the one with higher height.
1. We move to a higher height => Doesn’t matter, the height of the area is still determined by the lower one, since we decreased (right - left), the area is smaller.
2. We move to an equal height => Doesn’t matter, the area is smaller due to decreased (right - left).
3. Lower height => Not considerable, we always get a lower height.
Scenario B: Moving the one with the lower height. 1. We move to an equal height => Doesn't matter, the area is smaller due to decreased (right - left). 2. We move to a lower height => Not considerable, we always get a lower height. 3. We move to a higher height => Wwe have a `chance` of getting a greater area, but we don't know more about it since (right - left) is also an issue With all the scenarios given, moving the lower height one step forward and compare with the current max area is the solution.
func maxArea(height []int) int {
area := func(left, right, leftHeight, rightHeight int) int {
// The area is determined by the bottleneck from the lower between leftHeight and rightHeight
return (right - left) * min(leftHeight, rightHeight)
}
i, j := 0, len(height) - 1
// How do we update our left and right pointers?
// Minimum height is the bottleneck, we are trying to find a better bottleneck.
// For example, left height = 1, right height = 7
// We now assume that right height is good, and we want to optimize the answer by finding a better left height, move left height and compare again.
var maxArea int
for i < j {
maxArea = max(maxArea, area(i, j, height[i], height[j]))
if height[i] < height[j] {
i++
} else {
j--
}
}
return maxArea
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
4
Q
@Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.
Example 1:
Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).
1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.
A
- Use byte - ‘a’ to create an indexed array indicating the frequencies. Array is comparable in Go. Compare the two arrays.
func checkInclusion(s1 string, s2 string) bool {
windowSize := len(s1)
if len(s2) < windowSize {
return false
}
// Create two arrays to compare.
var s1Arr [26]int
for i := range s1 {
// All lowercases. rune 'a' is 97. rune 'b' is 98. 98-97 means adding one to bucket 1 in the array.
s1Arr[s1[i] - 'a']++
}
var s2Arr [26]int
var prevHeadIndex int
for r := range s2 {
// Remove head from s2Arr.
prevHeadIndex = r - windowSize
if prevHeadIndex >= 0 {
s2Arr[s2[prevHeadIndex] - 'a']--
}
// Add current new element to s2Arr. r is the new tail index.
s2Arr[s2[r] - 'a']++
if s1Arr == s2Arr {
return true
}
}
return false
}- Create a hashmap that helps check if the window is permutation of s1.
- TLE. Sort string and check if the window is permutation of s1.
5
Q
@155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- void push(int val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
You must implement a solution within O(1) time for each function
-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
A
Create a normal stack and a monotonic decreasing stack that keeps track of the minimum values. The minimum value is always the rightmost value of the monotonic decreasing stack.
6
Q
@191. Number of 1 Bits.
Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
A
Loop the following: Compare unit digits with 1 (0001)using &. Return value will be either 1 ( true ) or 0 ( false ). If result is 1, add one to count.
func hammingWeight(n int) int {
var ones int
// AND with 1.
for n != 0 {
if n & 1 == 1 {
ones++
}
n >>= 1
}
return ones
}& and»_space;
7
Q
@150. Evaluate Reverse Polish Notation
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
- The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.
- Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
- 1 <= tokens.length <= 10^4
- tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].
A
Create a stack that supports Pop().
Do the following recursively until the left and right value of the first operator is generated:
Pop() last token ( Head ) from stack.
If the token is an Operator, find left and right recursively.
Ex: [4, 3, *, 13, 5, /, +]
stack = [4, 3, *, 13, 5, /, +]
first op = +, stack = [4, 3, *, 13, 5, /]
left = eval([4, 3, *, 13, 5, /])
second op = /
left = 5, right = 13, return 2, stack = [4, 3, *]
right = eval([4, 3, 8])
third op = *
left = 4, right = 3, return 12, stack = []
firstOp = +, left = 2, right = 12, return 14.
8
Q
@22 Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
1 <= n <= 8
A
Backtracking. Keep track of the open and closing parentheses counts.
* Only add Open parentheses if openCount < n
* Only add a closing parentheses if closeCount < openCount
* Valid if openCount == closeCount == n, return
func generateParenthesis(n int) []string {
open, close := "(", ")"
openCount, closeCount := 1, 0
result := make([]string, 0)
// Declare the function
var generate func(openCount, closeCount int, currStr string)
// Define the function
generate = func(openCount, closeCount int, currStr string) {
if openCount > n {
// End the recursive call when openCount exceeds n: Too many Open Brackets.
return
}
if closeCount > openCount {
// End the recursive call when closeCount exceeds openCount: Too many Close Brackets.
return
}
// Append to result (this is a shared slice) when we reach a valid string.
if openCount == n && closeCount == n {
result = append(result, currStr)
return
}
generate(openCount+1, closeCount, fmt.Sprintf("%s%s",currStr, open))
generate(openCount, closeCount+1, fmt.Sprintf("%s%s",currStr, close))
}
// Start generating strings from '('.
generate(openCount, closeCount, "(")
return result
}Backtracking is used when we need to check all the possible conditions and also want to cut the check early off. It is basically a depth first search with conditions.
9
Q
@739 Daily Temperature
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
A
Create a stack that stores the index of days that haven’t met it’s condition. Compare the head ( temperatures[s.head()] ) with todays temperature. If the teperature is greater than the head, pop the head from the stack (meaning that it reaches condition and doesn’t have to be compared again). The days would be today - the day it was stored in the stack (todayIdx - storedIdx).
func dailyTemperatures(temperatures []int) []int {
result := make([]int, len(temperatures))
s := make(stack, 0)
for idx, t := range temperatures {
for s.length() > 0 && t > temperatures[s.head()] {
poppedIdx := s.pop()
result[poppedIdx] = idx - poppedIdx
}
// Add the current number to stack
s.push(idx)
}
return result
}
type stack []int
func (s *stack) push(num int) {
*s = append(*s, num)
}
func (s *stack) pop() int {
if s.length() > 0 {
poppedIndex := (*s)[len(*s) - 1]
*s = (*s)[:len(*s) - 1]
return poppedIndex
}
return -1
}
func (s *stack) length() int {
return len(*s)
}
func (s *stack) head () int {
return (*s)[len(*s) - 1]
}Stack is crazy.
10
Q
@853 Car Fleet
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.
n == position.length == speed.length
1 <= n <= 10^5
0 < target <= 10^6
0 <= position[i] < target
All the values of position are unique.
0 < speed[i] <= 10^6
A
Sort the car by position. The ones that are closer to the target are the dominating ones. If a second car reaches the target faster than the dominating one, it joins the fleet. Thus create a monotonic increasing stack that stores the time to destination for dominating cars. Only update when the time to the destination for a second car is greater than the head of the stack (the current dominating car), meaning that the car is slower and cannot catch up, this itself is a new fleet.
(position, speed, timeToTarget)
cars =
(10, 2, 1) sort (0,1,12)
(8, 4, 1) (3,3, 3)
(0, 1, 12) (5,1,7)
(5, 1, 7) (8,4,1)
(3, 3, 3) (10,2,1)
- 10, stack [1]
- 8, stack[1]
- 5, stack[1,7]
- 3, stack[1,7]
- 0, stack[1, 7, 12]
(0,1)–(3,3)–(5,1)—(8,4)–(10, 2)—12>
dom dom dom
func carFleet(target int, position []int, speed []int) int {
// fleets is a stack that stores the dominating fleet throughout the process.
// It is a monotonically increasing stack.
f := make(fleets, 0)
c := cars{
pos: position,
speed: speed,
}
// Sort the cars by position. The ones that are closer to the target are the dominators to the previous one.
sort.Sort(c)
c.timeToDest = make([]float64, len(c.pos))
for idx := range c.pos {
c.timeToDest[idx] = float64(target - c.pos[idx]) / float64(c.speed[idx])
}
for i := len(c.timeToDest) - 1; i >= 0; i-- {
// Only push the time to the stack when the stack is empty or the time to the destination is greater than the previous one (head)
// We ignore the time to target that is faster than the dominating one => Meaning that it joins the fleet ahead.
if len(f) == 0 || c.timeToDest[i] > f.head() {
f.push(c.timeToDest[i])
}
}
return len(f)
}
type cars struct {
pos []int
speed []int
timeToDest []float64
}
func (c cars) Len() int { return len(c.pos) }
func (c cars) Less(i, j int) bool { return c.pos[i] < c.pos[j] }
func (c cars) Swap(i, j int) {
c.pos[i], c.pos[j] = c.pos[j], c.pos[i]
c.speed[i], c.speed[j] = c.speed[j], c.speed[i]
}
type fleets []float64
func (f *fleets) push(timeToDest float64) {
*f = append(*f, timeToDest)
}
func (f *fleets) head() float64 {
if len(*f) > 0 {
return (*f)[len(*f)-1]
}
return -1.0
}
11
Q
@74 Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
A
Binary search the row first. Then Binary search the number within the target row. Check edge cases first (Out of bound and greater than the head of the tail row.). If the target is greater or equal to the head of the midRow, move headRow to mid, else, move the tailRow below mid(cuz it is not encluded).
12
Q
@704 Binary Search
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.
A
Binary search. Take special care for the boundary. Always use inclusive for both ends. ‘<=’ is for arrays that only has one element.
func search(nums []int, target int) int {
// Head and tail all inclusive.
// Everything left of head is smaller than target, everything right of tail is greater or equal to the target.
head, tail := 0, len(nums) - 1
var mid int
// '<=' is for arrays that only has one element.
for head <= tail {
mid = (head + tail) / 2
switch {
case nums[mid] == target:
return mid
case nums[mid] > target:
tail = mid - 1
case nums[mid] < target:
head = mid + 1
}
}
return -1
}
13
Q
@875 Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
A
Binary search. Search for all possible value util the lowest k is found. k starts from 1 and will never exceed the maximum value in piles.
func minEatingSpeed(piles []int, h int) int {
// k starts from 1 an will never exceed the maximum value in piles.
head, tail := 1, maxInPiles(piles) // O(n)
var mid, n int
for head < tail { // O(n^2)
mid = (head + tail) / 2
n = need(piles, mid) // O(n)
switch {
case n > h:
head = mid + 1
case n <= h:
// Always looking for a smaller k, we might have a smaller one on the left.
tail = mid
}
}
return tail
}
func maxInPiles(piles []int) int {
maximum := piles[0]
for i := range piles {
maximum = max(maximum, piles[i])
}
return maximum
}
func need(piles []int, possibleK int) int {
var n int
for i := range piles {
n += int(math.Ceil(float64(piles[i])/ float64(possibleK)))
}
return n
}
Take care of the bounds. It’s tricky.
14
Q
@2 Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
A
Create a new node that traverses when the nodes are adding.
In 10 based system there will be addOns, which will always be 1.
The value of the node will be either
* When l1 != nil && l2 != nil, value = l1.Val + l2.Val + addOn
* When l1 == nil && l2 != nil, value = l2.Val + addOn
* When l1 != nil && l2 == nil, value = l1.Val + addOn
* When both is empty, it’s out of the loop.
After it is out of the loop, if the addOn is not zero, create a new node with value 1 (When the value of the last node is greater than 10, 要進位)
15
Q
@138 Copy List With Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Ex1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
0 <= n <= 1000
-104 <= Node.val <= 10^4
Node.random is null or is pointing to some node in the linked list.
A
Since we cannot point to the orginal one, we have to have the address of the new nodes to point to. Create a hashmap that stores the relationship between the old and new (a <-> a’). Use the relations to get temp.Random’ from temp.Random.
13 (temp) -> 13’ (newNode)
|
v
7 (temp.Random)
and since we know who 7 points to (7’), we can know who 13’ should point to, which is 7’, fetched by 7.
func copyRandomList(head *Node) *Node {
relations := make(map[*Node]*Node)
dummy := new(Node)
nNode := dummy
temp := head
for temp != nil {
// Create newNode
newNode := &Node{Val: temp.Val}
relations[temp] = newNode
// Assign to the next node
nNode.Next = newNode
// Jump to next node.
nNode = nNode.Next
temp = temp.Next
}
temp = head
nNode = dummy.Next
for temp != nil {
nNode.Random = relations[temp.Random]
temp = temp.Next
nNode = nNode.Next
}
return dummy.Next
}The relations between new and old!
16
Q
@19 Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example2:
Input: head = [1,2,3,4,5], n = 5
Output: [2,3,4,5]
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
A
Count the length of the list first.
If n == length, remove the head (return head.Next); else traverse till the previous one, change the next of the previous one to the next of the next node (temp.Next = temp.Next.Next).
func removeNthFromEnd(head *ListNode, n int) *ListNode {
listLength := length(head)
if n == listLength {
return head.Next
}
prevIdx := listLength - n - 1
var idx int
temp := head
for temp != nil {
if idx == prevIdx {
temp.Next = temp.Next.Next
}
temp = temp.Next
idx++
}
return head
}
func length(head *ListNode) int {
var count int
temp := head
for temp != nil {
count++
temp = temp.Next
}
return count
}
17
Q
@141 Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
The number of the nodes in the list is in the range [0, 104].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.
A
- Use a set to check if a node already exist => Space: O(n)
func hasCycle(head *ListNode) bool {
nodeSet := make(map[*ListNode]struct{})
temp := head
var exist bool
for temp != nil {
if _, exist = nodeSet[temp]; exist {
return true
} else {
nodeSet[temp] = struct{}{}
}
temp = temp.Next
}
return false
}- Use fast and slow pointer, if they point to the same node (since if there’s a cycle the fast pointer will catch up with the slow one from the back), has cycle.
func hasCycle(head *ListNode) bool {
fast, slow := head, head
for fast != nil && fast.Next != nil && slow != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}
18
Q
@287 Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.
A
- (Best Solution) Floyd’s Cycle Detection
func findDuplicate(nums []int) int {
var slow, fast int
// Find the intersection point of the two pointers
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
// Find the entrance to the cycle
slow = 0
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
- Hashset: Return the number if it is already in set => Time: O(n), Space: O(n)
func findDuplicate(nums []int) int {
set := make(map[int]struct{})
for i := range nums {
if _, ok := set[nums[i]]; ok {
return nums[i]
} else {
set[nums[i]] = struct{}{}
}
}
return 0
}- Sort and compare the adjacent elements => Time: O(nlogn), Space: O(1)
func findDuplicate(nums []int) int {
sort.Ints(nums)
for i := 1; i < len(nums); i ++ {
if nums[i] == nums[i - 1] {
return nums[i]
}
}
return 0
}Floyd’s Cycle Detection is the best
19
Q
@146 LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
A
Create a data structure that can store the timestamp of the keys.
- A queue that removes the head when full.
- A doubly linked list.
Get(): If key is in cache, update timestamp (For doubly linked List, move key to head). Else, return -1.
Put(): If key is in cache, update timestamp. If key not in cache and cache is full, remove the least used element (for a queue it is the head, for the doubly linked list it is the back), delete the last element from cache. Create a new timestamp for element.
type LRUCache struct {
cache map[int]*list.Element
linklist *list.List
capacity int
}
type Obj struct {
Key int
Value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
cache: make(map[int]*list.Element, capacity),
linklist: list.New(),
capacity: capacity,
}
}
func (this *LRUCache) Get(key int) int {
if elem, ok := this.cache[key]; ok {
// Put the element to head.
this.linklist.MoveToFront(elem)
return elem.Value.(Obj).Value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if elem, ok := this.cache[key]; ok {
// If the key is in list, remove the old timestamp.
this.linklist.Remove(elem)
} else if len(this.cache) == this.capacity {
// Reached Capacity
// Last element of the linked list is the least used.
leastUsedEle := this.linklist.Back()
// Remove the last element from the list.
this.linklist.Remove(leastUsedEle)
// Remove the last element from the map.
delete(this.cache, leastUsedEle.Value.(Obj).Key)
}
// Create a new obj
newObj := Obj{
Key: key,
Value: value,
}
newEle := this.linklist.PushFront(newObj) // New Obj is the recently used, put to head.
this.cache[key] = newEle
return
}We have list in Go Standard Library. It updates the node by directly updating the Next, and Prev pointer.
MoveToFront: O(1)
Remove:O(1)
PushFront: O(1)
20
Q
@226 Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
A
Rotate recursively. Observe the base case, where the recursive function should end.
Base case: When node is nil.
Rotate left and right.
func invertTree(root *TreeNode) *TreeNode {
// If node is nil, return nil. Else rotate left and right.
if root != nil {
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
return nil
}
21
Q
@104 Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
A
Add height recursively. Add 1 at every layer when node is not nil. Compare the maxDepth(node.Left) and maxDepth(node.Right) before adding it to the current height.
Base Case: When node is nil, then maxDepth(nil) = 0
func maxDepth(root *TreeNode) int {
// DFS.
if root == nil {
return 0
}
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}Always think of the base case first.
22
Q
@543 Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100
A
Compare the diameter and the local diameter recursively.
Diameter = CurrMaxLeftHeight, CurrMaxRightHeight
Return max(currMaxLeftHeight, currMaxRightHeight) to the parent. The parent will use it as either it’s currMaxLeftHeight or currMaxRightHeight.
func diameterOfBinaryTree(root *TreeNode) int {
var diameter int
// dfs finds the maxDepth of each node and compares the local diameter with the stored diameter.
// Local diameter is the leftHeight + rightHeight.
// Only add 1 to the height when a leaf exist.
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
var leftHeight, rightHeight int
if node.Left != nil {
leftHeight = dfs(node.Left) + 1
}
if node.Right != nil {
rightHeight = dfs(node.Right) + 1
}
diameter = max(diameter, leftHeight + rightHeight)
return max(leftHeight, rightHeight)
}
dfs(root)
return diameter
}Diameter = leftHeight + rightHeight
23
Q
@110 Balanced Binary Tree
Given a binary tree, determine if it is
height-balanced.
Ex1:
Input: root = [3,9,20,null,null,15,7]
Output: true
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4
A
Do the following recursively until the base case: Check the height difference every layer. If height difference is smaller than 2, the node is balanced. Return the height of the subroot to the next layer, and compare again.
func isBalanced(root *TreeNode) bool {
// Return height, isBalanced
var dfs func(node *TreeNode) (int, bool)
dfs = func(node *TreeNode) (int, bool) {
if node == nil {
return 0, true
}
leftHeight, leftIsBalanced := dfs(node.Left)
rightHeight, rightIsBalanced := dfs(node.Right)
if leftHeight - rightHeight >= 2 || rightHeight - leftHeight >= 2 {
return -1, false
}
return max(leftHeight, rightHeight) + 1, leftIsBalanced && rightIsBalanced
}
_, rootBalanced := dfs(root)
return rootBalanced
}Depth First Search
24
Q
@100 Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Ex1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Ex2:
Input: p = [1,2], q = [1,null,2]
Output: false
The number of nodes in both trees is in the range [0, 100].
-10^4 <= Node.val <= 10^4
A
Do the following recursively until the base case: Check if the node value is the same. If the node value is the same, compare the children.
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
// In case one of the nodes is nil.
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)
}Depth First Search
25
# @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
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)
}
```
26
# @235 Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Ex1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Ex2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Ex3:
Input: root = [2,1], p = 2, q = 1
Output: 2
## Footnote
* The number of nodes in the tree is in the range [2, 10^5].
* -10^9 <= Node.val <= 10^9
* All Node.val are unique.
* p != q
* p and q will exist in the BST.
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.
27
# @102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Ex1:
Input: root = [3,9,20,4,615,7]
Output: [[3],[9,20],[4,6,15,7]]
## Footnote
* The number of nodes in the tree is in the range [0, 2000].
* -1000 <= Node.val <= 1000
**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.
28
# @199. Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Ex1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Ex2:
Input: root = [1,null,3]
Output: [1,3]
## Footnote
* The number of nodes in the tree is in the range [0, 100].
* -100 <= Node.val <= 100
**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
}
```
29
# @1448 Count Good Nodes in Binary Tree
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Ex1:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
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
}
```
30
# @230. Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
## Footnote
The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4
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**
31
# @98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
## Footnote
The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1
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
32
# @124. Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Ex1:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
## Footnote
The number of nodes in the tree is in the range [1, 3 * 10^4].
-1000 <= Node.val <= 1000
**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.
33
# @105. Contruct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
## Footnote
* 1 <= preorder.length <= 3000
* inorder.length == preorder.length
* -3000 <= preorder[i], inorder[i] <= 3000
* preorder and inorder consist of unique values.
* Each value of inorder also appears in preorder.
* preorder is guaranteed to be the preorder traversal of the tree.
* inorder is guaranteed to be the inorder traversal of the tree.
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
34
# @703. Kth Largest Element In a Stream
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Implement KthLargest class:
KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.
Example 1:
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
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);
*/
```
35
# @78 Subsets
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
## Footnote
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.
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
}
```
36
# @39. Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
## Footnote
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40
**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
}
```
37
# @79. Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
## Footnote
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
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
}
```
38
# @215. Kth Largest Element in an array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
## Footnote
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
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
}
}
}
}
```
39
# @1046. Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
## Footnote
1 <= stones.length <= 30
1 <= stones[i] <= 1000
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
}
}
}
```
40
# @621. Task Scheduler
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.
Example 2:
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
With a cooling interval of 1, you can repeat a task after just one other task.
## Footnote
1 <= tasks.length <= 10^4
tasks[i] is an uppercase English letter.
0 <= n <= 100
* **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. 算出最少需要多少格剩下就是隨便塞。
41
# @973. K closest to origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
## Footnote
1 <= k <= points.length <= 10^4
-10^4 <= xi, yi <= 10^4
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)
}
}
```
42
# @46. Permutation
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
## Footnote
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
**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
}
```
43
# @40. Combination Sum 2
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[[1,1,6], [1,2,5], [1,7], [2,6]]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[[1,2,2], [5]]
## Footnote
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
**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.
44
# @17. Letter Combinations of a phone number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
```
letterMap := map[byte]string{
'2': "abc", '3': "def", '4': "ghi", '5': "jkl",
'6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
}
```
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
## Footnote
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].
**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.
45
# @90. Subsets 2
Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
## Footnote
1 <= nums.length <= 10
-10 <= nums[i] <= 10
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
}
```
46
# @200. Number of islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
## Footnote
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
**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
}
```
47
# @208. Implement a trie
A **trie** (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
## Footnote
1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.
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
}
```
48
# @695 Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
## Footnote
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1
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
}
```
49
# @133. Clone Graph
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
## Footnote
The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
* **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)
}
```
50
# @994. Rotten Orange
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
## Footnote
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.
**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
}
```
51
# @70 Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
## Footnote
1 <= n <= 45
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.
52
# @746. Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
## Footnote
2 <= cost.length <= 1000
0 <= cost[i] <= 999
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])
}
```
53
# @198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
## Footnote
1 <= nums.length <= 100
0 <= nums[i] <= 400
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
}
```
54
# @213. House Robber 2
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
## Footnote
1 <= nums.length <= 100
0 <= nums[i] <= 1000
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
}
```
55
# @55. Jump Game
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
## Footnote
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
* 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]
}
```
56
# @53. Maximum Subarray
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
| Follow up: If you have figured out the O(n) solution, try coding another
## Footnote
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
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
}
```
57
# @134. Gas Station
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
## Footnote
n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
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
}
```
58
# @5. Longest Palindromic Substring
Given a string s, return the longest
palindromic
substring
in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
## Footnote
1 <= s.length <= 1000
s consist of only digits and English letters.
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'
59
# @647. Palindromic Substring
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
## Footnote
1 <= s.length <= 1000
s consists of lowercase English letters.
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'
60
# @1899. Merge Triplets to Form Target TripletA triplet is an array of thr
A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.
To obtain target, you may apply the following operation on triplets any number of times (possibly zero):
Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].
Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.
Example 1:
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.
Example 2:
Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.
Example 3:
Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.
## Footnote
1 <= triplets.length <= 10^5
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000
**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
}
```
61
# @91. Decode Ways
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
## Footnote
1 <= s.length <= 100
s contains only digits and may contain leading zero(s).
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)
}
```
62
# @2243. Calculate Digit Sum of a String
You are given a string s consisting of digits and an integer k.
A round can be completed if the length of s is greater than k. In one round, do the following:
Divide s into consecutive groups of size k such that the first k characters are in the first group, the next k characters are in the second group, and so on. Note that the size of the last group can be smaller than k.
Replace each group of s with a string representing the sum of all its digits. For example, "346" is replaced with "13" because 3 + 4 + 6 = 13.
Merge consecutive groups together to form a new string. If the length of the string is greater than k, repeat from step 1.
Return s after all rounds have been completed.
Example 1:
Input: s = "11111222223", k = 3
Output: "135"
Explanation:
- For the first round, we divide s into groups of size 3: "111", "112", "222", and "23".
Then we calculate the digit sum of each group: 1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5.
So, s becomes "3" + "4" + "6" + "5" = "3465" after the first round.
- For the second round, we divide s into "346" and "5".
Then we calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5.
So, s becomes "13" + "5" = "135" after second round.
Now, s.length <= k, so we return "135" as the answer.
Example 2:
Input: s = "00000000", k = 3
Output: "000"
Explanation:
We divide s into "000", "000", and "00".
Then we calculate the digit sum of each group: 0 + 0 + 0 = 0, 0 + 0 + 0 = 0, and 0 + 0 = 0.
s becomes "0" + "0" + "0" = "000", whose length is equal to k, so we return "000".
## Footnote
1 <= s.length <= 100
2 <= k <= 100
s consists of digits only.
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)
}
```
63
# @678. Valid Parenthesis String
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "(*)"
Output: true
Example 3:
Input: s = "(*))"
Output: true
## Footnote
* 1 <= s.length <= 100
* s[i] is '(', ')' or '*'
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
}
```
64
# @1480. Running Sum of 1D array
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
## Footnote
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
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
}
```
65
# @338. Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
## Footnote
0 <= n <= 10^5
* 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
}
```
66
# @190. Reverse Bit
Reverse bits of a given 32 bits unsigned integer.
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Example 1:
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
## Footnote
The input must be a binary string of length 32
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
}
```
67
# @268. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
| Implement a solution using only O(1) extra space complexity an
## Footnote
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.
* 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
}
```
68
# @371. Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
## Footnote
-1000 <= a, b <= 1000
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
}
```
69
# @461. Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.
Example 1:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
Example 2:
Input: x = 3, y = 1
Output: 1
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
}
```
70
# @693. Binary Number with Alternating Bits
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
Example 1:
Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101
Example 2:
Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.
Example 3:
Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.
## Footnote
1 <= n <= 2^31 - 1
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
}
```
71
# @139. Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
## Footnote
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
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]
}
```
72
# @7. Reverese Integer
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
## Footnote
-2^31 <= x <= 2^31 - 1
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
}
```
73
# @50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
## Footnote
* -100.0 < x < 100.0
* -2^31 <= n <= 2^31-1
* n is an integer.
* Either x is not zero or n > 0.
* -10^4 <= x^n <= 10^4
* 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
}
```
74
# @1732. Find the Highest Altitude
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
Example 1:
Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
## Footnote
* n == gain.length
* 1 <= n <= 100
* -100 <= gain[i] <= 100
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
}
```
75
# @1456. Maximum Number of Vowels in a SubString of a Given Length
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
Example 2:
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.
Example 3:
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.
## Footnote
1 <= s.length <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length
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
}
```
76
# @1679. Max Number of K-Sum Pairs
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
Example 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
Example 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
## Footnote
* 1 <= nums.length <= 10^5
* 1 <= nums[i] <= 10^9
* 1 <= k <= 10^9
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
}
```
77
# @2390. Removing Stars From a String
You are given a string s, which contains stars *.
In one operation, you can:
Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
## Footnote
* 1 <= s.length <= 105
* s consists of lowercase English letters and stars *.
* The operation above can be performed on s.
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)
}
```
78
# @872. Leaf-Similar Tree
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
Example 1:
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Example 2:
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
## Footnote
* The number of nodes in each tree will be in the range [1, 200].
* Both of the given trees will have values in the range [0, 200].
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
}
```
79
# @841. Keys and Rooms
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
## Footnote
* n == rooms.length
* 2 <= n <= 1000
* 0 <= rooms[i].length <= 1000
* 1 <= sum(rooms[i].length) <= 3000
* 0 <= rooms[i][j] < n
* All the values of rooms[i] are unique.
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
}
```
80
# @701. Insert Into a Binary Search Tree
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
## Footnote
* The number of nodes in the tree will be in the range [0, 10^4].
* -10^8 <= Node.val <= 10^8
* All the values Node.val are unique.
* -10^8 <= val <= 10^8
* It's guaranteed that val does not exist in the original BST.
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
}
```
81
# @283. Move Zeros
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
| Follow up: Could you minimize the total number of operations done?
## Footnote
* 1 <= nums.length <= 10^4
* -2^31 <= nums[i] <= 2^31 - 1
* 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++
}
}
}
```
82
# @2095. Delete the Middle Node of a Linked List
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Example 1:
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.
Example 2:
Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.
## Footnote
* The number of nodes in the list is in the range [1, 10^5].
* 1 <= Node.val <= 10^5
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
}
```
83
# @1161. Maximum Level Sum of a Binary Tree
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.
Example 1:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
## Footnote
* The number of nodes in the tree is in the range [1, 10^4].
* -10^5 <= Node.val <= 10^5
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
}
```
84
# @450. Delete node in BST
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0
Output: []
## Footnote
* The number of nodes in the tree is in the range [0, 10^4].
* -10^5 <= Node.val <= 10^5
* Each node has a unique value.
* root is a valid binary search tree.
* -105 <= key <= 10
*
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
}
```
85
# @3162. Find the number of good pairs
You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.
A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).
Return the total number of good pairs.
Example 1:
Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1
Output: 5
Explanation:
The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).
Example 2:
Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3
Output: 2
Explanation:
The 2 good pairs are (3, 0) and (3, 1).
## Footnote
* 1 <= n, m <= 50
* 1 <= nums1[i], nums2[j] <= 50
* 1 <= k <= 50
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
}
```
86
# @3163. String Compression lll
Given a string word, compress it using the following algorithm:
Begin with an empty string comp. While word is not empty, use the following operation:
Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
Append the length of the prefix followed by c to comp.
Return the string comp.
Example 1:
Input: word = "abcde"
Output: "1a1b1c1d1e"
Explanation:
Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.
For each prefix, append "1" followed by the character to comp.
Example 2:
Input: word = "aaaaaaaaaaaaaabb"
Output: "9a5a2b"
Explanation:
Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.
For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
For prefix "aaaaa", append "5" followed by "a" to comp.
For prefix "bb", append "2" followed by "b" to comp.
## Footnote
* 1 <= word.length <= 2 * 10^5
* word consists only of lowercase English letters.
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)
}
```
87
# @724. Pivot Index
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Example 1:
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
Example 2:
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Example 3:
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0
## Footnote
1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
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
}
```
88
# @1208. Get Equal Substrings Within Budget
You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).
Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.
Example 1:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.
Example 2:
Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to character in t, so the maximum length is 1.
Example 3:
Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You cannot make any change, so the maximum length is 1.
## Footnote
* 1 <= s.length <= 10^5
* t.length == s.length
* 0 <= maxCost <= 10^6
* s and t consist of only lowercase English letters.
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
}
```
89
# @1404. Number of Steps to Reduce a Num in Binary Representation to One
Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:
If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.
It is guaranteed that you can always reach one for all test cases.
Example 1:
Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
Example 2:
Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.
Example 3:
Input: s = "1"
Output: 0
| Casting the string directly back to integer causes TLE.
## Footnote
* 1 <= s.length <= 500
* s consists of characters '0' or '1'
* s[0] == '1'
* 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
}
```
90
# @62. Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
## Footnote
1 <= m, n <= 100
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]
}
```
91
# @6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = "A", numRows = 1
Output: "A"
## Footnote
* 1 <= s.length <= 1000
* s consists of English letters (lower-case and upper-case), ',' and '.'.
* 1 <= numRows <= 1000
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)
}
```
92
# @260. Single Number lll
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0]
Output: [-1,0]
Example 3:
Input: nums = [0,1]
Output: [1,0]
## Footnote
* 2 <= nums.length <= 3 * 10^4
* -2^31 <= nums[i] <= 2^31 - 1
* Each integer in nums will appear twice, only two integers will appear once.
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}
}
```
93
# @1768. Merge String Alternatively
You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.
Return the merged string.
Example 1:
Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r
Example 2:
Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s
Example 3:
Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d
## Footnote
* 1 <= word1.length, word2.length <= 100
* word1 and word2 consist of lowercase English letters.
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)
}
```
94
# @2486. Append Characters to String to Make Subsequence
You are given two strings s and t consisting of only lowercase English letters.
Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1:
Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.
Example 2:
Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").
Example 3:
Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.
## Footnote
* 1 <= s.length, t.length <= 10^5
* s and t consist only of lowercase English letters.
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
}
```
95
# @2352. Equal Row and Column Pairs
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]
Example 2:
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]
## Footnote
* n == grid.length == grid[i].length
* 1 <= n <= 200
* 1 <= grid[i][j] <= 10^5
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
}
```
96
# @409. Longest Palindrome
Given a string s which consists of lowercase or uppercase letters, return the length of the longest
palindrome
that can be built with those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome.
Example 1:
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2:
Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.
## Footnote
* 1 <= s.length <= 2000
* s consists of lowercase and/or uppercase English letters only.
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
}
```
97
# @345. Reverse Vowels of a String
Given a string s, reverse only all the vowels in the string and return it.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.
Example 1:
Input: s = "hello"
Output: "holle"
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
## Footnote
* 1 <= s.length <= 3 * 10^5
* s consist of printable ASCII characters.
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
}
}
```
98
# @437. Path Sum lll
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
## Footnote
* The number of nodes in the tree is in the range [0, 1000].
* -10^9 <= Node.val <= 10^9
* -1000 <= targetSum <= 1000
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);
}
```
99
# @1002. Find Common Characters
Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.
Example 1:
Input: words = ["bella","label","roller"]
Output: ["e","l","l"]
Example 2:
Input: words = ["cool","lock","cook"]
Output: ["c","o"]
## Footnote
* 1 <= words.length <= 100
* 1 <= words[i].length <= 100
* words[i] consists of lowercase English letters.
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
}
```
100
# @151. Reverse Words in a String
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
## Footnote
* 1 <= s.length <= 10^4
* s contains English letters (upper-case and lower-case), digits, and spaces ' '.
* There is at least one word in s
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
}
```
101
# @846. Hand of Straights
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.
## Footnote
* 1 <= hand.length <= 10^4
* 0 <= hand[i] <= 10^9
* 1 <= groupSize <= hand.length
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
}
```
102
# @1143. Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
## Footnote
* 1 <= text1.length, text2.length <= 1000
* text1 and text2 consist of only lowercase English characters.
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]
}
```
103
# @648. Replace word
In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.
Return the sentence after the replacement.
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Example 2:
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
* 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
104
# @523. Continuous Subarray Sum
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
its length is at least two, and
the sum of the elements of the subarray is a multiple of k.
Note that:
A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
## Footnote
* 1 <= nums.length <= 10^5
* 0 <= nums[i] <= 10^9
* 0 <= sum(nums[i]) <= 2^31 - 1
* 1 <= k <= 2^31 - 1
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
}
```
105
# @1071. Greatest Common Divisor of Strings
For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Example 1:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Example 2:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Example 3:
Input: str1 = "LEET", str2 = "CODE"
Output: ""
## Footnote
* 1 <= str1.length, str2.length <= 1000
* str1 and str2 consist of English uppercase letters.
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)
}
```
106
# @974. Subarray Sums Divisible by K
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Example 2:
Input: nums = [5], k = 9
Output: 0
## Footnote
* 1 <= nums.length <= 3 * 10^4
* -10^4 <= nums[i] <= 10^4
* 2 <= k <= 10^4
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
}
```
107
# @1051. Height Checker
A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.
You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).
Return the number of indices where heights[i] != expected[i].
Example 1:
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
heights: [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.
Example 2:
Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights: [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.
Example 3:
Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights: [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.
## Footnote
* 1 <= heights.length <= 100
* 1 <= heights[i] <= 100
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
}
```
108
# @1122. Relatvie Sort Arrray
Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.
Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.
Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
Example 2:
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
## Footnote
* 1 <= arr1.length, arr2.length <= 1000
* 0 <= arr1[i], arr2[i] <= 1000
* All the elements of arr2 are distinct.
* Each arr2[i] is in arr1.
* 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
}
```
109
# @75. Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]
## Footnote
* n == nums.length
* 1 <= n <= 300
* nums[i] is either 0, 1, or 2
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]
}
}
}
}
```
110
# @2037. Minimum Number of Moves to Seat Everyone
There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.
You may perform the following move any number of times:
Increase or decrease the position of the ith student by 1 (i.e., moving the ith student from position x to x + 1 or x - 1)
Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.
Note that there may be multiple seats or students in the same position at the beginning.
Example 1:
Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: The students are moved as follows:
- The first student is moved from from position 2 to position 1 using 1 move.
- The second student is moved from from position 7 to position 5 using 2 moves.
- The third student is moved from from position 4 to position 3 using 1 move.
In total, 1 + 2 + 1 = 4 moves were used.
Example 2:
Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:
- The first student is not moved.
- The second student is moved from from position 3 to position 4 using 1 move.
- The third student is moved from from position 2 to position 5 using 3 moves.
- The fourth student is moved from from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.
Example 3:
Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: Note that there are two seats at position 2 and two seats at position 6.
The students are moved as follows:
- The first student is moved from from position 1 to position 2 using 1 move.
- The second student is moved from from position 3 to position 6 using 3 moves.
- The third student is not moved.
- The fourth student is not moved.
In total, 1 + 3 + 0 + 0 = 4 moves were used.
## Footnote
* n == seats.length == students.length
* 1 <= n <= 100
* 1 <= seats[i], students[j] <= 100
* 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
}
```
111
# @1004. Max Consecutive Ones
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
## Footnote
* 1 <= nums.length <= 10^5
* nums[i] is either 0 or 1.
* 0 <= k <= nums.length
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
}
```
112
# @1207. Unique Number of occurrences
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
Example 1:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.
Example 2:
Input: arr = [1,2]
Output: false
Example 3:
Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
## Footnote
* 1 <= arr.length <= 1000
* -1000 <= arr[i] <= 1000
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
}
```
113
# @945. Minimum Increment to Make Array Unique
You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.
Return the minimum number of moves to make every value in nums unique.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].
Example 2:
Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
## Footnote
* 1 <= nums.length <= 10^5
* 0 <= nums[i] <= 10^5
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
}
```
114
# @216. Combination Sum lll
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
## Footnote
* 2 <= k <= 9
* 1 <= n <= 60
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
}
```
115
# [HARD] @501. IPO
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.
Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Example 2:
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
## Footnote
* 1 <= k <= 10^5
* 0 <= w <= 10^9
* n == profits.length
* n == capital.length
* 1 <= n <= 10^5
* 0 <= profits[i] <= 10^4
* 0 <= capital[i] <= 10^9
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
}
```
116
# [HARD] @330. Patching Array
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1:
Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:
Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].
Example 3:
Input: nums = [1,2,2], n = 5
Output: 0
## Footnote
* 1 <= nums.length <= 1000
* 1 <= nums[i] <= 10^4
* nums is sorted in ascending order.
* 1 <= n <= 2^31 - 1
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.
117
# @633. Sum of Square Numbers
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: c = 3
Output: false
## Footnote
* 0 <= c <= 2^31 - 1
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
}
```
118
# @344. Reverse String
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
## Footnote
* 1 <= s.length <= 10^5
* s[i] is a printable ascii character.
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--
}
}
```
119
# @1493. Longest Subarray of 1's After Deleting One Element
Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
## Footnote
* 1 <= nums.length <= 10^5
* nums[i] is either 0 or 1
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
}
}
```
120
# @826. Most Profit Assigning Work
You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:
difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).
Every worker can be assigned at most one job, but one job can be completed multiple times.
For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.
Return the maximum profit we can achieve after assigning the workers to the jobs.
Example 1:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
Example 2:
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
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}
```
121
# @1431. Kids With the Greatest Number of Candies
There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.
Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.
Note that multiple kids can have the greatest number of candies.
Example 1:
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
Example 2:
Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.
Example 3:
Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]
## Footnote
* n == candies.length
* 2 <= n <= 100
* 1 <= candies[i] <= 100
* 1 <= extraCandies <= 50
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
}
```
122
# @1482. Minimum Number of Days to Make m Bouquets
You are given an integer array bloomDay, an integer m and an integer k.
You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here is the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.
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
}
```
123
# @278. First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1
## Footnote
* 1 <= bad <= n <= 2^31 - 1
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
}
```
124
# @162. Find Peak Element
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
## Footnote
* 1 <= nums.length <= 1000
* -2^31 <= nums[i] <= 2^31 - 1
* nums[i] != nums[i + 1] for all valid i.
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
}
```
125
# @1552. Magnetic Force Between Two Balls
In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.
Rick stated that magnetic force between two different balls at positions x and y is |x - y|.
Given the integer array position and the integer m. Return the required force.
Example 1:
Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.
Example 2:
Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.
## Footnote
* n == position.length
* 2 <= n <= 10^5
* 1 <= position[i] <= 10^9
* All integers in position are distinct.
* 2 <= m <= position.length
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
}
```
126
# @1052. Grumpy Book Store Owner
There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.
When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Example 2:
Input: customers = [1], grumpy = [0], minutes = 1
Output: 1
## Footnote
* n == customers.length == grumpy.length
* 1 <= minutes <= n <= 2 * 10^4
* 0 <= customers[i] <= 1000
* grumpy[i] is either 0 or 1.
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
}
```
127
# @2462. Total Cost to Hire K Workers.
You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.
You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:
You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.
Return the total cost to hire exactly k workers.
Example 1:
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.
Example 2:
Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.
## Footnote
* 1 <= costs.length <= 10^5
* 1 <= costs[i] <= 10^5
* 1 <= k, candidates <= costs.length
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
}
```
128
# @239. Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
## Footnote
* 1 <= nums.length <= 10^5
* -10^ 4 <= nums[i] <= 10^4
* 1 <= k <= nums.length
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
}
```
129
# @1438. Longest Continuous Subarray with Absolute Diff Less Than or Equal
Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
Example 1:
Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.
Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3
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
}
```
130
# @1248. Count Number Of Nice Subarrays
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There are no odd numbers in the array.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
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
}
```
131
# [HARD] @995. Minimum Number of K Consecutive Bit Flips
You are given a binary array nums and an integer k.
A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].
Example 2:
Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].
Example 3:
Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation:
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]
## Footnote
* 1 <= nums.length <= 10^5
* 1 <= k <= nums.length
* 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
}
```
132
# @3191. Minimum Operations to Make Binary Array Elements Equal to One I
You are given a
binary array
nums.
You can do the following operation on the array any number of times (possibly zero):
Choose any 3 consecutive elements from the array and flip all of them.
Flipping an element means changing its value from 0 to 1, and from 1 to 0.
Return the minimum number of operations required to make all elements in nums equal to 1. If it is impossible, return -1.
Example 1:
Input: nums = [0,1,1,1,0,0]
Output: 3
Explanation:
We can do the following operations:
Choose the elements at indices 0, 1 and 2. The resulting array is nums = [1,0,0,1,0,0].
Choose the elements at indices 1, 2 and 3. The resulting array is nums = [1,1,1,0,0,0].
Choose the elements at indices 3, 4 and 5. The resulting array is nums = [1,1,1,1,1,1].
Example 2:
Input: nums = [0,1,1,1]
Output: -1
Explanation:
It is impossible to make all elements equal to 1.
## Footnote
* 3 <= nums.length <= 10^5
* 0 <= nums[i] <= 1
* 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
}
```
133
# @1038. Binary Search Tree to Greater Sum Tree
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:
Input: root = [0,null,1]
Output: [1,null,1]
## Footnote
* The number of nodes in the tree is in the range [1, 100].
* 0 <= Node.val <= 100
* All the values in the tree are unique.
* 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
}
```
134
# @1382. Balance a Binary Search Tree
Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.
A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
Example 1:
Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.
Example 2:
Input: root = [2,1,3]
Output: [2,1,3]
## Footnote
* The number of nodes in the tree is in the range [1, 10^4].
* 1 <= Node.val <= 10^5
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)
}
```
135
# @2285. Maximum Total Importance of Roads
You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.
You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.
You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.
Return the maximum total importance of all roads possible after assigning the values optimally.
Example 1:
Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.
Example 2:
Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20
Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.
## Footnote
* 2 <= n <= 5 * 10^4
* 1 <= roads.length <= 5 * 10^4
* roads[i].length == 2
* 0 <= ai, bi <= n - 1
* ai != bi
* There are no duplicate roads.
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)
}
```
136
# @1791. Find Center of Star Graph
There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.
You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.
Example 1:
Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
Example 2:
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
## Footnote
* 3 <= n <= 10^5
* edges.length == n - 1
* edges[i].length == 2
* 1 <= ui, vi <= n
* ui != vi
* The given edges represent a valid star graph.
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
}
```
137
# @2192. All Ancestors of a Node in a Directed Acyclic Graph
You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).
You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.
Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.
A node u is an ancestor of another node v if u can reach v via a set of edges.
Example 1:
Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.
Example 2:
Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.
## Footnote
* 1 <= n <= 1000
* 0 <= edges.length <= min(2000, n * (n - 1) / 2)
* edges[i].length == 2
* 0 <= fromi, toi <= n - 1
* fromi != toi
* There are no duplicate edges.
* The graph is directed and acyclic.
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
}
```
138
# @684. Redundant Connection
n this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
## Footnote
* n == edges.length
* 3 <= n <= 1000
* edges[i].length == 2
* 1 <= ai < bi <= edges.length
* ai != bi
* There are no repeated edges.
* The given graph is connected.
**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.
}
```
139
# [Hard] @1579. Remove Max Number of Edges to Keep Graph Fully Traverable
Alice and Bob have an undirected graph of n nodes and three types of edges:
Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can be traversed by both Alice and Bob.
Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.
Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.
Example 1:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.
Example 2:
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.
Example 3:
Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.
## Footnote
* 1 <= n <= 10^5
* 1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
* edges[i].length == 3
* 1 <= typei <= 3
* 1 <= ui < vi <= n
* All tuples (typei, ui, vi) are distinct.
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
}
```
140
# @1550. Three Consecutive Odds
Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.
Example 1:
Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.
Example 2:
Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.
## Footnote
* 1 <= arr.length <= 1000
* 1 <= arr[i] <= 1000
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
}
```
141
# @2058. Find Minimum and Maximum Number of Nodes Between Critical Points
A critical point in a linked list is defined as either a local maxima or a local minima.
A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.
A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.
Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.
Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].
Example 1:
Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].
Example 2:
Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.
Example 3:
Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.
## Footnote
* The number of nodes in the list is in the range [2, 10^5].
* 1 <= Node.val <= 10^5
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}
}
```
142
# @2582. Pass the pillow
There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.
For example, once the pillow reaches the nth person they pass it to the n - 1th person, then to the n - 2th person and so on.
Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.
Example 1:
Input: n = 4, time = 5
Output: 2
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2.
After five seconds, the 2nd person is holding the pillow.
Example 2:
Input: n = 3, time = 2
Output: 3
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3.
After two seconds, the 3rd person is holding the pillow.
## Footnote
* 2 <= n <= 1000
* 1 <= time <= 1000
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
}
```
143
# @1518. Water Bottles
There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.
The operation of drinking a full water bottle turns it into an empty bottle.
Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.
Example 1:
Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.
Example 2:
Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 15 + 3 + 1 = 19.
## Footnote
* 1 <= numBottles <= 100
* 2 <= numExchange <= 100
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
}
```
144
# @1823. Find the Winner of the Circular Game
There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.
The rules of the game are as follows:
Start at the 1st friend.
Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
The last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
Else, the last friend in the circle wins the game.
Given the number of friends, n, and an integer k, return the winner of the game.
Example 1:
Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.
Example 2:
Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.
* 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
}
```
145
# @2130. Maximum Twin Sum of a Linked List
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.
For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.
Given the head of a linked list with even length, return the maximum twin sum of the linked list.
Example 1:
Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.
Example 2:
Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.
Example 3:
Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.
## Footnote
* The number of nodes in the list is an even integer in the range [2, 10^5].
* 1 <= Node.val <= 10^5
* 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
146
# @1701. Average Waiting Time
There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrivali, timei]:
arrivali is the arrival time of the ith customer. The arrival times are sorted in non-decreasing order.
timei is the time needed to prepare the order of the ith customer.
When a customer arrives, he gives the chef his order, and the chef starts preparing it once he is idle. The customer waits till the chef finishes preparing his order. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.
Return the average waiting time of all customers. Solutions within 10-5 from the actual answer are considered accepted.
Example 1:
Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) The first customer arrives at time 1, the chef takes his order and starts preparing it immediately at time 1, and finishes at time 3, so the waiting time of the first customer is 3 - 1 = 2.
2) The second customer arrives at time 2, the chef takes his order and starts preparing it at time 3, and finishes at time 8, so the waiting time of the second customer is 8 - 2 = 6.
3) The third customer arrives at time 4, the chef takes his order and starts preparing it at time 8, and finishes at time 11, so the waiting time of the third customer is 11 - 4 = 7.
So the average waiting time = (2 + 6 + 7) / 3 = 5.
Example 2:
Input: customers = [[5,2],[5,4],[10,3],[20,1]]
Output: 3.25000
Explanation:
1) The first customer arrives at time 5, the chef takes his order and starts preparing it immediately at time 5, and finishes at time 7, so the waiting time of the first customer is 7 - 5 = 2.
2) The second customer arrives at time 5, the chef takes his order and starts preparing it at time 7, and finishes at time 11, so the waiting time of the second customer is 11 - 5 = 6.
3) The third customer arrives at time 10, the chef takes his order and starts preparing it at time 11, and finishes at time 14, so the waiting time of the third customer is 14 - 10 = 4.
4) The fourth customer arrives at time 20, the chef takes his order and starts preparing it immediately at time 20, and finishes at time 21, so the waiting time of the fourth customer is 21 - 20 = 1.
So the average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.
## Footnote
* 1 <= customers.length <= 10^5
* 1 <= arrivali, timei <= 10^4
* arrivali <= arrivali+1
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)
}
```
147
# @1598. Crawler Log Folder
The Leetcode file system keeps a log each time some user performs a change folder operation.
The operations are described below:
"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
"./" : Remain in the same folder.
"x/" : Move to the child folder named x (This folder is guaranteed to always exist).
You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.
The file system starts in the main folder, then the operations in logs are performed.
Return the minimum number of operations needed to go back to the main folder after the change folder operations.
Example 1:
Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.
Example 2:
Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3
Example 3:
Input: logs = ["d1/","../","../","../"]
Output: 0
## Footnote
* 1 <= logs.length <= 10^3
* 2 <= logs[i].length <= 10
* logs[i] contains lowercase English letters, digits, '.', and '/'.
* logs[i] follows the format described in the statement.
* Folder names consist of lowercase English letters and digits.
* 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.
148
# @71. Simplify Path
Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this path into its simplified canonical path.
In Unix-style file system context, a single period '.' signifies the current directory, a double period ".." denotes moving up one directory level, and multiple slashes such as "//" are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like "...") as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
It must start with a single slash '/'.
Directories within the path should be separated by only one slash '/'.
It should not end with a slash '/', unless it's the root directory.
It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
Example 1:
Input: path = "/home/"
Output: "/home"
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation:
Multiple consecutive slashes are replaced by a single one.
Example 3:
Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation:
A double period ".." refers to the directory up a level.
Example 4:
Input: path = "/../"
Output: "/"
Explanation:
Going one level up from the root directory is not possible.
Example 5:
Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"
Explanation:
"..." is a valid name for a directory in this problem.
## Footnote
* 1 <= path.length <= 3000
* path consists of English letters, digits, period '.', slash '/' or '_'.
* path is a valid absolute Unix path.
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, "/")
}
```
149
# @1190. Rerverse Substrings Betwen Each Pair of Parentheses
You are given a string s that consists of lower case English letters and brackets.
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example 1:
Input: s = "(abcd)"
Output: "dcba"
Example 2:
Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.
Example 3:
Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
## Footnote
* 1 <= s.length <= 2000
* s only contains lower case English characters and parentheses.
* It is guaranteed that all parentheses are balanced.
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--
}
}
```
150
# @2096. Step-By-Step Directions From a Binary Tree Node to Another
You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s to node t.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.
## Footnote
* The number of nodes in the tree is n.
* 2 <= n <= 10^5
* 1 <= Node.val <= n
* All the values in the tree are unique.
* 1 <= startValue, destValue <= n
* startValue != destValue
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)
}
```
151
# @2196. Create Binary Tree From Descriptions
You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,
If isLefti == 1, then childi is the left child of parenti.
If isLefti == 0, then childi is the right child of parenti.
Construct the binary tree described by descriptions and return its root.
The test cases will be generated such that the binary tree is valid.
Example 1:
Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.
Example 2:
Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.
## Footnote
* 1 <= descriptions.length <= 10^4
* descriptions[i].length == 3
* 1 <= parenti, childi <= 10^5
* 0 <= isLefti <= 1
* The binary tree described by descriptions is valid.
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
}
```
152
# @1717. Maximum Score From Removing Substrings
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
For example, when removing "ba" from "cabxbae" it becomes "cabxe".
Return the maximum points you can gain after applying the above operations on s.
Example 1:
Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.
Example 2:
Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20
## Footnote
* 1 <= s.length <= 10^5
* 1 <= x, y <= 10^4
* s consists of lowercase English letters.
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
}
```
153
# @1190. Reverse Substrings Between Each Pair of Parentheses
You are given a string s that consists of lower case English letters and brackets.
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example 1:
Input: s = "(abcd)"
Output: "dcba"
Example 2:
Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.
Example 3:
Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
## Footnote
* 1 <= s.length <= 2000
* s only contains lower case English characters and parentheses.
* It is guaranteed that all parentheses are balanced.
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--
}
}
```
154
# @2751. Robot Collisions
There are n 1-indexed robots, each having a position on a line, health, and movement direction.
You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.
All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.
If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.
Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e. final heath of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.
Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.
Note: The positions may be unsorted.
Example 1:
Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
Output: [2,17,9,15,10]
Explanation: No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].
Example 2:
Input: positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
Output: [14]
Explanation: There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].
Example 3:
Input: positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"
Output: []
Explanation: Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].
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] }
```
155
# @1530. Number of Good Leaf Nodes Pairs
You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.
Return the number of good leaf node pairs in the tree.
Example 1:
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
Example 2:
Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.
Example 3:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].
## Footnote
* The number of nodes in the tree is in the range [1, 210].
* 1 <= Node.val <= 100
* 1 <= distance <= 10
* 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
}
```
I’m Going To Google
flashcards
Decks in class (6)
# Cards
