Heap Advanced¶
Table of Contents¶
- 23. Merge k Sorted Lists (Hard)
- 355. Design Twitter (Medium)
- 502. IPO (Hard)
- 1705. Maximum Number of Eaten Apples (Medium)
- 778. Swim in Rising Water (Hard)
- 1631. Path With Minimum Effort (Medium)
- 1354. Construct Target Array With Multiple Sums (Hard)
- 1353. Maximum Number of Events That Can Be Attended (Medium)
- 1235. Maximum Profit in Job Scheduling (Hard)
- 632. Smallest Range Covering Elements from K Lists (Hard)
- 2542. Maximum Subsequence Score (Medium)
- 1383. Maximum Performance of a Team (Hard)
- 2503. Maximum Number of Points From Grid Queries (Hard)
- 2163. Minimum Difference in Sums After Removal of Elements (Hard)
- 857. Minimum Cost to Hire K Workers (Hard)
- 1606. Find Servers That Handled Most Number of Requests (Hard)
- 1851. Minimum Interval to Include Each Query (Hard)
- 218. The Skyline Problem (Hard)
- 407. Trapping Rain Water II (Hard)
- 2940. Find Building Where Alice and Bob Can Meet (Hard)
- 3399. Smallest Substring With Identical Characters II (Hard)
- 2589. Minimum Time to Complete All Tasks (Hard)
- 3266. Final Array State After K Multiplication Operations II (Hard)
- 1675. Minimize Deviation in Array (Hard)
- 2617. Minimum Number of Visited Cells in a Grid (Hard)
- 2532. Time to Cross a Bridge (Hard)
- 1199. Minimum Time to Build Blocks (Hard) 👑
23. Merge k Sorted Lists¶
"""
- Prerequisite: 21. Merge Two Sorted Lists
- Video explanation: [23. Merge K Sorted Lists - NeetCode](https://youtu.be/q5a5OiGbT6Q?si=SQ2dCvsYQ3LQctPh)
"""
import copy
import heapq
from typing import List, Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def merge_k_lists_divide_conquer(
lists: List[Optional[ListNode]],
) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
def mergeTwo(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged.append(mergeTwo(l1, l2))
lists = merged
return lists[0]
def merge_k_lists_heap(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
min_heap = [] # (val, idx, node)
for idx, head in enumerate(lists):
if head:
heapq.heappush(min_heap, (head.val, idx, head))
while min_heap:
_, idx, node = heapq.heappop(min_heap)
cur.next = node
cur = cur.next
node = node.next
if node:
heapq.heappush(min_heap, (node.val, idx, node))
return dummy.next
def test_merge_k_lists() -> None:
n1 = list_from_array([1, 4])
n2 = list_from_array([1, 3])
n3 = list_from_array([2, 6])
lists = [n1, n2, n3]
lists1 = copy.deepcopy(lists)
lists2 = copy.deepcopy(lists)
assert (list_to_array(merge_k_lists_divide_conquer(lists1))) == [
1,
1,
2,
3,
4,
6,
]
assert (list_to_array(merge_k_lists_heap(lists2))) == [1, 1, 2, 3, 4, 6]
355. Design Twitter¶
"""
- Similar question: [23. Merge K Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/) (Hard)
"""
import heapq
from collections import defaultdict
from typing import List
# Design
class Twitter:
def __init__(self):
self.tweets = defaultdict(list)
self.followees = defaultdict(set)
self.time = 0
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweets[userId].append((self.time, tweetId))
self.time += 1
def getNewsFeed(self, userId: int) -> List[int]:
news_feed = []
news_feed.extend(self.tweets[userId])
for followee in self.followees[userId]:
news_feed.extend(self.tweets[followee])
return [tweet for _, tweet in heapq.nlargest(10, news_feed)]
def follow(self, followerId: int, followeeId: int) -> None:
if followerId != followeeId:
self.followees[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followerId != followeeId:
self.followees[followerId].discard(followeeId)
twitter = Twitter()
print(twitter.postTweet(1, 5)) # None
print(twitter.getNewsFeed(1)) # [5]
print(twitter.follow(1, 2)) # None
print(twitter.postTweet(2, 6)) # None
print(twitter.getNewsFeed(1)) # [6, 5]
print(twitter.unfollow(1, 2)) # None
print(twitter.getNewsFeed(1)) # [5]
502. IPO¶
import heapq
from typing import List
# Heap - Two Heaps
def findMaximizedCapital(k: int, w: int, profits: List[int], capital: List[int]) -> int:
"""
Time Complexity: O(k log N)
Space Complexity: O(N)
"""
if not profits or not capital:
return w
if w >= max(capital) and k >= len(capital):
return sum(profits) + w
max_profit = []
min_capital = [(c, p) for c, p in zip(capital, profits)]
heapq.heapify(min_capital)
for _ in range(k):
while min_capital and min_capital[0][0] <= w:
_, pro = heapq.heappop(min_capital)
heapq.heappush(max_profit, -pro)
if max_profit:
w += -heapq.heappop(max_profit)
return w
if __name__ == "__main__":
k = 2
w = 0
profits = [1, 2, 3]
capital = [0, 1, 1]
assert findMaximizedCapital(k, w, profits, capital) == 4
1705. Maximum Number of Eaten Apples¶
778. Swim in Rising Water¶
-
Tags: Array, Binary Search, Depth First Search, Breadth First Search, Union Find, Heap Priority Queue, Matrix
"""
- Return the minimum time when you can reach the target.
"""
import heapq
from typing import List
# Dijkstra's
def swimInWater(grid: List[List[int]]) -> int:
n = len(grid)
visited = set()
minHeap = [(grid[0][0], 0, 0)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited.add((0, 0))
while minHeap:
time, r, c = heapq.heappop(minHeap)
if r == n - 1 and c == n - 1:
return time
for dr, dc in directions:
nr, nc = r + dr, c + dc
if nr in range(n) and nc in range(n) and (nr, nc) not in visited:
visited.add((nr, nc))
heapq.heappush(minHeap, (max(time, grid[nr][nc]), nr, nc))
grid = [
[0, 1, 2, 3, 4],
[24, 23, 22, 21, 5],
[12, 13, 14, 15, 16],
[11, 17, 18, 19, 20],
[10, 9, 8, 7, 6],
]
print(swimInWater(grid)) # 16
1631. Path With Minimum Effort¶
-
Tags: Array, Binary Search, Depth First Search, Breadth First Search, Union Find, Heap Priority Queue, Matrix
"""
- Return the minimum effort required to travel from the top-left to the bottom-right corner.
"""
import heapq
from typing import List
# Prim
def minimumEffortPath(heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[False] * n for _ in range(m)]
heap = [(0, 0, 0)] # (effort, row, col)
while heap:
effort, r, c = heapq.heappop(heap)
if visited[r][c]:
continue
if r == m - 1 and c == n - 1:
return effort
visited[r][c] = True
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
updated = max(effort, abs(heights[r][c] - heights[nr][nc]))
heapq.heappush(heap, (updated, nr, nc))
return -1
heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
print(minimumEffortPath(heights)) # 2
1354. Construct Target Array With Multiple Sums¶
1353. Maximum Number of Events That Can Be Attended¶
1235. Maximum Profit in Job Scheduling¶
632. Smallest Range Covering Elements from K Lists¶
from heapq import heapify, heapreplace
from math import inf
from typing import List
# Heap
def smallestRange(nums: List[List[int]]) -> List[int]:
heap = [(arr[0], i, 0) for i, arr in enumerate(nums)]
heapify(heap)
res_l = heap[0][0]
res_r = right = max(arr[0] for arr in nums)
while heap[0][2] + 1 < len(nums[heap[0][1]]):
_, i, j = heap[0]
x = nums[i][j + 1]
heapreplace(heap, (x, i, j + 1))
right = max(right, x)
left = heap[0][0]
if right - left < res_r - res_l:
res_l, res_r = left, right
return [res_l, res_r]
# Sliding Window Variable Min
def smallestRangeSliding(nums: List[List[int]]) -> List[int]:
pairs = sorted((x, i) for (i, arr) in enumerate(nums) for x in arr)
res_l, res_r = -inf, inf
empty = len(nums)
cnt = [0] * empty
left = 0
for r, i in pairs:
if cnt[i] == 0:
empty -= 1
cnt[i] += 1
while empty == 0:
l, i = pairs[left]
if r - l < res_r - res_l:
res_l, res_r = l, r
cnt[i] -= 1
if cnt[i] == 0:
empty += 1
left += 1
return [res_l, res_r]
if __name__ == "__main__":
nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
assert smallestRange(nums) == [20, 24]
assert smallestRangeSliding(nums) == [20, 24]
2542. Maximum Subsequence Score¶
1383. Maximum Performance of a Team¶
2503. Maximum Number of Points From Grid Queries¶
-
Tags: Array, Two Pointers, Breadth First Search, Union Find, Sorting, Heap Priority Queue, Matrix
2163. Minimum Difference in Sums After Removal of Elements¶
857. Minimum Cost to Hire K Workers¶
1606. Find Servers That Handled Most Number of Requests¶
1851. Minimum Interval to Include Each Query¶
218. The Skyline Problem¶
-
Tags: Array, Divide And Conquer, Binary Indexed Tree, Segment Tree, Line Sweep, Heap Priority Queue, Ordered Set
407. Trapping Rain Water II¶
2940. Find Building Where Alice and Bob Can Meet¶
-
Tags: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Heap Priority Queue, Monotonic Stack
3399. Smallest Substring With Identical Characters II¶
2589. Minimum Time to Complete All Tasks¶
3266. Final Array State After K Multiplication Operations II¶
1675. Minimize Deviation in Array¶
2617. Minimum Number of Visited Cells in a Grid¶
-
Tags: Array, Dynamic Programming, Stack, Breadth First Search, Union Find, Heap Priority Queue, Matrix, Monotonic Stack