Sort and Search — How the Pattern Works
Sort and Search imposes monotonic order (nums[0] <= nums[1] <= ... <= nums[n - 1]) via an upfront O(n log n) sort so that proximity, rank, and threshold queries no longer require exhaustive scanning. Maintaining sorted order clusters equal and nearby values into contiguous runs while guaranteeing directional monotonicity across array indices. Subsequent operations can then discard half the search space per comparison with binary search (O(log n)) or prune an entire slice of candidate pairs per step with converging two pointers or a sliding window (O(n)). This reduces brute-force O(n^2), O(n * q), and O(2^n) subset/pair checks to O((n + q) log n), O(n log n), or O(n log R) over value range R.
- Output values depend on element values, counts, sums, or pairwise differences rather than original indices, making in-place reordering valid (or order only matters across divide-and-conquer halves, as in
Reverse Pairs). - Multiple threshold, distance, or budget queries (
qqueries overnitems) ask how many elements or how much prefix sum falls belowqor inside[x - d, x + d]. - Pair or triplet counting/optimization problems (
nums[i] + nums[j] < k,a + b > c) where sorting enables opposite-end pointers to count or eliminateright - leftpairs inO(1)time per step. - Maximin, minimax, or
k-th smallest metric problems over an implicit search space where testing a guessed thresholdmidyields a monotonic boolean predicate. - 2D dominance or greedy marginal-cost problems (
Russian Doll Envelopes,Put Marbles in Bags) where sorting one dimension or independent cut costs isolates a tractable 1D subproblem.
- Sorting when original index order is part of the constraint: sorting the full array destroys
i < jordering unless pairs are symmetric (nums[i] + nums[j]) or order is preserved across recursive merge-sort halves (Reverse Pairs). - Confusing
bisect_left(>= x) withbisect_right(> x): off-by-one bugs arise on duplicate runs when counting elements<= q(requiresbisect_right) versus strictly< q(requiresbisect_left). - Wrong secondary tie-breaker in 2D sorting: sorting
(width, height)ascending inRussian Doll Envelopesallows equal-width envelopes to form an invalid increasing height pair; tie-breaking by(width, -height)is required. - Midpoint rounding stalls in binary search on the answer: updating
low = midwith floor division(low + high) // 2loops infinitely whenhigh == low + 1; use closed-interval[low, high]updates (low = mid + 1,high = mid - 1) or upper midpoints.
import bisect
def sort_and_binary_search(nums, queries):
nums.sort()
ans = []
for q in queries:
# First index i with nums[i] >= q (use bisect_right for > q)
idx = bisect.bisect_left(nums, q)
ans.append(idx)
return ansdef sort_and_two_pointers(nums, limit):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] > limit:
count += right - left
right -= 1
else:
left += 1
return countdef binary_search_on_answer(nums, k):
nums.sort()
low, high = 0, nums[-1] - nums[0]
while low < high:
mid = (low + high) // 2
if count_within(nums, mid) >= k:
high = mid
else:
low = mid + 1
return low