Category: heap
-
LeetCode 436: Find Right Interval
link For an interval we want to find the lowest such that . Sort and search Keeping the start times sorted let us find efficiently with binary-search. Time: , space: . Heaps Say, in the sorted start-times, we are searching right indices in order of end-times (smaller to bigger). If does not work for ,…
-
LeetCode 2231: Largest Number After Digit Swaps by Parity
link To make the number larger, we want to move bigger digits to the left. We can move a digit to the left via swap only if the target index has a same-parity digit. In other words, as we scan num from left to right, we want to pick the largest digit with matching parity.…
-
LeetCode 2402: Meeting Rooms III
link Looking at the scheduling requirements: Say there are meetings. Time: , space: .
-
LeetCode 480: Sliding Window Median
link Like the data stream median problem, we use two heaps. However, as numbers fall off the sliding window, we should also remove them from the heaps. Since, heaps do not support efficient search and delete, we delete lazily. When an index fall off the sliding window, we mark that index as stale. In the…
-
LeetCode 295: Find Median from Data Stream
link Median is the middle point in sorted order. So, we keep track of the middle point by keeping left and right halves of the values in two heaps: (1) max heap for the left half (2) min heap for the right half. So, the tops of these two heaps determine the median at all…
-
LeetCode 502: IPO
link Greedy Among the projects we have enough capital to do, we pick the most profitable one. Since total capital never decreases, once a project has been moved to the profit heap, unless we decide to do it, it remains there. Thus, a project is either in capital heap or profit heap. Each project is…
unreasonably effective 