Category: foundational_interview
-
LeetCode 658: Find K Closest Elements
link Since arr is sorted, the closest element to would be near ‘s insert index. With left and right pointers we keep collecting the closest elements from the two possible candidates. Time: , space: .
-
LeetCode 528: Random Pick with Weight
link We can binary-search in the cumulative weight list to pick an index with frequency proportional to its weight. Operation Time Space __init__ pickIndex
-
LeetCode 857: Minimum Cost to Hire K Workers
link If we hire a group of k workers, each worker must be paid at the maximum pay-rate where pay-rate is . Backtrack We can try all k-subsets of workers to find the minimum cost. Time: , space: . Sort and top-k Cost is a product of max-rate and sum-of-qualities. If we did not have…
-
LeetCode 973: K Closest Points to Origin
link k-closest points are the k-smallest distance points. We use a max-heap to keep track of the k-smallest distance points. Time: , space: .
-
LeetCode 767: Reorganize String
link If all characters were distinct, we could put them in any order and it works. For two instances of a repeated character, we need to put a different character in-between. The best choice to put in-between two instances of the most frequent character is the second most frequent character. Because, in that way we…
-
LeetCode 378: Kth Smallest Element in a Sorted Matrix
link Sweep line With row heads in a min-heap, we can traverse the elements in sorted order using sweep line. Time: , space: .
-
LeetCode 23: Merge k Sorted Lists
link Sweep line With the list heads in a min-heap, we can traverse them in sorted order using sweep line. If we have a tuple like in the heapq, the primary key is and the secondary key is . The primary keys are compared using strictly-less-than operator. If there is a tie, the comparison is…
-
LeetCode 373: Find K Pairs with Smallest Sums
link For a pair , and . Sweep line We can group the pairs by distinct ‘s. Since a group has a fixed and nums2 is sorted, we can consider each group as a sorted list of pairs . Keeping group heads in a min-heap, we can generate the pairs in sorted order of their…
-
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.…
unreasonably effective 