Binary Search
Search value in sorted sequences
Note that the sorted list we search for result can either be the domain or range.
We will need to find the function that gives us the direction.
278. First Bad Version
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
Thought process:
- Linear scan is \(O(N)\).
- The function is a given API call, which the result for a sequential inputs are sroted: FFFFTTTT.
- Use binary search to have \(logN\) search time.
def first_bad_version(n): l, h = 1, n while l < h: m = (l + h) // 2 if isBadVersion(m): h = m else: l = m + 1 return l
1231. Divide Chocolate
You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.
class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def can_divide(target_minimal):
pieces = 0
accum = 0
for amt in sweetness:
accum += amt
if accum >= target_minimal:
accum = 0
pieces += 1
return pieces >= k + 1
l, h = 0, sum(sweetness) // (k + 1) + 1
while l < h:
m = (l + h) // 2
if not can_divide(m):
h = m
else:
l = m + 1
return l - 1
875. Koko Eating Bananas
Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.
Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K such that she can eat all the bananas within H hours.
Thought process:
- Search space is
1, size(max pile)
, a tighter lower bound can beceil(size(min_pile))
- The function is
f(x) = # hour it needs to eat all bananas < H
. - The function space is FFFTTT.
import math
def min_eating_speed(piles, H):
def can_eat_all(speed):
return sum(math.ceil(num_bananas / speed) for num_bananas in piles) <= H
l, h = math.ceil(min(piles) / H), max(piles)
while l < h:
m = (l + h) // 2
if can_eat_all(m):
h = m
else:
l = m + 1
return l
1060. Missing Element in Sorted Array
Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.
- The actual search space is
A[0], A[n - 1]
.- Directly search for the value is a bit difficult, we instead search for a quantity that have a fomularic relationship with the target.
- Notice number of missing integers before idx i is
A[i] - A[0] - i
.- let
A == [4,7,9,10]
,A[1] - A[0] - 1 == 7 - 4 - 1 == 2
and the missing integers before 7 are 5 and 6.- Use binary search to find smallest
i
such that number of missing intgers beforeA[i]
is greater than or equal tok
. FFFFFFTTTTTTT+ Then we can calculate the k th missing element based off that. ```python def missing_element(A, k): def missing(idx): return A[idx] - A[0] - idx
l, h = 0, len(A)
while l < h:
m = (l + h) // 2
if missing(m) >= k: # i >= m -> missing(m) >= k
h = m
else:
l = m + 1
return A[l - 1] + (k - missing(l - 1)) ```
Peak Finding
- Binary search applied to unsorted array to find a local peak.
- This is done by comparing middle point with its adjacent neighbor and cut space in half.
852. Peak Index in a Mountain Array
Let’s call an array A a mountain if the following properties hold:
- A.length >= 3
- There exists some 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].
Thought process:
- The search space is
0, len(A)
. - Sequential less than comparison results are sorted.
A[i - 2] < A[i - 1] < A[i] > A[i + 1] > A[i + 2] A[m] < A[m + 1] --> T A[m] < A[m + 1] --> T A[m] < A[m + 1] --> F A[m] < A[m + 1] --> F
def peak_index_in_mountain_array(A): l, h = 0, len(A) while l < h: m = (l + h) // 2 if A[m] >= A[m + 1]: h = m else: l = m + 1 return l
162. Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Thought process:
- This is exactly the same question as the one above.
def find_peak_element(nums): l, h = 0, len(nums) - 1 while l < h: m = (l + h) // 2 if nums[m] >= nums[m + 1]: h = m else: l = m + 1 return l
1901. Find a Peak Element II
A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom. Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j]. You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell. You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.
def findPeakGrid(mat): l, h = 0, len(mat) - 1 while l < h: m = (l + h) // 2 if max(mat[m]) >= max(mat[m + 1]): h = m else: l = m + 1 return [l, mat[l].index(max(mat[l]))]
Search in Rotated Sorted Array
153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Thought process:
- Compare the mid point with the high point.
nums[m] < nums[h]
means that from m to h, it is sorted, thus the minimal value can only be to the left of it.nums[m] > nums[h]
means the minimal value must in between m and h. Think of the casem -> 7, 0, 1 <- h
def find_min(nums): l, h = 0, len(nums) - 1 while l < h: m = (l + h) // 2 if nums[m] < nums[h]: h = m else: l = m + 1 return nums[l]
154. Find Minimum in Rotated Sorted Array II
Same as above, but the array may contain duplicates.
Thought process:
- Add one line to handle the case of duplicates, decrement the right pointer.
def find_min(nums):
l, h = 0, len(nums)-1
while l < h:
m = (l + h) // 2
if nums[m] == nums[h]: l -= 1
elif nums[m] < nums[h]: h = m
else: l = m + 1
return nums[l]
33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
You are given a target value to search. If found in the array return its index, otherwise return -1.
Thought process:
- If mid pivot number is larger than the left number, the left half is sorted, right half is rotated sorted.
- Numbers in the rotated sorted part is eithe larger than the max from left or smaller than the min from left.
- Thus, if the target is between left and mid numbers, it has to be in the left half.
- Otherwise it has to be in the right half.
- Otherwise, the left half is rotated sorted, the right half is sorted
- Use logic similar to above.
/
/
/
/
/
def search(nums, target):
l, h = 0, len(nums) - 1
while l <= h:
mid = (l + h) // 2
if nums[mid] == target: return mid
if nums[mid] >= nums[l]:
if nums[l] <= target < nums[mid]:
h = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[h]:
l = mid + 1
else:
h = mid - 1
return -1
81. Search in Rotated Sorted Array II
Same as above, difference is return True or False, and there can be duplicated values in the array.
/
__/ ______
/
l h
Thought process:
- Duplicates will hurts only when it happens as illustrated above.
- Simple fix is to add one line to move either left or right pointer to break it.
def search(nums, target):
l, h = 0, len(nums) - 1
while l <= h:
while l < h and nums[l] == nums[h]: l += 1 # only difference
mid = (l + h) // 2
if nums[mid] == target: return True
if nums[l] <= nums[mid]:
if nums[l] <= target < nums[mid]:
h = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[h]:
l = mid + 1
else:
h = mid - 1
return False
Not so obvious ones
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Thought process:
- To find the middle elements of the merged array is equal to find a partition of the two arrays, such that, the left subarrys merged is equal in size to the right subarrys merges.
- For partitions like these, we want one with the minimal value from the two right subarrays to be bigger than the maximuum value from the two left subarrays.
- If we can find such a partition, the median can be calculated with the four elements on the boundary.
def find_median_from_two_sorted_arrays(nums1, nums2):
if len(nums2) < len(nums1):
nums1, nums2 = nums2, nums1
l1, l2 = len(nums1), len(nums2)
half_size = (l1 + l2 + 1) // 2
l, h = 0, len(nums1)
is_even = not ((l1 + l2) % 2)
while l <= h:
p1 = (l + h) // 2
p2 = half_size - p1
max_left_1 = float("-inf") if p1 == 0 else nums1[p1 - 1]
min_right_1 = float("inf") if p1 == l1 else nums1[p1]
max_left_2 = float("-inf") if p2 == 0 else nums2[p2 - 1]
min_right_2 = float("inf") if p2 == l2 else nums2[p2]
max_left, min_right = max(max_left_1, max_left_2), min(min_right_1, min_right_2)
if max_left <= min_right:
return (max_left + min_right) / 2 if is_even else max_left
elif max_left_1 > min_right_2:
h = p1 - 1
elif max_left_2 > min_right_1:
l = p1 + 1
Multiple uses of binary search
34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
Thought process:
- Use binary search twice, once for the left most, once for the right most.
from bisect import bisect_left, bisect_right
def search_range(nums, target):
left = bisect_left(nums, target, 0, len(nums) - 1)
if left == len(nums) or nums[left] != target: return [-1, -1]
right = bisect_right(nums, target, left, len(nums) - 1)
return [left, right] if nums[right] == target else [left, right - 1]
378. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
*Thought process: *
- The search space is the integers between
matrix[0][0]
andmatrix[-1][-1]
- The function
f(x) = {# of elements in matrix smaller than x} < k
. FFFFFFTTTTTTT - For calculating the above function, we can apply binary on each row.
from bisect import bisect_right
def kth_smallest(matrix, k):
l, h = matrix[0][0], matrix[-1][-1]
while l < h:
mid = (l + h) // 2
if sum(bisect_right(row, mid) for row in matrix) >= k:
h = mid
else:
l = mid +1
return l
Combination with other techniques
658. Find K Closest Elements
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Thought process:
- Find the target value via binary search.
- Shrink the length == 2k window around the target with two pointers.
from bisect import bisect_left def find_closest_elements(arr, k, x): if x <= arr[0]: return arr[:k] if x >= arr[-1]: return arr[-k:] n = len(arr) loc = bisect_left(arr, x) l, h = max(0, loc - k), min(n - 1, loc + k) while h - l + 1 > k: if l < 0 or x - arr[l] <= arr[h] - x: h -= 1 elif h > n - 1 or x - arr[l] > arr[h] - x: l += 1 return arr[l: h + 1]
300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Thought process:
- It a famous problem in CS, here for more detail. ```python def length_of_longest_increasing_subsequence(nums): n = len(nums) p = [0] * n m = [0] * (n + 1) max_l = 0 for i, num in enumerate(nums): l, h = 1, max_l while l <= h: mid = (l + h) // 2 if nums[m[mid]] < num: l = mid + 1 else: h = mid - 1
p[i] = m[l - 1]
m[l] = i
max_l = max(max_l, l)
s = [None] * max_l
k = m[max_l]
for i in range(max_l):
s[~i] = nums[k]
k = p[k]
return max_l ```
A shorter solution is as follows, it only returns the length, but not able to reconstruct the full optimal sequence. The tails[i] here is the tail element of the most recent length i increasing subsequence. (TODO: Monotonic Stack?)
from bisect import bisect_left
def length_of_longest_increasing_subsequence(nums):
tails = []
for num in nums:
i = bisect_left(tails, num)
if i == len(tails):
tails.append(num)
else:
tails[i] = num
return len(tails)
Google List
Straight forward
- 34. Find First and Last Position of Element in Sorted Array
Use a function / sub-rounte as criterion
- 410. Split Array Largest Sum
- 1231. Divide Chocolate
- 1618. Maximum Font to Fit a Sentence in a Screen
As sub-routines for other methods
- 354. Russian Doll Envelopes
- 300. Longest Increasing Subsequence
As a method for container type data structure
- 1146. Snapshot Array
- 981. Time Based Key-Value Store
- 528. Random Pick with Weight
Peak Finding
- 852. Peak Index in a Mountain Array
- 162. Find Peak Element
- 1901. Find a Peak Element II
- 302. Smallest Rectangle Enclosing Black Pixels
*Uncategorized
- 4. Median of Two Sorted Arrays