LeetCode Freedom Flashcards
Getting into Google
@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.
@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.
@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
}
@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]]
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
}
Use a decision tree for the thinking process.
@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”]
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
}
Use a decision tree for the thinking process.
@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]]
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
}
@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
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
}
@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
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
}
@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
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
}
@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<Node> neighbors;
}</Node>
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).
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) } ~~~
@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.
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
}
@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
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]
}
It’s a Fibonacci Series.
@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.
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])
}
@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.
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
}
@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
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. 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.
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]
}
@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
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
}
@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.
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
}
@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”
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
}
A palindrome has two forms: One with a single core ‘aba’ and another with a two-element core ‘abba’
@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”.
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
}
A palindrome has two forms: One with a single core ‘aba’ and another with a two-element core ‘abba’
@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.
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
}
~~~
@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”).
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)
}
@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”.
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)
}
