Topic 4: Binary Search

Canonical Questions #

Key Intuition: we are able to exploit the property of monotonicity in the order of a sequence to our benefit. This monotonicty may be seen in various factors / domains: the input, the output, the intermediate search space, some sort of virtual domain.

Classic Search over Sorted Array #

Objective
- Efficiently find the target element or boundary positions in a sorted array.
In some instances we might be posed with a multi-dimensional input and we should attempt to flatten it in a way that works for us.

Problems #

First/Last Position of Element in Sorted Array (34)

This question asks us to implement a custom bisect_left and bisect_right. The key learning here is that the accuracy matters. Just go slow and be clear in two aspects: a) what the while condition’s predicate function should be and b) how the recursion / boundary adjustment happens.

It’s for this reason that the open-open range boundary via left and right pointers is usually the easier way to write this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
      class Solution:
        def searchRange(self, nums: List[int], target: int) -> List[int]:
            """
            Objective is to implement bisect_left and bisect_right manually.

            In this solution, we shall use inclusive ranges for the helper functions, which affects how the rest of the recursive logic is implemented.
            """
            def search_left(left, right, target):
                """
                The bounds matter. We shall use left to right inclusive, which changes the while conditional.
                """
                res = -1
                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] >= target: # try searching to the left:
                        if nums[mid] == target:
                            res = mid
                            right = mid - 1
                    else:
                        left = mid + 1

                return res

            def search_right(left, right, target):
                """
                Left and right inclusive ranges, hence the while condition is not strict.
                """
                res = -1
                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] <= target: #  attempt to search right
                        if nums[mid] == target:
                            res = mid
                            left = mid + 1
                    else:
                        right = mid - 1
                return res

            n = len(nums)
            left_res = search_left(0, n - 1, target)
            if left_res == -1:
                return [-1,-1]

            right_res = search_right(0, n - 1, target)
            return [left_res, right_res]

Code Snippet 1: First/Last Position of Element in Sorted Array (34)

Pattern Extraction

Core Insight: Two binary searches with different tie-breaking: one that continues left on equality (finds first occurrence) and one that continues right (finds last occurrence). Pattern Name: Binary Search with Directional Tie-Breaking Canonical Section: Binary Search > Standard Sorted Array Search Recognition Signals:

Sorted array with duplicates
Need first/last/all positions of a target value
$O(\log n)$ required

Anti-Signals:

Need the count of occurrences — compute as last - first + 1 after finding both bounds
Array is unsorted — binary search doesn’t apply
Need to find the closest value, not an exact match — different binary search variant

Decision Point: This is bisect_left (first) and bisect_right - 1 (last) in Python’s bisect module. Understanding the tie-breaking direction is the core skill.

Pitfalls and Misconceptions

Trap: Using a single binary search and then scanning linearly for the first/last occurrence. Why: Linear scan after binary search degrades to $O(n)$ when all elements are the target. Correction: Use two separate binary searches: one for the left bound, one for the right bound. Both are $O(\log n)$.
Trap: Off-by-one in the boundary conditions — using mid - 1 vs mid in the wrong direction. Why: For left-bound search: when nums[mid] = target=, set right = mid (not mid - 1). For right-bound: set left = mid + 1. Mixing these up causes infinite loops or missed elements. Correction: Left-bound: if nums[mid] > target: right = mid else: left = mid + 1=. Right-bound: if nums[mid] < target: left = mid + 1 else: right = mid=.

Problem Mutations

What if you needed the count of occurrences? (stress-tests: position vs count) count = last_pos - first_pos + 1. Two binary searches, $O(\log n)$ total.
What if the target doesn’t exist and you need the insertion point? (stress-tests: existence assumption) bisect_left returns the insertion point. This IS the generalisation. Connects to LC 35 Search Insert Position.
What if the array were rotated? (stress-tests: sorted assumption) Need to determine which half is sorted before deciding the search direction. Connects to LC 33 Search in Rotated Sorted Array.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for First/Last Position of Element in Sorted Array generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Searching a 2D Matrix (74)

Key Idea is to search by the starting numbers to find the row and to do it again within the row. So dimension-by-dimension. This works in $O(log m + log n)$ speed since it’s dimension by dimension. This should be the first-reach implementation.

For an improvement, better still, we can treat it as a flattened array. This works in $O(log(m * n))$ speed

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   class Solution:
       def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
           if not matrix or not matrix[0]:
               return False

           m, n = len(matrix), len(matrix[0])
           left, right = 0, ( m * n ) - 1

           while left <= right:
               mid = left + (right - left) // 2
               # TRICK: ⭐️ this is pretty!
               row, col = divmod(mid, n)
               val = matrix[row][col]
               if val == target:
                   return True
               elif val < target:
                   left = mid + 1
               else:
                   right = mid - 1
           return False

Code Snippet 2: Searching a 2D Matrix (74)

Pattern Extraction

Core Insight: The 2D matrix with sorted rows and each row’s first element greater than the previous row’s last is effectively a single sorted 1D array. Map 1D index to 2D: row = mid // cols, col = mid % cols. Pattern Name: Virtual 1D Binary Search on 2D Matrix Canonical Section: Binary Search > Standard Sorted Array Search Recognition Signals:

Matrix where rows are sorted AND first element of each row > last element of previous row
$O(\log(mn))$ required
Single-target search

Anti-Signals:

Rows are sorted but NOT globally ordered (row starts not > previous row ends) — use staircase search ($O(m + n)$). Connects to LC 240 Search a 2D Matrix II
Need to find a range, not a single element — different approach

Decision Point: If the matrix is “fully sorted” (flattened is sorted), virtual 1D binary search. If only rows/columns are sorted independently, staircase search from top-right corner.

Pitfalls and Misconceptions

Trap: Doing two binary searches (one for the row, one within the row). Why: Works but is unnecessarily complex. The matrix is a contiguous sorted sequence; one binary search with index mapping is cleaner. Correction: Single binary search with row, col = divmod(mid, cols).
Trap: Confusing this problem with LC 240 (Search a 2D Matrix II). Why: LC 240 has a weaker sorting guarantee (each row and column sorted, but not globally). The staircase search from the top-right works for LC 240 but binary search on the virtual 1D array works for LC 74. Correction: Check whether the matrix is “fully sorted” or “row/column sorted independently” to choose the approach.

Problem Mutations

What if rows and columns are sorted but the first element of each row is NOT guaranteed to be > previous row’s last? (stress-tests: global sort assumption) Staircase search from top-right: move left if value is too large, down if too small. $O(m + n)$. Connects to LC 240.
What if the matrix were sparse? (stress-tests: dense assumption) Store non-zero elements in a sorted list of (row, col, val) tuples and binary search on that.
What if you needed to count elements less than a target? (stress-tests: search vs counting) For the fully-sorted case, binary search gives the count directly (insertion point). For the row/column sorted case, use the staircase approach counting elements per row.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Searching a 2D Matrix generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Search on Answer / Decision Space #

Objective
- Perform binary search over a numeric answer or parameter space with a monotonic feasibility predicate to find optimal solutions.

Problems #

Koko Eating Bananas (875)

We know that the eating speed is the search space and it’s monotonically increasing so that’s what we have to manually search through because we can’t use bisect function for this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
   class Solution:
     def minEatingSpeed(self, piles: List[int], h: int) -> int:
       max_pile = max(piles)
         if h == len(piles):
             return max_pile

         eating_time = lambda rate: sum((-(-pile//rate)) for pile in piles)

         left, right = 1, max_pile # NOTE: inclusive ranges

         ans = right # will definitely reach this
         while left <= right:
           mid = left + ((right - left) // 2)
           time = eating_time(mid)
             if (time <= h): # fast enough but we wanna find slower rate
               ans = mid # save this at least
               right = mid - 1
             else:
               left = mid + 1

         return ans

Code Snippet 3: Koko Eating Bananas (875)

Pattern Extraction

Core Insight: Binary search on the answer space: the eating speed $k$ is the search variable. For each candidate $k$, check feasibility (can Koko finish within $h$ hours?). The feasibility check is monotonic — if speed $k$ works, any speed $> k$ also works. Pattern Name: Binary Search on Answer (Monotonic Predicate) Canonical Section: Binary Search > Binary Search on Answer Space Recognition Signals:

“Find the minimum/maximum value satisfying a condition”
The condition is monotonic (once it becomes True, it stays True for all larger/smaller values)
The answer space is bounded and orderable (integers in a range)
Feasibility check is cheaper than brute-forcing all candidates

Anti-Signals:

No monotonic predicate (feasibility isn’t monotonic in the search variable) — can’t binary search
The answer space is continuous/unbounded — need to bound it first or use different approach
The feasibility check itself is expensive ($O(n^2)$) — binary search might not help enough

Decision Point: “Minimum speed/capacity/time such that X is possible” where feasibility is monotonic = binary search on answer. The pattern template: lo, hi = bounds; while lo < hi: mid = (lo+hi)//2; if feasible(mid): hi = mid; else: lo = mid + 1. Interviewer Comms: “I binary search on the eating speed. For each candidate speed $k$, I compute total hours: $\\sum \\lceil\\text{pile}_i / k\\rceil$. If total $\\leq h$, $k$ is feasible and I search lower. If not, I search higher. Feasibility check is $O(n)$, binary search is $O(\\log(\\max(\\text{piles})))$, total $O(n \\log M)$.”

Pitfalls and Misconceptions

Trap: Linear scanning through all possible speeds instead of binary searching. Why: Speed range is $[1, \\max(\\text{piles})]$. Linear scan is $O(M \\cdot n)$; binary search is $O(n \\log M)$. Correction: Binary search over the speed range with a feasibility predicate.
Trap: Using pile // k instead of ceil(pile / k) for hours per pile. Why: Koko can’t eat a fraction of a pile per hour — she takes a full hour even for the remainder. Floor division undercounts hours. Correction: Use math.ceil(pile / k) or the integer trick (pile + k - 1) // k or -(-pile // k).
Trap: Setting the upper bound too low (e.g., sum(piles) instead of max(piles)). Why: The minimum speed is 1 and the maximum useful speed is max(piles) (faster than this has no benefit since Koko eats at most one pile per hour). Correction: lo, hi = 1, max(piles).

Problem Mutations

What if Koko could eat from multiple piles per hour? (stress-tests: one pile per hour constraint) The ceiling division per pile no longer applies. Total bananas / speed gives hours. Much simpler feasibility check.
What if the number of hours were not given and you needed to minimise hours? (stress-tests: constraint type) Not a binary search problem anymore — just eat at max speed. The constraint (finish within $h$ hours) is what makes binary search useful.
What if piles were dynamic (new piles added over time)? (stress-tests: static assumption) Need to re-evaluate feasibility as piles change. Could amortise with incremental sum tracking.
What if you needed to MAXIMISE the eating speed subject to “takes at least $h$ hours”? (stress-tests: min vs max direction) Flip the binary search: if feasible at speed $k$ (takes $\\geq h$ hours), search higher. lo = mid + 1; hi = mid. Same pattern, different direction. Connects to LC 1011 Capacity To Ship Packages.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Koko Eating Bananas generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Capacity To Ship Packages Within D Days (1011)

Approach: leverages the binary search over the answer space (capacity) combined with a greedy check for feasibility

NOTE: need to adapt the binary search over the answer space (the ship capacity), but bisect works on sorted arrays, not on a computed range, hence the manually written:

Also to take note of the logical gotcha: there will be at least one trip needed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
   class Solution:
      def shipWithinDays(self, weights: List[int], days: int) -> int:
          def get_days(capacity):
             num_trips = 1 # GOTCHA (logical): at least one trip needed
             curr_load = 0
              for w in weights:
                  if curr_load + w > capacity:
                     num_trips += 1
                     curr_load = w
                  else:
                     curr_load += w

              return num_trips

          low = min_capacity = max(weights) # else we can't even bring this package over
          high = sum(weights) # then we can just take it all in one go

          ans = high
          # inclusive ranges:
          while low <= high:
             mid = low + (high - low) // 2
              if get_days(mid) <= days:
                 # restrict the search on a smaller space:
                  high = mid - 1
                  ans = mid
              else:
                 low = mid + 1

          return ans

Code Snippet 4: Capacity To Ship Packages Within D Days (1011)

For manual implementations, I prefer using inclusive ranges, it differs in pattern from the typical pythonic approach of open-closed though.

Pattern Extraction

Core Insight: Binary search on the ship capacity. For each candidate capacity, greedily simulate loading: start a new day when adding the next package would exceed capacity. Feasibility = total days $\leq$ D. Pattern Name: Binary Search on Answer (Monotonic Predicate) Canonical Section: Binary Search > Binary Search on Answer Space Recognition Signals:

“Find minimum capacity/budget/threshold to complete within K steps”
Greedy simulation gives feasibility in $O(n)$
Monotonic: larger capacity $\implies$ fewer days needed

Anti-Signals:

Packages can be reordered — this would be bin-packing (NP-hard). The constraint that order is preserved makes greedy simulation valid.
Need to optimise which packages go on which day — order preservation makes it greedy, not combinatorial

Decision Point: This is the same pattern as Koko Eating Bananas (LC 875). lo = max(weights) (must fit the heaviest package), hi = sum(weights) (ship everything in one day).

Pitfalls and Misconceptions

Trap: Setting lo = 1 instead of lo = max(weights). Why: The ship must be able to carry the heaviest single package. Any capacity less than max(weights) is infeasible. Correction: lo = max(weights), hi = sum(weights).
Trap: Forgetting to start a new day when the current day’s load plus the next package exceeds capacity. Why: Off-by-one in the greedy simulation — either shipping an overloaded day or starting a new day too early. Correction: if current_load + weight > capacity: days + 1; current_load = weight=.

Problem Mutations

What if packages could be split across days? (stress-tests: indivisible items) Feasibility simplifies to total_weight / capacity < D=. No greedy simulation needed.
What if packages could be reordered? (stress-tests: order preservation) Becomes bin-packing, which is NP-hard. The order constraint is load-bearing.
What if the cost were proportional to capacity (minimise cost)? (stress-tests: binary answer) If cost is linear in capacity, same binary search. If cost is non-linear, the monotonicity may break.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Capacity To Ship Packages Within D Days generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Minimum Time to Activate String (3639)

We search on the answer space and for the predicate we do a complement based, arithmetic calculation that we shall use a complement approach to count. The premise automatically makes us think of this complementary counting approach.

To get the number of valid substrings, we can take the total number of substrings (arithmetic) and then subtract away the total number of invalid substrings (for which we sliding window it and use arithmetic).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
   from typing import List

   class Solution:
      def minTime(self, s: str, order: List[int], k: int) -> int:
         n = len(s)

          def is_active(t):
             """
              To get the number of valid substrings, we can take the total number of substrings (arithmetic) and then subtract away the total number of invalid substrings (forwhich we sliding window it and use arithmetic).
              """
             stars = set(order[:t + 1])
             total_substrings = n * (n + 1) // 2 # nCr

              count_no_star = 0
              length = 0
              for i in range(n):
                  if i not in stars:
                     length += 1
                  else:
                     count_no_star += length * (length + 1) // 2
                     length = 0 # we start again, hence length == 0
                     count_no_star += length * (length + 1) // 2

              return (total_substrings - count_no_star) >= k

          left, right = 0, n
          min_t = -1
          while left <= right:
             mid = left + (right - left) // 2
              if is_active(mid):
                 min_t = mid
                 right = mid - 1
              else:
                 left = mid + 1

          return min_t

Code Snippet 5: Minimum Time to Activate String (3639)

Pattern Extraction

Core Insight: Binary search on the answer (time $t$). For each candidate $t$, greedily check if the string can be activated by simulating the process within $t$ time units. Pattern Name: Binary Search on Answer (Monotonic Predicate) Canonical Section: Binary Search > Binary Search on Answer Space Recognition Signals:

“Minimum time to achieve X” where feasibility is monotonic in time
Greedy feasibility check per candidate

Anti-Signals:

Non-monotonic feasibility – can’t binary search

Decision Point: Same template as Koko Bananas (LC 875) and Capacity Ship (LC 1011). The feasibility check is problem-specific but the binary search structure is identical.

Pitfalls and Misconceptions

Trap: Not identifying the monotonic structure (more time $\implies$ easier to activate). Why: Without recognising monotonicity, you might try DP or simulation instead of binary search. Correction: Ask: “if time $t$ works, does time $t+1$ also work?” If yes, binary search.
Trap: Getting the feasibility check wrong. Why: The greedy simulation within the feasibility check is the hard part. Binary search is just the wrapper. Correction: Focus on the inner check: what operations can you perform within $t$ time, and do they suffice?

Problem Mutations

What if the activation process were non-monotonic? (stress-tests: monotonicity) Can’t binary search. Need DP or exhaustive search.
What if there were multiple strings to activate simultaneously? (stress-tests: single target) Need to consider interactions between activations. More complex feasibility check.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Minimum Time to Activate String. Review against personal solving experience.

1482. Minimum Number of Days to Make m Bouquets

This is an interesting one because it matters how we write the helper function, it has to be performant enough. There’s a bunch of implicit mistakes I made:

correctness when doing the accumulation:
- we can’t allow overlapping ranges – this means we need to jump by the size of the buffer once we meet the requirement
- we must ensure that the fixed length window is always adhered – this needs a good guard case for the iteration loop actually

speed of doing the calculation: avoid creating intermediate slices in hot loops

it’s natural to reach for python slices when doing this, however, it has hidden overheads because it won’t end up being a single pass anymore. The best approach is to write this as you would the caterpillar solution.

compare the ready functions below to see what I mean:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
              def ready(day: int) -> bool:
                  completed, buffer = 0, 0 # buffer: consecutvie bloomed
                  for bloom in bloomDay:
                      if bloom > day:
                          buffer = 0
                          continue
                      buffer += 1
                      if buffer == k:
                          completed += 1
                          buffer = 0 # reset it
                  return completed >= m

              def ready_slow_multipass(day: int) -> bool:
                  completed, left = 0, 0 # left is a ptr
                  # fixed sized sliding window:
                  while left + k <= len(bloomDay):
                      if all(d <= day for d in bloomDay[left:left + k]):
                          completed += 1
                          left += k # avoids overlapping regions
                      else:
                          left += 1
                  return completed >= m

              def ready_wrong_no_fixed_length_guard(day: int):
                  completed = 0
                  left = 0
                  # fixed size window:
                  while left < len(bloomDay):
                      if all(d <= day for d in bloomDay[left: left + k]):
                          completed += 1
                          left = left + k
                      else:
                          left += 1
                  return completed >= m

Code Snippet 6: 1482. Minimum Number of Days to Make m Bouquets

Gotcha: Slicing Inside Hot Loops Has Hidden Cost
When you call all(predicate(d) for d in arr[left:left+k]) inside a loop that increments left by 1, you’re paying O(k) per iteration for slicing and checking, not O(1).

                while left + k <= len(arr):
                    if all(d <= day for d in arr[left : left + k]):
                        # ... match found
                        left += k
                    else:
                        left += 1  # ← Slides by 1, repeats O(k) work

Code Snippet 7: SLOW: $O(n·k)$ per ready() call

      completed, buffer = 0, 0
                for val in arr:
                    if val > day:
                        buffer = 0
                        continue
                    buffer += 1
                    if buffer == k:
                        completed += 1
                        buffer = 0

Code Snippet 8: FAST: O(n) per ready() call

The single-pass approach is O(1) per element, no slicing overhead.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
          class Solution:
              def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
                  """
​                  - looking for numDays which will go from at worst the highest bloomday -- we need to mimise this
​                    - low, high = 1, max(bloomDay)
​                  - trivial rejection case: when not enough flowers
                  """
                  # trivial rejection: not enough flowers
                  if (m * k) > len(bloomDay):
                      return -1

                  def ready(day: int) -> bool:
                      completed, buffer = 0, 0 # buffer: accums consecutive bloomed flowers
                      for bloom in bloomDay:
                          if bloom > day:
                              buffer = 0
                              continue
                          buffer += 1
                          if buffer == k:
                              completed += 1
                              buffer = 0 # reset it
                      return completed >= m

                  low, high = min(bloomDay), max(bloomDay)
                  ans = high
                  while low <= high:
                      mid = low + (high - low) // 2
                      if ready(mid): # can try smaller
                          ans = mid
                          high = mid - 1
                      else:
                          low = mid + 1

                  return ans

Code Snippet 9: Single pass approach O(1) per element, no slicing overhead

Pattern Extraction

Core Insight: Binary search on the day $d$. For each candidate $d$, greedily count how many bouquets of $k$ consecutive bloomed flowers can be formed from flowers that bloom by day $d$. Pattern Name: Binary Search on Answer (Monotonic Predicate) Canonical Section: Binary Search > Binary Search on Answer Space Recognition Signals:

“Minimum day such that $m$ bouquets can be formed”
More days $\implies$ more flowers bloomed $\implies$ easier to form bouquets (monotonic)
Greedy consecutive-count check per candidate day

Anti-Signals:

Flowers can wilt (non-monotonic) – binary search breaks

Decision Point: Same family as Koko Bananas. lo = min(bloomDay), hi = max(bloomDay). Feasibility = greedy consecutive counting.

Pitfalls and Misconceptions

Trap: Setting lo = 0 instead of lo = min(bloomDay). Why: No flower blooms before the earliest bloom day. Starting lower wastes binary search iterations. Correction: lo = min(bloomDay), hi = max(bloomDay).
Trap: Counting non-consecutive flowers as forming a bouquet. Why: Bouquets require $k$ ADJACENT bloomed flowers. Non-adjacent flowers don’t count. Correction: Reset consecutive counter when a non-bloomed flower is encountered.

Problem Mutations

What if bouquets didn’t need consecutive flowers? (stress-tests: adjacency constraint) Much simpler: just count total bloomed flowers $\geq m \cdot k$. No greedy consecutive logic needed.
What if each bouquet required different numbers of flowers? (stress-tests: uniform size) More complex feasibility check. Greedy consecutive counting must be adapted per bouquet requirement.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Minimum Number of Days to Make m Bouquets. Review against personal solving experience.

Finding Min/Max Satisfying Conditions $\implies$ usually an Optimisation Problem #

Objective
- Find the minimum or maximum value that satisfies a given monotonic condition, often optimization problems.

Problems #

⭐️⭐️ Searching in Implicit / Virtual Domains #

Objective
- Perform binary search over conceptual or implicit domains not explicitly stored but probed by queries or functions.

Problems #

Median of Two Sorted Arrays (4) (conceptual virtual search)

Median is less about the value, more about the relative ordering of the elements (position-based). This question explores our ability to handle such virtual spaces.

The first observation that helps us that the middle of the two arrays is where we will eventually find our global median. This means we can use that as boundaries and keep searching for the optimal “partition”.

We do this test considering the immediate left and immediate right values of both pointers (in the respective arrays).

This is a lot more intuitive after looking a the solution but is likely something that is hard to see unless we break it down to its primitives.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   class Solution:
      def findMedianSortedArrays(self, nums1, nums2):
         # Ensure nums1 is the smaller array
          if len(nums1) > len(nums2):
             nums1, nums2 = nums2, nums1

          m, n = len(nums1), len(nums2)
          total = m + n
          half = total // 2

          # we know that the region between the median of nums 1 and median of nums 2 is where it will lie, this is the virtual search space.
          left, right = 0, m # pointers within nums1
          while True:
             i = (left + right) // 2  # Partition within nums1 -- always
             j = half - i             # Partition within nums2 (because len(nums2) >= len(nums1))
             nums_i_left, nums_i_right = nums1[i - 1] if i > 0 else float('-inf'), nums1[i] if i < m else float('inf')
             nums_j_left, nums_j_right = nums2[j - 1] if j > 0 else float('-inf'), nums2[j] if j < n else float('inf')

              # case 1: found the right partition:
              if nums_i_left <= nums_j_right and nums_j_left <= nums_i_right:
                 # case 1A: if even number, then calculate the median using two middle numbers:
                  if total % 2 == 0:
                      return (max(nums_i_left, nums_j_left) + min(nums_i_right, nums_j_right)) / 2
                  else:
                      return min(nums_i_right, nums_j_right)

              elif nums_i_left > nums_j_right: # recurse "left"
                 right = i - 1
              else:
                 left = i + 1

Code Snippet 10: Median of Two Sorted Arrays (4)

Pattern Extraction

Core Insight: Binary search on the partition of the shorter array. A valid partition splits both arrays so all left elements $\leq$ all right elements. The median comes from the partition boundary. Pattern Name: Binary Search on Partition (Virtual Merge) Canonical Section: Binary Search > Advanced Conceptual Search Recognition Signals:

Two sorted arrays, find the median without merging
$O(\log(\min(m, n)))$ required
Partition-based reasoning

Anti-Signals:

Arrays are not sorted – sort first
$O(m + n)$ is acceptable – just merge

Decision Point: The $O(\log(\min(m, n)))$ requirement eliminates merging and forces binary search on the partition. One of the hardest binary search problems. Interviewer Comms: “I binary search on where to partition the shorter array. The partition of the longer array is forced by the total left-half size. A valid partition has maxLeft1 < minRight2= and maxLeft2 < minRight1=. The median comes from the max of left elements and min of right elements.”

Pitfalls and Misconceptions

Trap: Binary searching the longer array. Why: Can lead to invalid partitions where the shorter array doesn’t have enough elements. Correction: Always binary search the shorter array: if len(A) > len(B): A, B = B, A.
Trap: Not using sentinels for empty partition sides. Why: When one side of the partition is empty, accessing maxLeft or minRight causes index errors. Correction: Use float('-inf') for empty left, float('inf') for empty right.
Trap: Off-by-one in computing the second array’s partition. Why: If shorter array contributes $i$ to the left, longer must contribute (m+n+1)//2 - i. The +1 handles odd totals. Correction: j = (m + n + 1) // 2 - i.

Problem Mutations

What if you needed the $k$-th element instead of median? (stress-tests: median-specific) Same partition approach but left half size is $k$ instead of $(m+n)/2$.
What if there were $K$ sorted arrays? (stress-tests: two arrays) Merge with a heap in $O(N \log K)$, then index. Or binary search on the value space with counting.
What if the arrays were unsorted? (stress-tests: sorted) Sort first: $O(m \log m + n \log n)$. Or Quickselect on merged for expected $O(m + n)$.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Median of Two Sorted Arrays. Review against personal solving experience.

Lower Bound / UpperBound Variants #

Objective
- Find first or last positions in sorted structures (or insertion points) meeting criteria, handling duplicates or boundaries precisely.

Problems #

Searching in Rotated / Modified Arrays / Circular Structures #

Objective
- Adapt binary search to handle arrays that are rotated, partially sorted, or circularly structured.

Problems #

Search in Rotated Sorted Array (33)

Idea here is to realise that we should be finding out which segment is sorted, then making decisions the right on where to recurse.

It’s not that different from the usual, manual binary search implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   class Solution:
     def search(self, nums: List[int], target: int) -> int:
       """
         We search almost similarly, we just need to identify which segment is the sorted segment and which is the pivoted segment.
         """
       low, high = 0, len(nums) - 1
         while low <= high:
           mid = low + (high - low) // 2
           found_target = nums[mid] == target
             if found_target:
                 return mid

             # determine sorted vs pivoted side:
             if nums[low] <= nums[mid]:
               # within left sement
                 if nums[low] <= target < nums[mid]:
                   high = mid - 1 # recurse left
                 else:
                   low = mid + 1 # recurse right
             else: # is right segment sorted
                 if nums[mid] < target <= nums[high]:  # is target in the right side:
                   low = mid + 1 # recurse right
                 else:
                   high = mid - 1 # recurse left

         return -1

Code Snippet 11: Search in Rotated Sorted Array (33)

Pattern Extraction

Core Insight: At least one half of the array around mid is always properly sorted. Determine which half is sorted, then check if the target falls within that sorted range. If yes, search there; otherwise search the other half. Pattern Name: Modified Binary Search on Rotated Array Canonical Section: Binary Search > Rotated Sorted Array Recognition Signals:

Sorted array that has been rotated at an unknown pivot
$O(\log n)$ search required
No duplicates (LC 33) or with duplicates (LC 81)

Anti-Signals:

Array is simply sorted (not rotated) — standard binary search
Need to find the rotation point, not a target — different problem. Connects to LC 153

Decision Point: The key decision at each step: “which half is sorted?” Check nums[lo] < nums[mid]=. If true, left half is sorted. Then check if target is in [nums[lo], nums[mid]) to decide search direction.

Pitfalls and Misconceptions

Trap: Trying to find the pivot first, then doing standard binary search on the correct half.

Why: Works but requires two binary searches. The single-pass approach is cleaner and equally $O(\log n)$. Correction: At each step, determine which half is sorted and whether the target is in that range.

Trap: Using strict inequality nums[lo] < nums[mid] instead of nums[lo] < nums[mid]=.

Why: When lo = mid= (two-element subarray), the left “half” is a single element and IS sorted. Strict inequality misclassifies this case. Correction: Use nums[lo] < nums[mid]= for the “left half is sorted” check.

Problem Mutations

What if there are duplicates? (stress-tests: uniqueness assumption)

When nums[lo] = nums[mid]==, you can’t determine which half is sorted. Worst case, shrink lo + 1=. Degrades to $O(n)$ worst case. Connects to LC 81.

What if you needed the minimum element instead of a target? (stress-tests: search target type)

Always move toward the unsorted half — the minimum is there. Connects to LC 153 Find Minimum.

What if the array could be rotated at a known pivot? (stress-tests: unknown rotation)

Split into two sorted subarrays at the pivot and binary search each. $O(\log n)$ but trivial.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Search in Rotated Sorted Array generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Find Minimum in Rotated Sorted Array (153)

A rotated array is 2 sorted subarrays, with the minimum being a left-boundary search / pivot point search. Our choice of recursing into which subarray is based on the current window we are looking at so if nums[mid] > nums[right] then the min is to the right of mid and if nums[mid] < nums[right] then the min is at mid or to the left of mid.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    class Solution:
      def findMin(self, nums: List[int]) -> int:
          left, right = 0, len(nums) - 1
          while left < right:
              mid = left + (right - left) // 2
              # then the min must be in the right segment
              if nums[mid] > nums[right]:
                  left = mid + 1
                  # min must be in the left segment
              else:
                  right = mid
          return nums[left]

Code Snippet 12: Find Minimum in Rotated Sorted Array (153)

Pattern Extraction

Core Insight: Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum is in the right half. Otherwise, it’s in the left half (including mid). Pattern Name: Binary Search for Rotation Pivot Canonical Section: Binary Search > Rotated Sorted Array Recognition Signals:

Rotated sorted array, find the minimum
$O(\log n)$ required, no duplicates

Anti-Signals:

Array has duplicates – worst case $O(n)$. Connects to LC 154
Need to search for a target, not the minimum – LC 33

Decision Point: Compare with nums[right], not nums[left]. nums[mid] > nums[right] means minimum is right of mid.

Pitfalls and Misconceptions

Trap: Comparing nums[mid] with nums[left] instead of nums[right]. Why: Comparing with nums[left] is ambiguous when mid = left=. Correction: Use if nums[mid] > nums[right]: left = mid + 1 else: right = mid.
Trap: Using right = mid - 1 instead of right = mid. Why: mid could be the minimum. Skipping it misses the answer. Correction: right = mid (keep mid as candidate).

Problem Mutations

What if there are duplicates? (stress-tests: uniqueness) When nums[mid] = nums[right]=, shrink: right - 1=. Worst case $O(n)$. Connects to LC 154.
What if the array is not rotated? (stress-tests: rotation assumption) Algorithm still works: nums[mid] < nums[right]= always holds, so right converges to 0.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Find Minimum in Rotated Sorted Array. Review against personal solving experience.

⭐️ Find minimum in Rotated Sorted Array II (154)

The key idea is that same as usual binary search: which segment do we confidently recurse into? Turns out that we can compare boundaries with the mid: if right is smaller than mid then the min value must be @ right segment, if right is larger than mid, then the min value must come from the left segment and if it’s equal, then we have to pop out one of the duplicates and carry on.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    class Solution:
     def findMin(self, nums: List[int]) -> int:
         left, right = 0, len(nums) - 1
         ans = float('inf')
         while left < right:
             mid = left + (right - left) // 2
             # can recurse left because left segment is smaller, right is sorted
             if nums[mid] < nums[right]:
                 right = mid
                 # can recurse right because right segment is smaller, min is in the right half, excluding idx = mid
             elif nums[right] < nums[mid]:
                 left = mid + 1
             else: # they are equal
                 # left += 1 # NOTE: can't just remove both, it's going to remove info
                 right -= 1

         return nums[left]

Code Snippet 13: Find minimum in Rotated Sorted Array II (154)

NOTE: the left, right define inclusive ranges above. The while condition having strict inequality is so that we avoid infinite loops (by ensuring that the interval size decreases in each iteration). This is necessary because we may have duplicates which lead to nums[left] = nums[right]=. This means that the while loop terminates when left = right=

Pattern Extraction

Core Insight: Same as LC 153 but duplicates create ambiguity. When nums[mid] = nums[right]=, you can’t determine which half has the minimum. Shrink right - 1= to break the tie. Pattern Name: Binary Search with Duplicate Handling (Worst-Case Linear) Canonical Section: Binary Search > Rotated Sorted Array Recognition Signals:

Rotated sorted array with duplicates
Find minimum
Worst case $O(n)$ but average $O(\log n)$ Anti-Signals:
- No duplicates – standard LC 153 approach, guaranteed $O(\log n)$
Decision Point: The duplicate case (nums[mid] = nums[right]=) is the only difference from LC 153. Everything else is identical.

Pitfalls and Misconceptions

Trap: Not handling the equality case (nums[mid] = nums[right]=). Why: Without this case, the binary search may loop infinitely or skip the minimum. Correction: When nums[mid] = nums[right]: right -= 1=. This safely shrinks the search space by one.
1. Trap: Trying to maintain $O(\log n)$ guarantee.
Why: With all-equal arrays (e.g., [1,1,1,1]), every step only shrinks by 1. $O(n)$ is unavoidable. Correction: Accept $O(n)$ worst case. The average case is still $O(\log n)$.

Problem Mutations

What if you needed to search for a target (not minimum) with duplicates? (stress-tests: search type) Even harder: LC 81. Same right - 1= trick for duplicates but the search logic is more complex.
1. What if you needed to count occurrences of the minimum? (stress-tests: find vs count)
Find minimum first, then linear scan or binary search for first/last occurrence.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Find Minimum in Rotated Sorted Array II. Review against personal solving experience.

Time Based Key Value Store (981)

We just have to keep sorted chained dictionaries (to act as a multiset), so we find the value from within the chain.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   from collections import defaultdict
   from bisect import bisect_right

    class TimeMap:
     def __init__(self):
         self.key_to_vals = defaultdict(list)

     def set(self, key: str, value: str, timestamp: int) -> None:
         self.key_to_vals[key].append((timestamp, value))

     def get(self, key: str, timestamp: int) -> str:
         vals = self.key_to_vals[key]
         if not vals:
             return ""

         idx = bisect_right(vals, timestamp, key=lambda x: x[0])
         if idx == 0:
             return ""

         return vals[idx-1][1]

Code Snippet 14: Time Based Key Value Store (981)

Pattern Extraction

Core Insight: Store values with timestamps in a list per key. For get, binary search (bisect_right) to find the latest value at or before the requested timestamp. Pattern Name: Hash Map + Sorted List with Binary Search Canonical Section: Binary Search > Standard Sorted Array Search Recognition Signals:

Key-value store with temporal versioning
Timestamps monotonically increasing per key
$O(\log n)$ get required

Anti-Signals:

Timestamps can decrease – need balanced BST
Need range queries over timestamps – segment tree

Decision Point: Monotonic timestamps = naturally sorted list per key. Binary search gives $O(\log n)$ floor lookup.

Pitfalls and Misconceptions

Trap: Using bisect_left instead of bisect_right. Why: bisect_right - 1 gives the last element $\leq$ target. bisect_left - 1 gives the last element $<$ target, missing exact matches. Correction: idx = bisect_right(timestamps, ts) - 1.
Trap: Linear scanning timestamps instead of binary searching. Why: $O(n)$ per get. Binary search is $O(\log n)$. Correction: Use bisect module.

Problem Mutations

What if timestamps could decrease? (stress-tests: monotonicity) Need SortedList or balanced BST for $O(\log n)$ insertion and lookup.
What if you needed to delete entries at specific timestamps? (stress-tests: append-only) Lists have $O(n)$ deletion. Need a balanced BST.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Time Based Key-Value Store. Review against personal solving experience.

⭐️ Bitwise / Digit-level Binary Search #

Objective
- Binary search over bits, digits, or sub-ranges within elements to find values or bounds at more granular levels.

Problems #

Single Element in a Sorted Array (540)

The requirement is to do it in $O(log n)$ time, so the bit (XOR) hack won’t work, but might as well just see it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

   # M1: my approach ( doing a scaled index access )
   class Solution:
       def singleNonDuplicate(self, nums: List[int]) -> int:
           n = len(nums)
           uniq = (n + 1) // 2
           left, right = 0, uniq - 1

           while left <= right:
               middle = left + (right - left) // 2
               middle_idx = middle * 2

               # Edge case: if middle_idx is the last index, it must be the answer
               if middle_idx == n - 1:
                   return nums[middle_idx]

               # Safely check neighbors to identify singular element
               left_neighbor_differs = (middle_idx == 0) or (nums[middle_idx] != nums[middle_idx - 1])
               right_neighbor_differs = (middle_idx == n - 1) or (nums[middle_idx] != nums[middle_idx + 1])

               # If both neighbors differ, found the singular element
               if left_neighbor_differs and right_neighbor_differs:
                   return nums[middle_idx]

               # If current pair is broken (does not match next), search left
               if nums[middle_idx] != nums[middle_idx + 1]:
                   right = middle
               else:
                   left = middle + 1

   # M2: parity based binary search:
   class Solution:
       def singleNonDuplicate(self, nums: List[int]) -> int:
           lo, hi = 0, len(nums) - 1
           while lo < hi:
               mid = (lo + hi) // 2
               # Ensure mid is even for easier pairing
               if mid % 2 == 1:
                   mid -= 1
               if nums[mid] == nums[mid + 1]:
                   lo = mid + 2
               else:
                   hi = mid
           return nums[lo]

   # M3: xor trick ( but not acceptable )
   class Solution:
       def singleNonDuplicate(self, nums):
           result = 0
           for num in nums:
               result = result ^ num  # XOR accumulates all numbers
           return result

Code Snippet 15: Single Element in a Sorted Array (540)

Pattern Extraction

Core Insight: Before the single element, pairs align at even-odd indices: nums[2k] = nums[2k+1]=. After it, pairs shift: nums[2k] = nums[2k-1]=. Binary search for the break point. Pattern Name: Binary Search on Pair Alignment Canonical Section: Binary Search > Parity-Based Search Recognition Signals:

Sorted array where every element appears exactly twice except one
$O(\log n)$ required
Pair alignment changes at the singleton

Anti-Signals:

Unsorted array with single unique – XOR all elements (LC 136)
Multiple unique elements – different approach

Decision Point: Sorted + pairs = binary search on pair alignment. Unsorted + pairs = XOR.

Pitfalls and Misconceptions

Trap: Using XOR (which is $O(n)$) instead of exploiting the sorted property. Why: XOR works but doesn’t achieve $O(\log n)$. Correction: Binary search on pair alignment.
Trap: Getting the even/odd check wrong. Why: Need to check if mid is even or odd, then compare with mid+1 or mid-1 to determine which half the singleton is in. Correction: If mid is even: pair is nums[mid] = nums[mid+1]=? If yes, singleton is right. If mid is odd: pair is nums[mid] = nums[mid-1]=?

Problem Mutations

What if the array were unsorted? (stress-tests: sorted) XOR all elements. $O(n)$ time, $O(1)$ space.
What if there were two singletons? (stress-tests: single unique) Binary search on pair alignment doesn’t work (two break points). Use XOR + split technique (LC 260).

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Single Element in a Sorted Array. Review against personal solving experience.

Find the Duplicate Number (287)

Technically there’s the binary search method that exploits the Pigeonhole Principle, but this is inferior because it’s slow:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
   class Solution:
       def findDuplicate(self, nums: List[int]) -> int:
           left, right = 1, len(nums) - 1
           while left < right:
               mid = (left + right) // 2
               count = sum(num <= mid for num in nums)
               if count > mid:
                   right = mid
               else:
                   left = mid + 1
           return left
       # _Why does the binary search work?_
       # The "pigeonhole principle": more numbers ≤ mid than mid itself means the duplicate is in that range.

Code Snippet 16: Find the Duplicate Number (287)

The optimal solution:

Treat the array as a linked list (by going to $nums[i]$ as the next pointer because of the question’s premise), use Floyd’s Tortoise and Hare for Cycle Detection then Duplicate Detection: move the fast pointer until they meet. Then to find entrance, move the slow pointer and the other pointer from the start until they meet again.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
   class Solution:
       def findDuplicate(self, nums: List[int]) -> int:
           # Phase 1: Find intersection
           slow = fast = nums[0]
           while True:
               slow = nums[slow]
               fast = nums[nums[fast]] # double jump
               if slow == fast:
                   break

           # Phase 2: Find entrance to the cycle
           fast = nums[0] # reset to beginning
           while slow != fast:
               slow = nums[slow]
               fast = nums[fast]
           return slow

Code Snippet 17: Find the Duplicate Number (287)

Pattern Extraction

Core Insight: Model as a linked list: nums[i] is the “next pointer” from index $i$. A duplicate means two indices point to the same value, creating a cycle. Floyd’s tortoise and hare finds the cycle entry = the duplicate. Pattern Name: Floyd’s Cycle Detection on Index-as-Pointer Canonical Section: Binary Search > Advanced / Linked List > Cycle Detection (cross-topic) Recognition Signals:

Array of $n+1$ integers in range $[1, n]$
Exactly one duplicate (Pigeonhole)
$O(1)$ space, can’t modify the array
The array defines an implicit linked list via next(i) = nums[i]

Anti-Signals:

Can modify the array – mark visited by negating (simpler)
Can use $O(n)$ space – hash set
Need to find ALL duplicates – different problem. Connects to LC 442

Decision Point: $O(1)$ space + no modification = Floyd’s cycle detection on the implicit linked list. The “linked list” framing is the key insight.

Pitfalls and Misconceptions

Trap: Not seeing the array as an implicit linked list. Why: The connection between “array with duplicates” and “linked list with cycle” is non-obvious. Without this reframing, you reach for hash sets or sorting. Correction: next(i) = nums[i]. Duplicate value = two nodes pointing to same node = cycle entry point.
Trap: Starting the tortoise/hare at index 0 but forgetting to reset for Phase 2. Why: After detection (tortoise meets hare), Phase 2 requires one pointer at the start (index 0) and one at the meeting point, both advancing at speed 1 until they meet at the cycle entry. Correction: Phase 1: detect cycle. Phase 2: reset one pointer to 0, advance both at speed 1.

Problem Mutations

What if there were multiple duplicates? (stress-tests: single duplicate) Floyd’s finds one cycle entry. Multiple duplicates = multiple cycles. Need different approach (hash set, sorting, or marking).
What if the array could be modified? (stress-tests: immutability) Negate values at index abs(nums[i]) to mark visited. If a value is already negative, it’s the duplicate. $O(n)$ time, $O(1)$ space.
What if the range were $[0, n]$ instead of $[1, n]$? (stress-tests: range) Index 0 becomes a valid value, complicating the implicit linked list. Need to offset by 1.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Find the Duplicate Number. Review against personal solving experience.

Binary Search with Custom Predicates / Conditions #

Objective
- Use customized predicate functions defining feasibility or constraints to guide the search for answers in monotonic settings.

TODO Problems #

Aggressive Cows writeup in leeetcode community (placing cows with minimum distance) seems like it’s actually Magnetic Force Between Two Balls (1552)
Painter Partition Problem

SOE #

when we write out the bisect functions manually, we need to realise that the bounds matter (is it open-close or open-open)?
this affects:
1. the while condition’s predicate function
2. how we do the ‘recursion’ / adjustment of left and right boundaries.
For this, my preference is to use inclusive boundaries (closed, closed ranges). It’s more intuitive to use.
Infinite loop (mid calculation)
- this happens when we don’t maintain the invariant that the search space constricts on every iteration of the while loop.
- Off-by-One Errors
  - typically the case on loop boundaries (remember, closed-closed is typically the most intuitive)
    - Closed-Closed: Using right = mid instead of right = mid - 1 causes infinite loops
    - Closed-Open: Using right = mid - 1 instead of right = mid causes missed elements
    - Open-Open: Forgetting to initialize left = -1 causes issues with boundary handling
Wrong boundary updates (low/high) – related to the range being closed, closed or closed, open.
Fallback Response:
- Returning the wrong type / wrong fallback response when returning on failure cases (e.g. returning -1 when asked to return "")

Decision Flow #

Sorted input? -> Classic binary search
Monotonic predicate over an answer space? -> Binary search on answer (BSOA). The search space is implicit, defined by a feasibility function.
First or last occurrence in sorted data? -> Use bisect_left / bisect_right variants
Optimisation problem with monotonic feasibility? -> BSOA with a feasibility checker as the predicate
Matrix search (sorted rows/cols)? -> Treat as flattened sorted array (divmod for index conversion) or staircase search for row+col sorted matrices
Rotated sorted array? -> Modified binary search exploiting the single inflection point

AI usage disclosure Claude Opus 4.6 · content enrichment

Expanded Decision Flow for binary search, adding BSOA, matrix search, and rotated array discrimination. Review and amend.

Styles, Tricks and Boilerplate #

Basic Boilerplates #

precursor handwritten framework and the bisect versions

NOTE: this boiler plate is pure python that doesn’t use the stdlib values. This is just for cases where we are asked to implement it by hand

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
  def binary_search(nums: List[int], target: int) -> int:
      # set left and right indexes (inclusive indices shown here)
      left, right = 0, len(nums) - 1
      while left <= right: # NOTE: the condition here is for an overrun because they are inclusive indices
          mid = left + (right - left) // 2 # NOTE: this avoids overflows in langs like C, Java but Python big integer handling is alright and safe

          if nums[mid] < target:
              left = mid + 1
          elif nums[mid] > target:
              right = mid - 1
          elif nums[mid] == target:
              # found the target value
              return mid
      # target value not found
      return -1

  def left_bound(nums: List[int], target: int) -> int:
      """
      This searches for a left boundary and it also handles the case where we don't have the target in the array.
      """
      # set left and right indexes, both are inclusive indices
      left, right = 0, len(nums) - 1
      while left <= right:
          mid = left + (right - left) // 2
          if nums[mid] < target:
              left = mid + 1
          elif nums[mid] > target:
              right = mid - 1 # because inclusive indices
          elif nums[mid] == target:
              # target exists, narrow the right boundary (since we are searching for the left boundary)
              right = mid - 1
      # determine if the target exists, these are non existing cases:
      if left < 0 or left >= len(nums):
          return -1
      # determine if the left boundary found is the target value
      return left if nums[left] == target else -1

  def right_bound(nums: List[int], target: int) -> int:
      # set left and right indexes
      left, right = 0, len(nums) - 1
      while left <= right:
          mid = left + (right - left) // 2
          if nums[mid] < target:
              left = mid + 1
          elif nums[mid] > target:
              right = mid - 1
          elif nums[mid] == target:
              # target exists, narrow the left boundary because we're still searching for the right boundary
              left = mid + 1
      # determine if the target exists -- these are the out-of-bounds cases to handle.
      if right < 0 or right >= len(nums):
          return -1
      # determine if the right boundary found is the target value
      return right if nums[right] == target else -1

Code Snippet 18: Basic Boilerplates

Alternatively, the same 3 things can be done using python’s bisect module:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  import bisect

  def binary_search(nums: List[int], target: int) -> int:
      # bisect_left to find leftmost occurrence of target
      pos = bisect.bisect_left(nums, target)
      # Verify pos is within range and equals target
      if pos != len(nums) and nums[pos] == target:
          return pos
      return -1

  def left_bound(nums: List[int], target: int) -> int:
      # bisect_left will give leftmost insertion point
      pos = bisect.bisect_left(nums, target)
      if pos != len(nums) and nums[pos] == target:
          return pos
      return -1

  def right_bound(nums: List[int], target: int) -> int:
      # bisect_right will give rightmost insertion point, so right boundary is pos - 1
      pos = bisect.bisect_right(nums, target)
      if pos > 0 and nums[pos - 1] == target:
          return pos - 1
      return -1

Recipes #

Math Recipes on Python: Doing division:
- integer division / floor division: a // b returns an int
- ceiling division: -(-a//b)
  we double negate it, first to carry out a floor division on the negated form, then to negate it back
- normal division: a / b returns a float, preserving the accuracy

Gotchas #

Gotcha: Slicing Inside Hot Loops Has Hidden Cost

see 1482. Minimum Number of Days to Make m Bouquets

When you call all(predicate(d) for d in arr[left:left+k]) inside a loop that increments left by 1, you’re paying O(k) per iteration for slicing and checking, not O(1).

SLOW: $O(n·k)$ per ready() call

      while left + k <= len(arr):
          if all(d <= day for d in arr[left : left + k]):
              # ... match found
              left += k
          else:
              left += 1  # ← Slides by 1, repeats O(k) work

Code Snippet 19: Gotchas

FAST: O(n) per ready() call

      completed, buffer = 0, 0
      for val in arr:
          if val > day:
              buffer = 0
              continue
          buffer += 1
          if buffer == k:
              completed += 1
              buffer = 0

Code Snippet 20: Gotchas

The single-pass approach is O(1) per element, no slicing overhead.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    class Solution:
       def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
           """
​           - looking for numDays which will go from at worst the highest bloomday -- we need to mimise this
​             - low, high = 1, max(bloomDay)
​           - trivial rejection case: when not enough flowers
           """
           # trivial rejection: not enough flowers
           if (m * k) > len(bloomDay):
               return -1

           def ready(day: int) -> bool:
               completed, buffer = 0, 0 # buffer: accums consecutive bloomed flowers
               for bloom in bloomDay:
                   if bloom > day:
                       buffer = 0
                       continue
                   buffer += 1
                   if buffer == k:
                       completed += 1
                       buffer = 0 # reset it
               return completed >= m

           low, high = min(bloomDay), max(bloomDay)
           ans = high
           while low <= high:
               mid = low + (high - low) // 2
               if ready(mid): # can try smaller
                   ans = mid
                   high = mid - 1
               else:
                   low = mid + 1

           return ans

TODO KIV #

[ ] Tough canonical types that haven’t been touched on: #

TODO Pending canonical questions: #

finding min/max satisfying conditions this entire category hasn’t been touched before.
1. TODO Split Array Largest Sum (410)
2. TODO Minimum Speed to Arrive on Time (1870)
Lower bound / upperbound variants This category of lower bound / upper bound variants has NOT been addressed yet.
1. TODO Count of Smaller Numbers After Self (315)
Binary Search with Custom Predicates / Conditions:: Aggressive Cows writeup in leeetcode community (placing cows with minimum distance) seems like it’s actually Magnetic Force Between Two Balls (1552)
This canonical type doesn’t have anything that was done prior to this.
Difficult canonicals:
1. More questions under the searching in implicit / virtual domains
2. More questions under the Bitwise Binary Search

More canonicals to explore #

Search in Infinite or Unknown Length Arrays
- Requires boundary doubling or exponential probing before classic binary search.
- Example: Search in a Sorted Array of Unknown Size (Leetcode 702).
Peak Finding (1D and 2D)
- Find a local maximum in an array/matrix; can use binary search due to monotonic property in neighbors.
- Example: Find Peak Element (Leetcode 162), Find a Peak Element II (Leetcode 1901).
Search in Sparse or Special-Format Arrays
- Adaptation for arrays with lots of nulls/blanks, or unknown spacing between entries.
- Example: Sparse Search (Cracking the Coding Interview, not a standard LeetCode problem).
Square Root, Cube Root Approximations
- Binary search for finding floor/ceiling of root values (for large inputs).
- Example: Sqrt(x) (Leetcode 69).
Binary Search on Continuous Real Intervals
- For precision or geometry problems, apply classic search to floating-point intervals.
- Example: Kth Smallest Prime Fraction (Leetcode 786).
Minimum/Maximum Capacity Without Sorting
- Push the bounds further for ship, chamber, core, etc., capacities required under constraints.
- Example: Minimum Number of Days to Make m Bouquets (Leetcode 1482), Minimum Limit of Balls in a Bag (Leetcode 1760).
Binary Search on Trees/Graphs
- Typical when binary search is used in conjunction with tree structures.
- Example: Closest Binary Search Tree Value II (Leetcode 272).
“K-th Element” by Count
- Binary search the answer, counting by predicate or via other methods.
- Example: Kth Smallest Element in a Sorted Matrix (Leetcode 378).
Median of Stream/Sliding Window
- Median finding with binary search combined with sliding windows and data structures.
- Example: Sliding Window Median (Leetcode 480).

Canonical Questions #

Classic Search over Sorted Array #

Problems #

Search on Answer / Decision Space #

Problems #

Finding Min/Max Satisfying Conditions \(\implies\) usually an Optimisation Problem #

Problems #

⭐️⭐️ Searching in Implicit / Virtual Domains #

Problems #

Lower Bound / UpperBound Variants #

Problems #

Searching in Rotated / Modified Arrays / Circular Structures #

Problems #

⭐️ Bitwise / Digit-level Binary Search #

Problems #

Binary Search with Custom Predicates / Conditions #

TODO Problems #

SOE #

Decision Flow #

Styles, Tricks and Boilerplate #

Basic Boilerplates #

Recipes #

Gotchas #

TODO KIV #

[ ] Tough canonical types that haven’t been touched on: #

TODO Pending canonical questions: #

More canonicals to explore #