Set 2 Flashcards
(17 cards)
Largest rectangle in histogram
Idea:
Sketch out the graph. We see that for certain height, the rectangle goes till the point the sequence is less that that certain height. We use monotonically increasing stack and put the (index, height)
Algorithm:
Declare empty stack and the max_area
enumerate through the heights
-start = i
-while stack and stack[-1] > heights[i]:
-index, height = stack.pop()
-reassign max area among itself or height * (index - i)
-start = index
-stack.append((start, heights[i]))
//clear remaining stack
for i, h in stack
-max_area = max(max_area, h * (len(heights) - i))
Walls and gates
Idea:
Multi-source bfs starting from gates
Algorithm:
Iterate through the grid and add the gates to the queue
Define addRoom function where row, col passed as params
If out of bounds or (row, col) in visited or wall at (row, col) return
Or else add to queue and visited
Declare dist as 0
while q
-for i in range q
-pop the r and c
-rooms[r][c] = dist
-call addRoom() in all 4 directions
-dist += 1
Surrounded regions
Idea:
We check the boundaries and if found “O”, we dfs and mark the surrounding “unsurrounded” regions by “T”
And then iterate through grid and change remaining “O” to “X”
And then again iterate through grid and replace back the “T” with “O”
Task scheduler
Idea:
Maintain a max heap with the task counts
When task executed, push to the queue along with the time it can be again executed
If the task in the queue becomes ready to execute, we push it back to heap
Algorithm:
count = Counter(tasks)
max_heap = [-cnt for cnt in count.values()]
heapq.heapify(max_heap)
time = 0
while max_heap or q:
-time += 1
-if max_heap:
-cnt = 1 + heappop
-if cnt:
-q.append([cnt, time + n])
-if q and q[0][1] == time:
-heappush(q.popleft()[0])
return time
Subarray sum equals k
Idea:
Think as if we are trying to find how many subarrays with specific sum, you can chop off from the current subarray
We keep count of the prefix sums of the current subarrays
If we find the difference from the k, we increment the result with that count
Algorithm:
curr_sum = 0 and prefix = {0: 1}
for every number in array
-curr_sum += number
-diff = curr_sum - k
-res += prefix.get(diff, 0)
-prefix[curr_sum] = 1 + prefix.get(curr_sum, 0)
return answer
Redundant connection
Idea:
Union find
In Union:
If the parent of both the nodes is same, we return False
Iterate through the edges and if union false false, return the edge
Min cost climbing stairs
Idea:
At any given step, the minimum cost is the minimum of prev two steps + current step.
We start in reverse and then min among of 0th and 1st index
Algorithm:
append 0 to cost array
for i from len-3 to 0
-cost[i] = cost[i] + min(cost[i+1], cost[i+2])
return min(cost[0], cost[1])
Reverse nodes in k-group
Idea:
Traverse the list to get groups of size k
Reverse that group and then re assign pointers
Keep storing the prev and next of group to reconnnect the groups
Algorithm:
Define getKth(curr, k)
while curr and k > 0
-curr = curr.next and dec k
end while
return curr
Declare dummy
group_prev = dummy
while true
-kth = getKth(group_prev, k)
-if not kth: break ….(not complete group)
-group_next = kth.next
// reverse the group
-prev, curr = kth.next, group_prev.next
-while curr!=group_next:
-temp = curr.next
-curr.next = prev
-prev = curr
-curr = temp
//reassign group_prev
-temp = group_prev.next
-group_prev.next = kth
-group_prev = temp
return dummy.next
Design Twitter
INIT:
self.count = 0 …(to keep track of time. We decrement it so we can use min_heap to fetch most recent ones)
tweet_map dict for (user_id, [count, tweet_id])
follow_map dict for (follower_id, set(followee_ids))
POST TWEET:
append [count,tweet_id] to tweet_map of the user
dec the count
FOLLOW:
add followee_id for follow_map in follower_id
UNFOLLOW:
if followee_id in follow_map for follower_id:
remove it from the map
POST TWEET:
Idea is to first fetch the most recent tweets of all the followees for the user
We get the index of the latest tweet, which will be n - 1
Heapify [count, tweet_id, followee_id, index - 1] … (So we can fetch the tweet before the latest for that followee)
Then min heapify it
Then pop the most recent, add to result and then add the tweet before that by that followee to the heap
Repeat this process till we have either min_heap or the 10 tweets in esult
Firstly add the user to their own follow_map
Network delay time
Idea:
Dijkstras algorithm
Use heap to store the closes neighbor and then pop it and check its neighbors
Algorithm:
create edges adjacency list dictionary in format
source -> [dest, cost]
declare empty visited set and heap[(0, k)]
And t = 0
while heap
-w1,n1 = pop()
-if w1 already visited, continue
-add w1 to visited
-t = max(t, w1)
for n2, w2 in edges[n1]:
-if n2 not visited, heappush([w1 + w2, n2])
-end for
-end while
return t if len(visited) == n or return -1
Cheapest flights with k stops
Idea:
Bellman ford algorithm for cheapest path from src to dest, relaxing all the edges k + 1 times
Algorithm:
Declare prices array with “+inf” of length n
prices[src] = 0
For range k times
-temp_prices = prices.copy()
-for s, d, p in flights
-if prices[s] is “inf”, continue
-if prices[s] + p < temp_prices[d], temp_prices[d] = prices[s] + p
-end for
-prices = temp_prices
end for
return -1 if prices[dst] is “inf” else return prices[dst]
Partition equal subset sum
Idea:
Firstly, we need to ensure that the sum of the array is even. If not, just return false
Set target to half of the sum
We maintain a set, which contains 0 first
We iterate through the array adn add the element to each of the set element
If at end target exists in the set, return True else False
Coin change 2
Idea:
Same as the coin change 1
We iterate through coins array
We maintain an array of how many coins are of that particular coin to reach certain amount
And for next coin, we use this array
Algorithm:
declare dp array of 0s of length amount + 1
dp[0] = 1
for every coin in reverse
-declare next_dp in same way as dp
-for a from range 1 to amount + 1
-next_dp[a] = dp[a]
-if a-coins[i] >= 0, next_dp[a] += next_dp[a - coins[i]]
-end for
-dp = next_dp
end for
return dp[amount]
Combination sum 2
Idea:
We first sort the arary
Same as combination sum 1
But, in a skip decision
We skip the entire part of the array which has the same number
Algorithm:
declare emtpy answer array and sort the candidates
define dfs(i, curr, total) as follows
if total = target, answer.append(curr.copy()) and return
if total > target or i == length, return
//include i candidate
curr.append(candidates[i])
dfs(i + 1, curr, total + candidates[i])
curr.pop()
//skip candidates[i] and the same values
while (i+1)<length and candidates[i] == candidates[i+1], i += 1
dfs(i + 1, curr, total)
end func
dfs(0, [], 0)
return answer
Subsets
Idea:
Include number and call dfs on next one
Pop the number and call the dfs on next one
Algorithm:
define empty answer and subset array
define dfs(i) as follows
if i >= length: answer.append(subset.copy()) and return
//include current number
subset.append(nums[i])
dfs(i + 1)
subset.pop()
//skip current number
dfs(i + 1)
end func
dfs(0)
return answer
Subsets 2
Idea:
Same as subsets
But we sort the input first
And in skip decision, we skip to next different number
Algorithm:
define empty answer and subset array
define dfs(i) as follows
if i >= length: answer.append(subset.copy()) and return
//include current number
subset.append(nums[i])
dfs(i + 1)
subset.pop()
//skip current number
while (i + 1) < length and nums[i] == nums[i + 1]: i += 1
dfs(i + 1)
end func
dfs(0)
return answer
Palindrome partitioning
Idea:
From the specific position, we check which what is the substring and then we add that to the temp solution and recurse from the point after that
Algorithm:
Define empty answer and partition array
Define isPalindrome(l, r) function
Define dfs(i) function as follows
if i >= length, answer.append(partition.copy()) and return
for j in range(i, len(s)):
-if isPalindrome(i,j):
-partition.append(s[i:j+1])
-dfs(j+1)
-partition.pop()
-end if
end for
end func
dfs(0)
return answer
