Heaps / Priority Queue Flashcards
- K Closest Points to Origin
Solved
Medium
Topics
Companies Facebook
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]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
1 <= k <= points.length <= 104
-104 <= xi, yi <= 104
https://leetcode.com/problems/k-closest-points-to-origin/description/
class Solution(object):
def kClosest(self, points, k):
"""
:type points: List[List[int]]
:type k: int
:rtype: List[List[int]]
"""
def euc(x,y):
return math.sqrt(x**2 + y**2)
heap = []
for idx, point in enumerate(points):
x,y = point[0], point[1]
dis = euc(x,y)
heapq.heappush(heap, (-dis, idx))
if len(heap) > k:
heapq.heappop(heap)
return [points[res[1]] for res in heap]
O(nLog(k)), Space: K
- Task Scheduler
Solved
Medium
Topics
Companies
Hint
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.
Example 3:
Input: tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.
Constraints:
1 <= tasks.length <= 104
tasks[i] is an uppercase English letter.
0 <= n <= 100
https://leetcode.com/problems/task-scheduler/description/
O(nLog(k)) solution where k is number of unique tasks. n is total time required, k will never go above len(tasks)
from collections import Counter
class Solution(object):
def leastInterval(self, tasks, n):
"""
:type tasks: List[str]
:type n: int
:rtype: int
"""
counts = Counter(tasks)
heap = [-val for val in counts.values()] # The execution queue, the highest count tasks execute first.
heapq.heapify(heap)
time = 0
q = deque() # The waiting queue
while heap or q:
# is there any task pending for execution at this time?
if q and q[0][0] == time:
# Add the task to execution queue
heapq.heappush(heap, q[0][1])
q.popleft()
if heap:
# There are tasks waiting to be executed
# pick one, execute it and append the time for the next time it can be executed if needed.
remaining = 1 + heapq.heappop(heap)
if remaining:
q.append((time+(n+1), remaining))
time+=1
return time
Simpler Solution O(n) but does use a lot of edge cases, I do not like this solution as in interview might not be possible to cleanly execute this. Heap solution is better for interview.
from collections import Counter
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
counts = Counter(tasks)
sortedCounts = sorted(list(counts.keys()), key=counts.get)
maxFreq = counts[sortedCounts[-1]]
# Imagine 3 A's and n = 2
# idle slots = A Idle Idle A Idle Idle A = 4 i.e count - 1 * n
idleSlots = (maxFreq - 1) * n
for task in sortedCounts[:-1]:
# min because there can be entries with same counts as max freq
# thus just like the above their last entry will need no idle slots as its the last one
# which will be after the maxFreq task.
# eg. A A A B B B CC , n = 3 A B C I A B C I A B
# notice how last A and B need n-1 idle slots
idleSlots -= min(maxFreq-1, counts[task])
# if no idle slots remain then just return the len of tasks
# else add the idle slots to len of tasks.
# if n is low enough, there will be no idle slots, rather
# we will be short of idle slots, so just take max of 0, idleslots
return len(tasks) + max(0, idleSlots)
heap solution is preferred in interview, but the O(n) might be asked if
- Find Median from Data Stream
Solved
Hard
Topics
Companies:
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
Constraints:
-105 <= num <= 105
There will be at least one element in the data structure before calling findMedian.
At most 5 * 104 calls will be made to addNum and findMedian.
Follow up:
If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
https://leetcode.com/problems/find-median-from-data-stream/
Always push in max heap (smaller half), then pop the largest of smal half and push it in larger half (min heap). Then balance them if needed. Since we always push the value in min_heap, (large half) we check if that’s larger.
class MedianFinder:
def \_\_init\_\_(self):
self.min_heap = []
self.max_heap = []
def push_max_heap(self, val):
heapq.heappush(self.max_heap, -val)
def pop_max_heap(self):
return -(heapq.heappop(self.max_heap))
def peek_max_heap(self):
return -(self.max_heap[0])
def addNum(self, num: int) -> None:
self.push_max_heap(num)
heapq.heappush(self.min_heap, self.pop_max_heap())
if len(self.min_heap) > len(self.max_heap) + 1:
val = heapq.heappop(self.min_heap)
self.push_max_heap(val)
def findMedian(self) -> float:
if len(self.max_heap) == len(self.min_heap):
return (self.peek_max_heap() + self.min_heap[0])/2.0
elif len(self.max_heap) > len(self.min_heap):
return self.peek_max_heap()
else:
return self.min_heap[0]
class MinHeap:
def \_\_init\_\_(self):
self.base = []
def insert(self, val):
heapq.heappush(self.base, val)
def pop(self):
if self.base:
return heapq.heappop(self.base)
else:
return None
def peek(self):
if self.base:
return self.base[0]
else:
None
def size(self):
return len(self.base)
def empty(self):
return True if len(self.base) == 0 else False
class MaxHeap:
def \_\_init\_\_(self):
self.base = []
def insert(self, val):
heapq.heappush(self.base, -1 * val)
def pop(self):
if self.base:
return -1 * heapq.heappop(self.base)
else:
return None
def peek(self):
if self.base:
return -1 * self.base[0]
else:
None
def size(self):
return len(self.base)
def empty(self):
return True if len(self.base) == 0 else False
class MedianFinder(object):
def \_\_init\_\_(self):
self.small = MaxHeap() # for smaller half
self.large = MinHeap() # for larger half
def addNum(self, num):
"""
:type num: int
:rtype: None
"""
self.small.insert(num)
self.large.insert(self.small.pop())
if self.large.size() > self.small.size() + 1:
self.small.insert(self.large.pop())
def findMedian(self):
"""
:rtype: float
"""
if self.small.size() > self.large.size():
return self.small.peek()
elif self.large.size() > self.small.size():
return self.large.peek()
elif self.large.empty():
return 0
else:
return (self.large.peek() + self.small.peek()) / 2.0
overused question, don’t expect in interview, but good to know how to use 2 heaps
- Reorganize String
Solved
Medium
Topics
Companies
Hint
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.
Example 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.
https://leetcode.com/problems/reorganize-string/description/
Same as the Leetcode 621
from collections import deque, defaultdict
class Solution(object):
def reorganizeString(self, s):
“””
:type s: str
:rtype: str
“””
heap = []
q = deque()
charCount = defaultdict(int)
for char in s:
charCount[char] -= 1
for key, value in charCount.items():
heapq.heappush(heap, (value, key))
pos = 0
ret = “”
while heap or q:
pos += 1
if heap:
freq, key = heapq.heappop(heap)
freq += 1
if freq <= 0:
q.append((key, pos + 1, freq))
if q and q[0][1] == pos:
key, pos, freq = q.popleft()
if ret and ret[-1] == key:
return “”
ret += key
heapq.heappush(heap, (freq, key))
return ret
O(n) solution, place the max freq char first, and then start placing the other ones
from collections import Counter
class Solution:
def reorganizeString(self, s: str) -> str:
output = [””] * len(s)
counts = Counter(s)
maxChar = ‘’
maxCharFreq = 0
maxChar, maxCharFreq = max(counts.items(), key=lambda x: x[1])
if maxCharFreq > (len(s) + 1) // 2:
return “”
idx = 0
while counts[maxChar] > 0:
output[idx] = maxChar
idx += 2
counts[maxChar] -= 1
for char, freq in counts.items():
while freq > 0:
if idx >= len(s):
idx = 1
output[idx] = char
idx += 2
freq -= 1
return ““.join(output)
- Top K Frequent Elements
https://leetcode.com/problems/top-k-frequent-elements/description/347. Top K Frequent Elements
Solved
Medium
Topics
Companies
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Facebook
58
Amazon
20
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == len(nums):
return nums
counts = Counter(nums)
return heapq.nlargest(k, counts.keys(), counts.get)
using quick select with count frequencies as key.
from collections import Counter
class Solution(object):
def topKFrequent(self, nums, k):
“””
:type nums: List[int]
:type k: int
:rtype: List[int]
“””
counts = Counter(nums)
unique = counts.keys()
def partition(l, r):
if l == r:
return l
pivot = unique[r]
store_idx = l
for i in range(l, r):
if counts[unique[i]] < counts[pivot]:
unique[i], unique[store_idx] = unique[store_idx], unique[i]
store_idx += 1
unique[r], unique[store_idx] = unique[store_idx], unique[r]
return store_idx
def quick_select(k):
k = len(unique) - k
l = 0
r = len(unique) - 1
piv_idx = partition(l, r)
while l < r:
if piv_idx == k:
return
elif piv_idx < k:
l = piv_idx + 1
piv_idx = partition(l, r)
else:
r = piv_idx - 1
piv_idx = partition(l, r)
quick_select(k)
n = len(unique)
return unique[n-k:]
- Design A Leaderboard
Solved
Medium
Topics
Companies
Hint
Design a Leaderboard class, which has 3 functions:
addScore(playerId, score): Update the leaderboard by adding score to the given player’s score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.
Initially, the leaderboard is empty.
Example 1:
Input:
[“Leaderboard”,”addScore”,”addScore”,”addScore”,”addScore”,”addScore”,”top”,”reset”,”reset”,”addScore”,”top”]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output:
[null,null,null,null,null,null,73,null,null,null,141]
Explanation:
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73); // leaderboard = [[1,73]];
leaderboard.addScore(2,56); // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39); // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51); // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4); // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1); // returns 73;
leaderboard.reset(1); // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2); // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51); // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3); // returns 141 = 51 + 51 + 39;
Constraints:
1 <= playerId, K <= 10000
It’s guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
There will be at most 1000 function calls.
https://leetcode.com/problems/design-a-leaderboard/
from collections import defaultdict
class Leaderboard(object):
def \_\_init\_\_(self):
self.score = defaultdict(int)
def addScore(self, playerId, score):
"""
:type playerId: int
:type score: int
:rtype: None
"""
self.score[playerId] += score
def top(self, K):
"""
:type K: int
:rtype: int
"""
heap = []
for v in self.score.values():
heapq.heappush(heap, v)
if len(heap) > K:
heapq.heappop(heap)
return sum(heap)
def reset(self, playerId):
"""
:type playerId: int
:rtype: None
"""
del self.score[playerId]
- Last Stone Weight
Solved
Easy
Topics
Companies
Hint
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.
Example 2:
Input: stones = [1]
Output: 1
Constraints:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
https://leetcode.com/problems/last-stone-weight/description/
class Solution(object):
def lastStoneWeight(self, stones):
“””
:type stones: List[int]
:rtype: int
“””
s = [-s for s in stones]
heapq.heapify(s)
res = 0
while len(s) > 1:
heapq.heappush(s, (heapq.heappop(s) - heapq.heappop(s)))
return -1 * s[-1]
- K Closest Points to Origin
Solved
Medium
Topics
Companies
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]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
1 <= k <= points.length <= 104
-104 <= xi, yi <= 104
https://leetcode.com/problems/k-closest-points-to-origin/
This is O(nLogK) solution)
from math import sqrt
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points = [(-sqrt(x[0]2 + x[1]2), x) for x in points]
heap = []
for negdist, point in points:
if heap:
if len(heap) == k and heap[0][0] < negdist:
heapq.heappop(heap)
heapq.heappush(heap, (negdist, point))
elif len(heap) < k:
heapq.heappush(heap, (negdist, point))
else:
heapq.heappush(heap, (negdist, point))
return [p[1] for p in heap]
The diff is that we keep heap size bounded. so after first K elements, its just logK for insert, remove
anything else will be O(nLog(n))
- Kth Largest Element in an Array
Solved
Medium
Topics
Companies: Facebook
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
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
https://leetcode.com/problems/kth-largest-element-in-an-array/description
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
h = []
for elem in nums:
heapq.heappush(h, elem)
if len(h) > k:
heapq.heappop(h)
return h[0]
- Merge k Sorted Lists
Solved
Hard
Topics
Companies
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length 0 <= k <= 104 0 <= lists[i].length <= 500 -104 <= lists[i][j] <= 104 lists[i] is sorted in ascending order. The sum of lists[i].length will not exceed 104.
https://leetcode.com/problems/merge-k-sorted-lists/description/
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
sentinel = ListNode()
cur = sentinel
heap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i))
while heap:
_, idx = heapq.heappop(heap)
cur.next = lists[idx]
lists[idx] = lists[idx].next
cur = cur.next
if lists[idx]:
heapq.heappush(heap, (lists[idx].val, idx))
return sentinel.next- Kth Smallest Element in a Sorted Matrix
Medium (hard)
Companies
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
Example 1:
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Example 2:
Input: matrix = [[-5]], k = 1
Output: -5
Constraints:
n == matrix.length == matrix[i].length 1 <= n <= 300 -109 <= matrix[i][j] <= 109 All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order. 1 <= k <= n2
Follow up:
Could you solve the problem with a constant memory (i.e., O(1) memory complexity)? Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.
Use 20-25 mins. This is hard.
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
Heap Solution with k space, similar to merge k-sorted linked list.
~~~
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
rows = min(len(matrix), k)
cols = len(matrix[0])
mat = matrix[:rows]
heap = []
ret = 0
for i in range(rows):
heapq.heappush(heap, (mat[i][0], (i,0)))
while k > 0:
val, (r,c) = heapq.heappop(heap)
ret = val
if c < cols-1:
heapq.heappush(heap, (mat[r][c+1], (r, c+1)))
k -= 1
return ret
~~~
Binary Search O(1) space solution. This is not the most straight forward, not sure how to develop intuition to show the path of thinking in interview.
import bisect
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
rows = len(matrix)
cols = len(matrix[0])
l = matrix[0][0]
r = matrix[rows-1][cols-1]
def rc(idx):
return idx//cols, idx%cols
# Why does this work?
# We calculate how many elements come before mid using the binary search
# If it is less than k then our target number is larger than mid because if it
# were equal to mid, then using bisect_right we would K smaller (which falls under other case)
# If it is equal or greater than k, then mid is equal to or greater than target number.
# we keep on doing this, we will end up with the actual number because of bisect_right there will never be k-1 elements less than mid if mid == target.
# we can't break on smaller_than_mid == k-1 because this will result in mid being a number smaller than our target.
def ele_less_than(e):
elements = 0
for i in range(rows):
before = bisect.bisect_right(matrix[i], e)
elements += before
return elements
while l < r:
mid = l + (r-l)//2
smaller_than_mid = ele_less_than(mid)
if smaller_than_mid < k:
l = mid + 1
else:
r = mid
return r
