Category: foundational_interview
-
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…
-
LeetCode 24: Swap Nodes in Pairs
link With four pointers (a, b, c, d) we can swap (b, c) in-place. Since head might change, we introduce a dummy node to simplify edge-case handling. Time: , space: .
-
LeetCode 1474: Delete N Nodes After M Nodes of a Linked List
link With (prev, curr) pointers, we skip nodes and then delete nodes. Time: , space: .
-
LeetCode 725: Split Linked List in Parts
link First we find the expected group sizes from the length of the list and k and then copy the heads of the groups as we do a second pass. Time: , space: .
-
LeetCode 2074: Reverse Nodes in Even Length Groups
link Two pass We first collect the groups in a list and then connect the groups. If a group has even size we also reverse it. Time: , space: . One pass For the groups we have two types of operations: If the count of nodes processed by an operation is smaller than the expected…
-
LeetCode 92: Reverse Linked List II
link One pass We jump to the left node and reverse (right-left+1) number of nodes. We then fix two pointers: To simplify the (prev, curr) logic we introduce a dummy node. Time: , space: .
-
LeetCode 25: Reverse Nodes in k-Group
link Two pass From the length of the list we find how many -groups need to be reversed and we reverse each -group in sequence. While reversing a -group, we have two types of operations: Time: , space: . One pass While reversing a -group, if nodes got reversed where , we know we have…
unreasonably effective 