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·

167Two Sum II - Input Array Is Sorted

3 Approaches · 3 patterns

Converging Pointers↗ Two Pointers

O(N) timeO(1) aux

Lookup Before Insert↗ Hash & Set

O(N) timeO(N) aux

Complement by Bisect

O(N log N) timeO(1) aux

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·

1855Maximum Distance Between a Pair of Values

2 Approaches

Without Reversing

O(M log N) timeO(1) aux

By Reversing

O(N + M log N) timeO(1) aux

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·

1346Check If N and Its Double Exist

Sort then Bisect the Double

O(2 N log N) timeO(sort) aux

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

---

300. Longest Increasing Subsequence

Medium·

300Longest Increasing Subsequence

4 Approaches · 2 patterns

LRU Cache↗ Dynamic Programming

O(n^2) timeO(3n) aux

Memoization↗ Dynamic Programming

O(n^2) timeO(2n) aux

Tabulation, O(n) Space↗ Dynamic Programming

O(n^2) timeO(n) aux

Binary Search, O(n log n)

O(n log n) timeO(n) aux

FIG. 300 LONGEST INCREASING SUBSEQUENCE BISECT● INTERACTIVE

visualization loads as you reach it

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

sub = [nums[0]]

for num in nums[1:]:

if num > sub[-1]:

sub.append(num)

else:

ind = bisect.bisect_left(sub, num)

sub[ind] = num

return len(sub)

---

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·

1351Count Negative Numbers in a Sorted Matrix

Per-Row Boundary by Bisect

O(N log M) timeO(1) aux

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·

1337The K Weakest Rows in a Matrix

Count Soldiers, Keep K with a Heap

O(N log(M*K)) timeO(2K) aux

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·

349Intersection of Two Arrays

Bisect Each Element

O(N log N + M log M + N log M) timeO(sort) aux

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·

350Intersection of Two Arrays II

Bisect and Consume

O(N log N + m log m + N*m) timeO(sort) aux

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·

1198Find Smallest Common Element in All Rows

Probe Every Other Row

O(N*M log M) timeO(1) aux

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·

1213Intersection of Three Sorted Arrays

Probe Every Other Array

O(2M log M) timeO(1) aux

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·

1428Leftmost Column with at Least a One

Custom Bisect per Row

O(N log M) timeO(1) aux

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

---