Array Search, Selection, And Dynamic Programming

What's being tested

Array search, selection, and dynamic programming problems test whether you can turn brute-force scans into structured O(log n), O(n), or O(n log n) solutions. Interviewers look for clean boundary handling, invariant-based reasoning, and the ability to explain time/space tradeoffs under production-like constraints.

Patterns & templates

• Binary search boundaries — implement lower_bound(nums, target) and upper_bound(nums, target); O(log n) time, avoid off-by-one errors.

• Quickselect partitioning — find kth largest via in-place partition; average O(n), worst O(n^2), randomized pivot reduces risk.

• Heap selection — maintain a min-heap of size k; O(n log k) time, safer than Quickselect when worst-case predictability matters.

• Dynamic programming for subsequences — LIS uses dp[i] = max(dp[j] + 1) for j < i; O(n^2) baseline, simple and explainable.

• Patience sorting LIS — maintain tails and binary-search replacement index; O(n log n) time, but tails is not the actual subsequence.

• Prefix/suffix parity sums — deletion-fairness problems need even/odd sums before and after index removal; O(n) time, O(1) possible.

• Interval sweep / min-heap rooms — sort start times or intervals; count overlapping meetings in O(n log n), clarify inclusive vs exclusive endpoints.

Common pitfalls

Pitfall: Returning any target index instead of the first/last boundary misses the core binary search invariant.

Pitfall: Treating kth largest as index k after sorting; it is usually nums[len(nums) - k] in ascending order.

Pitfall: For LIS, using <= instead of < changes “increasing” into “non-decreasing.”

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.