LeetCode Freedom Flashcards
Getting into Google
@49. Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
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: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
Sort the string and use it as key. Value are the keys that are anagrams. (‘ant’: [‘tan’, ‘ant’, ‘atn’])
@217. Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Create a set. Check if number already in set.
@347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 <= nums.length <= 105
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
Create a bucket that stores number by count.
Bucket will look like this
Count 1 2 3 4 5
Num 2 1 8 0 9
Top 2 frequent are the two right most bucket that has number in it.
@392. Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
Output: false
0 <= s.length <= 100
0 <= t.length <= 10^4
s and t consist only of lowercase English letters.
Compare all the way using a pointer for s and a pointer for t. If is subsequence, the pointer for s should exceed the end of s.
func isSubsequence(s string, t string) bool {
var i int
for j := 0; j < len(t) && i < len(s); j++ {
if s[i] == t[j] {
i++
}
}
return i == len(s)
}
@1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.
Create a hashmap using substraction(target - num) as key and index as value.
@Two Sum - Input array is sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
Add head and tail. If result greater than target, tail is too big, move tail; else, move head.
func twoSum(nums []int, target int) []int {
// Array sorted. Compare would be easier.
i, j := 0, len(nums) - 1
for nums[i] + nums[j] != target {
if nums[i] + nums[j] < target {
i++
} else if nums[i] + nums[j] > target {
j--
}
}
return []int{i + 1, j + 1}
}
@128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Create a set that stores all number. Check the left neighbor to know if a number is the start of a sequence. Check the right neighbor until the neighbor is not in the set. Visualizing the problem would be easier.
__1,2,3,4_____100_____200_>
@Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or ‘.’.
Create 3 hashsets (rows, columns and squares) that stores existing number. Squares index calculation is tricky.
@238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Construct left and right product array using 1D dp. Calculate product array with the two array.
nums = [ a, b, c, d]
left = [ 1, a, ab, abc]
right = [bcd, cd, d, 1]
—————————–
Desire = [bcd, acd, abd, abc]
@121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Think of it logically. There’s no need to keep the previous low when you encounter a lower one, so update the currLow whenever there’s a lower number. Since we don’t know where the max profit happens, we keep a maxProfit and update it at every possible turn, which is a Greedy algorithm.
[3, 6, 7, 2, 8, 1, 3, 5]
|3–6|
|3—–7|
|3————-8|(Don’t need to track, we already have a smaller number 2)
|3——————-3|(Don’t need to track, we already have a smaller number 1)
|3————————5|(Don’t need to track, we already have a smaller number 1)
|2–8|
|2——–3|(Don’t need to track, we already have a smaller number 1)
|2———–5|(Don’t need to track, we already have a smaller number 1)
|1–3|
|1—-5|
func maxProfit(prices []int) int {
var profit int
currLow := prices[0]
for i := 0; i < len(prices); i++ {
if prices[i] >= currLow {
profit = max(prices[i] - currLow, profit)
} else {
currLow = prices[i]
}
}
return profit
}
Greedy. Keep track of every possible minimum buy-in price and maximum profit ==> Too vague.
@125. Valid Palindrome.
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters.
Two Pointers. Clean string. Continue when a char isn’t alphanumeric.
@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.
- 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
}
@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
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.
@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
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
}
@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.
- 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.
@3. Longest Substring Without Repeating Characters.
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Sliding window. When confront a duplcate, remove the head until the new element is not in set.
@76. [Hard] Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.
Use hashmap for counts. Keep track of ‘needs’ and ‘haves’ instead of comparing the entire hashmap. Loop the following until the end: Expand the window until it’s valid; shrink the window until it’s not valid. Keep track of minimum length and only update the window location when minimum length occurs.
@20. Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()[]{}”
Output: true
Example 2:
Input: s = “(]”
Output: false
1 <= s.length <= 10^4
s consists of parentheses only ‘()[]{}’
Use a stack to keep track of occurences. Pop the stack correspondingly to the type of the parenthesis. Length of stack should eventually be zero.
func isValid(s string) bool {
parenMap := map[rune]rune{
')': '(',
']': '[',
'}': '{',
}
stack := make([]rune, 0)
for i := range s {
switch rune(s[i]) {
case '(', '[', '{':
stack = append(stack, rune(s[i]))
case ')', ']', '}':
if len(stack) == 0 {
// Error
return false
} else {
if stack[len(stack)-1] != parenMap[rune(s[i])] {
// Error
return false
} else {
// Pop
stack = stack[:len(stack)-1]
}
}
}
}
return len(stack) == 0
}
@136. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Bitwise operation. Use XOR.
Set initial as 0. Compare all the way in one loop using XOR.
0000 ^ 0010 = 0010
0010 ^ 0010 = 0000 ( Cancels out each other if there’s a duplicate)
0000 ^ 0001 = 0001
return 0001
func singleNumber(nums []int) int {
var single int
for i := range nums {
single ^= nums[i]
}
return single
}
@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.
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.
@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.
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;
@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].
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.
@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
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.
@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]
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.
@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
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
}
@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
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).
@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.
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
}
@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
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.
@153 Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times
Binary Search.
- If mid is greater than tail, minimum is at the right side of the array. Move head to mid + 1 (since the mid is already greater we don’t need to consider it anymore).
- If mid is smaller than tail, from mid to tail is an increasing array, where mid is the smallest one for the right side.
The minimum might be in the left side, mid inclusive. Thus move tail to mid.
Value of the head will be the lowest at the end.
func findMin(nums []int) int {
h, t := 0, len(nums) - 1
var mid int
for h < t {
mid = (h + t) / 2
if nums[mid] > nums[t] {
h = mid + 1
} else {
t = mid
}
}
return nums[h]
}
@981 Time Based Key Value Store
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.
Implement the TimeMap class:
TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.
Example 1:
Input:
[“TimeMap”, “set”, “get”, “get”, “set”,”get”, “get”, “get”]
[[], [“foo”, “bar”, 2], [“foo”, 2], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 1],[“foo”, 4], [“foo”, 5]]
Output:
[null, null, “bar”, “bar”, null, null, “bar2”, “bar2”]
Create a map that stores an array as value. Binary search the array base on the timestamp. If timestamp is smaller than the mid value, tail = mid - 1 (since the mid is now not included). If timestamp is greater than the mid value, head = mid (since head might be the result.) Return the tail (last value that is available, which is the max).
Note that if a value exist but the desired timestamp is smaller than the earliest timestamp, return null.
@206 Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
ex:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
Store the next node first. Update the direction. After updating the direction, jump to the stored next node. When temp reached nil (the last stored next node), break out of the loop. The last updated previous node is the head of the reversed linked list.
[A, B, C, D]
prev temp next
nil <-change– A –jump-> B
A <-change– B –jump-> C
B <-change– C –jump-> D
C <-change– D –jump-> nil
D <-change– nil (break)
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
var prev, next *ListNode
temp := head
for temp != nil {
// After using the stored next node, store the old next node for later jumps.
next = temp.Next
// Assign new next to the previos node.
temp.Next = prev
// After using previous node, update previous to current.
prev = temp
// Jump to the stored next.
temp = next
}
return prev
}
Rememeber to deal with empty inputs (nil head).
@21 Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Create a placeholder for a new list. Compare through two lists by looping.
Exhaust the list that isn’t empty by directly assigning.
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
merged := new(ListNode)
temp := merged
for list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
temp.Next = list1
list1 = list1.Next
} else {
temp.Next = list2
list2 = list2.Next
}
temp = temp.Next
}
if list1 != nil {
temp.Next = list1
}
if list2 != nil {
temp.Next = list2
}
return merged.Next
}
Take special care on initializing the result node.
@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.
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, 要進位)
@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.
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!
@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
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
}
@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.
- 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
}
@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.
- (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
@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]
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)
@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
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
}
@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
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.
@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
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
@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
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
@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
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
@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.
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)
}
@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
- 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
}
}
The Lowest Common Ancestor happens when p and q are on separate sides, or either p or q equals to the root.
@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]]
- 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
}
Track level size to know when to stop in the queue.
@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]
- 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
}
@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
}
@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.
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)
}
InOrder Traversal: Left -> Root -> Right
@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.
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)
}
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
@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.
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
}
Break the problem down and find the base problem.
@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.
- 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:]),
}
}
Inorder is left -> root -> right. Preorder is root -> left -> right
@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);
*/
@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]]
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
}
@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.
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
}
@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
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
}
@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
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
}
}
}
}
@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.
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
}
}
}
@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.
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)
}
Greedy. 算出最少需要多少格剩下就是隨便塞。
@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]].
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)
}
}
@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]]
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
}
