7 notes tagged
The "binary search on the answer" pattern explained: when the answer space has a monotone yes/no predicate, binary-search the answer itself. With a re...
Find the Smallest Divisor Given a Threshold (LeetCode 1283): binary search the divisor using ceiling-division sums, O(n log max).
Allocate Minimum Number of Pages: binary search the minimum possible maximum pages per student with a greedy allocation check, O(n log sum).
Aggressive Cows: binary search the largest minimum distance between cows placed in stalls, with a greedy feasibility check, O(n log range).
Split Array Largest Sum (LeetCode 410): binary search the largest subarray sum with a greedy split check, O(n log sum).
Capacity To Ship Packages Within D Days (LeetCode 1011): binary search the ship capacity with a greedy feasibility check, O(n log sum).
Koko Eating Bananas (LeetCode 875): binary search on the eating speed, checking feasibility in O(n log maxPile).