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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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​

Solutions:
Visualize
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​

Solutions:
Visualize
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·
Solutions:
Visualize
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