Skip to main content

Secondary Loop BS

Binary search as the inner step of an outer loop. The outer pass walks elements (or rows); for each one we bisect into a sorted structure. Total cost is O(N log M) - the loop times the search.

Bisect Derivatives​

Loop one value, binary-search for its partner (complement, double, or matching boundary).

167. Two Sum II - Input Array Is Sorted​

Medium·
Explanation

The array is already sorted, so instead of an inner linear scan we can binary-search for each element's complement. Fix an outer index i, then look for the value that completes the pair.

The outer loop:

  • For each i, the partner we need is find = target - numbers[i].
  • Because every pair (i, j) is symmetric, we only ever search the suffix to the right of i - the range [i + 1, len(numbers)). This avoids re-finding pairs and keeps each search strictly forward.

The inner search:

  • bisect_left returns the leftmost insertion point for find in that suffix.
  • If that landing index j is in bounds and numbers[j] == find, we found the pair and return the 1-indexed answer [i + 1, j + 1].
Analysis
Time
O(n log n)
  • n = len(numbers). The outer for i loop runs n times, and each iteration calls bisect_left, an O(log n) binary search for the complement.
Space
O(1)
  • Only scalar indices (i, lo, hi, mid) are tracked; no extra structures are built.
FIG. 167 TWO SUM II INPUT ARRAY IS SORTED 2● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
find = target - numbers[i]
j = self.bisect_left(numbers, find, lo=i + 1, hi=len(numbers))
if j < len(numbers) and numbers[j] == find:
return [i + 1, j + 1]
return [-1, -1]

1855. Maximum Distance Between a Pair of Values​

Medium·
2 Approachesclick to switch
Explanation

Both arrays are sorted in descending order, and a valid pair (i, j) needs i <= j with nums1[i] <= nums2[j]. We want to maximize j - i.

The outer loop:

  • For each element a = nums1[i], every nums2[j] that is >= a forms a valid pair. Because nums2 is descending, those valid j form a prefix [0, boundary).

The inner search:

  • bisect_right_rev finds the insertion boundary j for a in the descending nums2 - i.e. how many nums2 values are >= a.
  • The best distance for this i is j - i - 1, and we keep the running maximum.
Analysis
Time
O(M log N)
  • M is the length of nums1, N is the length of nums2.
  • We iterate over nums1 and binary-search nums2 each time, which costs O(log N).
Space
O(1)
  • Only scalar counters are tracked.
FIG. 1855 MAXIMUM DISTANCE BETWEEN A PAIR OF VALUES 1● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_right_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] > target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] >= target:
lo = mid + 1
else:
hi = mid
return lo
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
maxi = 0
for i, a in enumerate(nums1):
j = self.bisect_right_rev(nums2, a)
maxi = max(maxi, j - i - 1)
return maxi

1346. Check If N and Its Double Exist​

Easy·
Explanation

We need a pair where one value is exactly twice another. Sorting the array first lets us binary-search for each element's double.

The outer loop:

  • After arr.sort(), we walk every value num.
  • For each non-zero num, we look for 2 * num in the sorted array using bisect_left. If the landing index is in bounds and holds 2 * num, the pair exists and we return True.

The zero case:

  • 0 is its own double, so a single zero is not enough - we need two of them. We count zeros separately and return True if zeros >= 2.
Analysis
Time
O(2 N log N)
  • N is the length of the array.
  • Sorting is O(N log N), and the loop runs N times with an O(log N) bisect_left call each, another O(N log N) - two same-order passes collapse to 2 N log N.
Space
O(sort)
  • zeros and index are scalars; the only space beyond the input is the sort's own working memory.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 1346 CHECK IF N AND ITS DOUBLE EXIST● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def checkIfExist(self, arr: List[int]) -> bool:
arr.sort()
zeros = 0
for num in arr:
if num == 0:
zeros += 1
else:
index = self.bisect_left(arr, 2 * num)
if index < len(arr) and arr[index] == 2 * num:
return True
return zeros >= 2

Bisect Derivatives in a 2D Matrix​

Each row is independently sorted, so bisect row by row.

1351. Count Negative Numbers in a Sorted Matrix​

Easy·
Explanation

Each row is sorted in descending order, so within a row all the negatives sit in a contiguous suffix. The job per row is to find where that negative suffix begins.

The per-row search:

  • bisect_right_rev(grid[row], 0) returns the boundary index where 0 is supposed to be inserted in the descending row - equivalently, the first index where negatives start.
  • It works even when 0 is absent: the boundary still lands exactly where the non-negative prefix ends.

Counting:

  • The number of negatives in the row is len(grid[row]) - index. Summing this over all rows gives the total.
Analysis
Time
O(N log M)
  • N is the number of rows, M is the number of columns.
  • Each row gets one O(log M) binary search, repeated N times.
Space
O(1)
  • Only a running counter is tracked.
FIG. 1351 COUNT NEGATIVE NUMBERS IN A SORTED MATRIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_right_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] > target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] >= target:
lo = mid + 1
else:
hi = mid
return lo
def countNegatives(self, grid: List[List[int]]) -> int:
negatives = 0
for row in range(len(grid)):
index = self.bisect_right_rev(grid[row], 0)
print(index, grid[row])
negatives += len(grid[row]) - index
return negatives

1337. The K Weakest Rows in a Matrix​

Easy·
Explanation

Every row is 1s followed by 0s, so a row's strength is just its count of 1s. The "weakest" rows are those with the fewest soldiers, breaking ties by smaller index.

Counting soldiers per row:

  • The 1s form a descending block (then 0s), so bisect_left_rev(mat[row], 0) returns the boundary where 0 begins - exactly the number of 1s in that row.

Keeping only K:

  • Python only has a min-heap, so we push (-soldiers, -row) to simulate a max-heap of strength.
  • Whenever the heap exceeds k, we pop the strongest entry, leaving the k weakest behind.
  • Finally we drain the heap, flip the indices back to positive, and reverse so the result is ordered from weakest to strongest.
Analysis
Time
O(N log(M·K))
  • N is the number of rows, M is the number of columns.
  • Each row costs O(log M) to count soldiers and O(log K) for the heap operation, giving N·(log M + log K) = O(N log(M·K)).
Space
O(K)
  • The heap holds at most k entries at any time.
FIG. 1337 THE K WEAKEST ROWS IN A MATRIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
max_heap = []
for row in range(len(mat)):
soldiers = self.bisect_left_rev(mat[row], 0)
# Put the strength/index pairs into a priority queue.
entry = (-soldiers, -row)
heapq.heappush(max_heap, entry)
if len(max_heap) > k:
heapq.heappop(max_heap)
ans = []
# Pull out and return the indexes of the smallest k entries.
# Don't forget to convert them back to positive numbers!
while max_heap:
ans.append(-heapq.heappop(max_heap)[1])
return ans[::-1] # Reverse, as the indexes are around the wrong way.

Intersection​

Iterate the first array (or row), and binary-search every other one for the same value.

349. Intersection of Two Arrays​

Easy·
Explanation

The intersection is the set of values that appear in both arrays. Sort both, then walk the first array and binary-search each value in the second - a hit means the value belongs to the result.

The setup:

  • Sort nums1 and nums2. Sorting both is O(N log N); it lets us binary-search the second array and skip duplicates in the first cheaply.
  • Iterate nums1 in order. Because it is sorted, every duplicate value sits next to its twin, so a single prev guard collapses repeats - each distinct value is processed once.

The lookup:

  • For each num, bisect_left(nums2, num) returns the leftmost insert position.
  • If that index is in range and nums2[index] == num, the value is present in both arrays, so append it to ans.

The prev check is what keeps the output a true set: without it, a repeated value in nums1 would be added multiple times.

Analysis
Time
O(N log N + M log M + N log M)
  • N is the length of nums1, M is the length of nums2.
  • nums1.sort() costs O(N log N).
  • nums2.sort() costs O(M log M).
  • The loop then walks the N values of nums1 and binary-searches nums2 (log M per bisect_left call) for each - N log M.
Space
O(sort)
  • Beyond the sort's working memory, only the result list and a prev scalar are kept.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 349 INTERSECTION OF TWO ARRAYS● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
ans = []
prev = None
for num in nums1:
if num == prev:
continue
index = self.bisect_left(nums2, num)
if index < len(nums2) and nums2[index] == num:
ans.append(num)
prev = num
return ans

350. Intersection of Two Arrays II​

Easy·
Explanation

This is the multiset version of the intersection: a value that appears twice in both arrays should appear twice in the result. So instead of skipping duplicates, we consume each match from the second array.

The setup:

  • Sort nums1 and nums2 so binary search applies. Sorting is O(N log N).
  • Iterate every value of nums1 (no prev guard this time - repeats are intentional).

The lookup and consume:

  • bisect_left(nums2, num) finds the leftmost insert position.
  • If that index is in range and nums2[index] == num, append num to ans and pop it out of nums2. Removing the matched element means a later duplicate in nums1 can only match a still-unused element, giving correct multiplicities.

Cost note:

  • The pop(index) shifts the tail of nums2, which is O(M) per match - so the worst case degrades to O(N*M) even though each lookup itself is logarithmic.
Analysis
Time
O(n log n + m log m + n*m)
  • nums1.sort() and nums2.sort() cost O(n log n) and O(m log m), where n = len(nums1) and m = len(nums2).
  • The for num in nums1 loop runs n times; each iteration calls bisect_left (O(log m)) and, on a match, nums2.pop(index), which shifts the tail of nums2 in O(m). In the worst case every iteration matches, so the loop costs O(n*m) (the O(log m) bisect is dominated by the O(m) pop within the same iteration).
Space
O(sort + m)
  • ans holds at most min(n, m) matched values, bounded by O(m).
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 350 INTERSECTION OF TWO ARRAYS II● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
ans = []
for num in nums1:
index = self.bisect_left(nums2, num)
print(index, nums2)
if 0 <= index < len(nums2) and nums2[index] == num:
nums2.pop(index)
ans.append(num)
return ans

1198. Find Smallest Common Element in All Rows​

Medium·
Explanation

Each row is sorted ascending, so the candidates for "smallest common element" are exactly the values of the first row, taken in increasing order. The first one that exists in every other row is the answer.

The outer scan:

  • Walk mat[0] left to right. Since it is sorted, the first value confirmed in all rows is automatically the smallest common element.

The inner probe:

  • For each candidate num, binary-search it in every other row with bisect_left(mat[row], num).
  • A row "contains" num when the returned index is in range and mat[row][index] == num. The moment a row misses, set found = False and break - no point checking the rest.

Result:

  • If a candidate clears all rows, return it immediately. If the first row is exhausted with no winner, return -1.
Analysis
Time
O(N*M log M)
  • N is the number of rows, M is the number of columns.
  • For each of the M first-row candidates, we binary-search (log M) across the other N rows.
Space
O(1)
  • Only scalar bookkeeping (num, found, index) is used.
FIG. 1198 FIND SMALLEST COMMON ELEMENT IN ALL ROWS● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def smallestCommonElement(self, mat: List[List[int]]) -> int:
for num in mat[0]:
found = True
for row in range(1, len(mat)):
index = self.bisect_left(mat[row], num)
if not (index < len(mat[row]) and mat[row][index] == num):
found = False
break
if found:
return num
return -1

1213. Intersection of Three Sorted Arrays​

Easy·
Explanation

This is the list-returning sibling of "smallest common element". Stack the three sorted arrays as rows of a matrix, then collect every value of the first row that also appears in the other two.

The setup:

  • Group the inputs as mat = [arr1, arr2, arr3]. The first row (arr1) supplies the ordered candidate stream; since it is sorted, the collected answers come out sorted for free.

The inner probe:

  • For each candidate num, binary-search it in every other row with bisect_left(mat[row], num).
  • A row contains num when the index is in range and mat[row][index] == num. The first miss flips found = False and breaks out early.

Result:

  • Unlike 1198, we don't stop at the first hit - every candidate that survives all rows is appended to ans, which is returned at the end.
Analysis
Time
O(N*M log M)
  • N is the number of arrays (here 3), M is the length of the longest.
  • For each of the M candidates from the first array, we binary-search (log M) across the other arrays.
Space
O(1)
  • Ignoring the output list, only scalar bookkeeping is used.
FIG. 1213 INTERSECTION OF THREE SORTED ARRAYS● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def arraysIntersection(
self, arr1: List[int], arr2: List[int], arr3: List[int]
) -> List[int]:
mat = [arr1, arr2, arr3]
ans = []
for num in mat[0]:
found = True
for row in range(1, len(mat)):
index = self.bisect_left(mat[row], num)
if not (index < len(mat[row]) and mat[row][index] == num):
found = False
break
if found:
ans.append(num)
return ans

Custom Bisect​

When the input is an opaque interface, hand-roll the bisect against its accessor.

1428. Leftmost Column with at Least a One​

Medium·
Explanation

Each row of the binary matrix is sorted - all the 0s come before all the 1s. So within a row, the leftmost 1 is exactly a lower-bound of the value 1, which a standard binary search finds in O(log M).

Per-row bisect:

  • A nested bisect_left(row) runs the lower-bound template against the row, reading cells lazily through binaryMatrix.get(row, mid). It returns the first column whose value is >= 1, i.e. the first 1.

The shrinking horizon:

  • We track mini, the best (smallest) column seen so far. For a new row, there is no reason to look past mini - any 1 further right cannot improve the answer. The probe is therefore bounded by the running minimum, which keeps the total work near O(N log M).
  • A quick guard binaryMatrix.get(row, n - 1) != 0 skips all-zero rows before bisecting.

Result:

  • Return the smallest column that ever held a 1, or -1 if no row contained one.
Analysis
Time
O(N log M)
  • N is the total number of rows, M is the total number of columns.
  • Each row triggers one binary search over its columns, costing log M.
Space
O(1)
  • Only scalar trackers (mini, first_one, loop indices) are used.
FIG. 1428 LEFTMOST COLUMN WITH AT LEAST A ONE● INTERACTIVE
visualization loads as you reach it
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
def bisect_left(row):
lo, hi = 0, n - 1
target = 1
while lo < hi:
mid = lo + (hi - lo) // 2
if binaryMatrix.get(row, mid) < target:
lo = mid + 1
else:
hi = mid
return lo
 
m, n = binaryMatrix.dimensions()
mini = n
for row in range(m):
if binaryMatrix.get(row, n - 1) != 0:
first_one = bisect_left(row)
mini = min(mini, first_one)
return mini if mini != n else -1