-
LeetCode 78: Subsets
link Take or skip: Recursion We skip or take each element. Time: , space: . Take or skip: Iterative Say we have subsets with (n-1) elements. For the n-th element, we can take it or we can skip it. Skipping n-th element is same as keeping the subsets with only (n-1) elements or the subsets…
-
LeetCode 2824: Count Pairs Whose Sum is Less than Target
Sort and two pointers In sorted order, if nums[i] + nums[j] < target, then with nums[i] as the first element there are (j-i) second elements that can make a valid pair. Time: , space: .
-
LeetCode 1337: The K Weakest Rows in a Matrix
link We want to find k-smallest strength row, so we use a size-limited max heap with count of ones as the primary key and row-index as the secondary key. Since in a row 0’s and 1’s are nicely separated, we can use binary search to find the index of the leftmost 0 which is the…
-
LeetCode 1802: Maximum Value at a Given Index in a Bounded Array
link Since all numbers in nums must be positive, bounded_sum(nums) must be at least n, so maxSum >= n. As we increase nums[index] the predicate bounded_sum(nums) > maxSum evaluates like: False, False, False, True, True, … In other words, once the predicate becomes true, it remains True. We want the value of nums[index] for the…
-
LeetCode 540: Single Element in a Sorted Array
link Bitwise If we xor all elements in the array, the single element remains. Time: , space: . Binary search Since nums is sorted, all repeated numbers appear consecutively. All numbers except one has duplicates so, len(nums) is odd. Also, removing a pair of (consecutive) duplicate numbers breaks nums into two halves: one half has…
-
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…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 