22 articles
LeetCode 347 asks for k most frequent elements with a constraint: beat O(n log n). Learn why naive sort fails, how a min-heap of size k achieves O(n log k), and the elegant bucket sort insight that delivers true O(n) — with full visual dry run, common mistakes, and Python/JavaScript solutions for all three approaches.
Find the minimum refueling stops to reach target by greedily picking the largest fuel station passed so far whenever we run out.
Minimum cost to connect all sticks. Always connect the two cheapest (Huffman coding variant). Min-heap greedy: cost = sum of merged sticks each round.
Design Twitter with follow/unfollow and getNewsFeed using per-user tweet lists and a min-heap merge.
Find the Kth smallest element in an n×n row-and-column sorted matrix using binary search on value range or heap.
Find minimum conference rooms required by tracking room end times with a min-heap of ongoing meeting endings.
Design a simplified Twitter with follow/unfollow and a news feed showing the 10 most recent tweets from followed users.
Merge k sorted linked lists into one sorted list using a min-heap for O(n log k) time complexity.
Find the median dynamically as numbers are added using two heaps: a max-heap for the lower half and min-heap for upper.
Find the median of each sliding window of size k using two heaps (max-heap for lower half, min-heap for upper half) with lazy deletion.
Build the minimum spanning tree using Prim's algorithm: start from any vertex, greedily expand by always adding the minimum-weight crossing edge using a min-heap.
Advanced Dijkstra patterns: state-space Dijkstra for problems with extra constraints like K stops, fuel limit, or restricted nodes. The key is augmenting the state beyond just the node.
Find the minimum time to swim from (0,0) to (n-1,n-1) where you can only move to a cell when time >= cell value. Two approaches: Dijkstra O(n² log n) and binary search + BFS O(n² log n).
Design a stream that always returns the kth largest element after each add. Uses a min-heap of size k — the top is always the kth largest.
Find the minimum intervals to complete all tasks given cooldown n. Greedy with max-heap: always execute most frequent available task, idle only when forced.
Merge k sorted linked lists into one sorted list using a min-heap. O(n log k) time by always extracting the current minimum across all list heads.
Find the k most frequent elements using a max-heap or bucket sort. O(n) bucket sort approach using frequency as bucket index — faster than O(n log n) heap.
Calculate how much water can be trapped in a 3D height matrix. Uses a min-heap BFS starting from the boundary, always processing the lowest border cell to determine water trapped inside.
Design a simplified Twitter where users post tweets and follow each other, with getNewsFeed returning the 10 most recent tweets from followed users using a min-heap merge.
Design a search autocomplete system that returns top 3 historical queries matching the current prefix, sorted by frequency then lexicographically. Uses a Trie with per-node frequency maps.
Design a leaderboard that tracks player scores, supports score additions, top K sum queries, and player resets using a hashmap with sorted aggregation.
Maintain a running median from a data stream using two heaps: a max-heap for the lower half and a min-heap for the upper half, rebalancing after each insertion.