Tags
- ⭐ = solved in first try
- 📍 = revisit
- 🔥 = important
- ⚠️ = solved but edge case missed
- 👀 = solved but had to see little solution first
- 🐢 = solved, but less optimized
- 💀 = out of the box
- no tag = pending/not started
4. Pattern: Binary Search
4.1 Direct Binary Search (Sorted Array)
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Binary Search (easy) | |||
| 2. First Bad Version (easy) | pure template — condition is the API itself | ||
| 3. Sqrt(x) (easy) | find min k where k*k > x, return k-1 | ||
| 4. Search Insert Position (easy) | min k where nums[k] >= target; hi = n (not n-1) | ||
| 5. Find First and Last Position (medium) | run template twice: >= target and > target | ||
| 6. Find Smallest Letter Greater Than Target (easy) | upper_bound variant | ||
| 7. Count Negative Numbers in a Sorted Matrix (easy) | binary search per row or staircase |
4.2 Binary Search on Answer (Feasibility Check)
💡 Signal: “minimize the maximum” or “find minimum X such that constraint Y is satisfied”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Koko Eating Bananas (medium) | lo=1, hi=max. feasible: sum(ceil(p/speed)) ⇐ h | ||
| 2. Capacity To Ship Packages Within D Days (medium) | lo=max(w), hi=sum(w). greedy pack simulation | ||
| 3. Split Array Largest Sum (hard) | identical to #2. same feasible function | ||
| 4. Minimum Number of Days to Make m Bouquets (medium) | lo=min, hi=max. count adjacent bloomed flowers | ||
| 5. Find the Smallest Divisor Given a Threshold (medium) | lo=1, hi=max. sum(ceil(x/d)) ⇐ threshold | ||
| 6. Minimum Limit of Balls in a Bag (medium) | min max-size. operations to split = ceil(x/mid)-1 | ||
| 7. Magnetic Force Between Two Balls (medium) | maximize minimum distance — flip condition | ||
| 8. Minimized Maximum of Products Distributed to Any Store (medium) | min max products. feasible: sum(ceil(q/mid)) ⇐ n | ||
| 9. Maximum Candies Allocated to K Children (medium) | maximize — BS on answer, count piles >= mid | ||
| 10. Sum of Mutated Array Closest to Target (medium) | BS on the mutation value |
4.3 Kth Smallest (Binary Search + Counting)
💡 Signal: “kth smallest” in a virtual/implicit collection
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Kth Smallest Number in Multiplication Table (hard) | count per row: min(mid/i, n). BS on value | ||
| 2. Find K-th Smallest Pair Distance (hard) | sort + two pointers to count pairs ≤ mid | ||
| 3. Ugly Number III (medium) | inclusion-exclusion with LCM | ||
| 4. Kth Smallest Element in a Sorted Matrix (medium) | count elements ≤ mid column by column |
4.4 Rotated / Peak / Tricky Conditions
💡 Signal: sorted array with a twist — rotation, peak, bitonic
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Find Peak Element (medium) | nums[mid] < nums[mid+1] → go right; else go left | ||
| 2. Peak Index in a Mountain Array (medium) | same as #1 | ||
| 3. Find Minimum in Rotated Sorted Array (medium) | compare mid with hi. mid > hi → min is right | ||
| 4. Search in Rotated Sorted Array (medium) | one half always sorted — check if target in that half | ||
| 5. Search in Rotated Sorted Array II (medium) | duplicates: lomidhi → shrink both ends | ||
| 6. Find Minimum in Rotated Sorted Array II (hard) | duplicates: mid==hi → hi— to break tie | ||
| 7. Missing Element in Sorted Array (medium) | count missing = nums[mid] - nums[0] - mid | ||
| 8. Search in a Nearly Sorted Array (GFG) | check mid-1, mid, mid+1 |
4.5 Binary Search on Two Sorted Arrays
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Median of Two Sorted Arrays (hard) | BS on shorter array. partition both into equal halves. | ||
| 2. Kth Element of Two Sorted Arrays (GFG) | same partition idea, target = k instead of half |
4.6 Matrix Binary Search
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Search a 2D Matrix (medium) | treat as flat array: row = mid/n, col = mid%n | ||
| 2. Search a 2D Matrix II (medium) | staircase from top-right corner. O(m+n) |
4.7 C++ STL Binary Search
💡 When problem gives sorted data + needs lookups, reach for
lower_bound/upper_bound/map
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Time Based Key-Value Store (medium) | map + upper_bound, then prev(it) | ||
| 2. Online Election (medium) | precompute leader, upper_bound on timestamps | ||
| 3. Random Pick with Weight (medium) | prefix sum + lower_bound on random target | ||
| 4. Find Right Interval (medium) | store start→idx in map, lower_bound on each end | ||
| 5. H-Index II (medium) | sorted → BS for n-mid >= citations[mid] |
4.8 Misc / Advanced
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Pow(x, n) (medium) | binary exponentiation, not classical BS but O(log n) division | ||
| 2. Divide Two Integers (medium) | repeated doubling. BS-like halving approach | ||
| 3. Count of Smaller Numbers After Self (hard) | merge sort or BIT. BS on sorted suffix | ||
| 4. Shortest Subarray With Sum at Least K (hard) | deque + prefix sum (not pure BS) | ||
| 5. Max Sum of Rectangle No Larger Than K (hard) | 2D prefix sum + ordered set + BS |