Category: modified_binary_search
-
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
unreasonably effective 