1. Binary Search
Easy · LC 704
Given a sorted array of integers and a target, return the index of the target or -1 if absent. Maintain lo and hi pointers, compute the middle index, and discard the half that cannot contain the target until the pointers cross. The classic pitfall is boundary handling: with an inclusive hi, loop while lo <= hi and move hi to mid - 1, which guarantees termination in O(log n).
def binary_search(nums: list[int], target: int) -> int:
"""LC 704. Binary Search.
The classic: inclusive lo/hi pointers, loop while lo <= hi, and
discard the half that cannot contain the target. The inclusive hi
pairs with hi = mid - 1; mixing in an exclusive update is the
textbook infinite-loop pitfall. O(log n) time, O(1) space.
"""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1 # hi is inclusive, so mid itself must be excluded
return -1
// LC 704. Classic inclusive-bounds search: loop while lo <= hi, discard the
// half that cannot contain the target, and move hi to mid - 1 on the way down.
int binarySearch(vector<int> nums, int target) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
/// LC 704. The classic: inclusive hi pointer, loop while lo <= hi, and
/// discard the half that cannot hold the target. i32 indices sidestep the
/// usize underflow when hi moves to mid - 1 at mid == 0.
pub fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
let (mut lo, mut hi) = (0i32, nums.len() as i32 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
if nums[mid as usize] == target {
return mid;
} else if nums[mid as usize] < target {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
-1
}
/** LC 704. Inclusive bounds: loop while lo <= hi, discard the dead half. */
export function binarySearch(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// LC 704. Classic inclusive-bounds search: loop while lo <= hi, discard the
// half that cannot contain the target, and move hi to mid - 1 on the way down.
func binarySearch(nums []int, target int) int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}
// LC 704. Classic inclusive-bounds search: loop while lo <= hi, discard the
// half that cannot contain the target, and move hi to mid - 1 on the way down.
func binarySearch(_ nums: [Int], _ target: Int) -> Int {
var lo = 0, hi = nums.count - 1
while lo <= hi {
let mid = lo + (hi - lo) / 2
if nums[mid] == target { return mid }
if nums[mid] < target { lo = mid + 1 } else { hi = mid - 1 }
}
return -1
}
2. Search Insert Position
Easy · LC 35
Given a sorted array of distinct integers and a target, return the index of the target or the index where it would be inserted to keep order. Binary search with lo at 0 and hi at the array length, shrinking toward the first element greater than or equal to the target, and return lo. This is exactly lower_bound: the invariant is that everything left of lo is strictly less than the target.
def search_insert(nums: list[int], target: int) -> int:
"""LC 35. Search Insert Position.
Exactly lower_bound: hi starts at len(nums) (one past the end is a
legal insertion spot) and the invariant is that everything left of
lo is strictly less than the target. When the pointers meet, lo is
the target's index or its insertion point. O(log n) time, O(1)
space.
"""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid # nums[mid] >= target: mid stays a candidate slot
return lo
// LC 35. lower_bound: the invariant is that everything left of lo is strictly
// less than the target, so lo lands on the first element >= target.
int searchInsert(vector<int> nums, int target) {
int lo = 0, hi = static_cast<int>(nums.size());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
/// LC 35. Exactly lower_bound: hi starts at len (one past the end), the loop
/// closes in on the first element >= target, and lo is the answer whether or
/// not the target is present.
pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
let (mut lo, mut hi) = (0usize, nums.len());
while lo < hi {
let mid = (lo + hi) / 2;
// Everything left of lo stays strictly less than the target.
if nums[mid] < target {
lo = mid + 1;
} else {
hi = mid;
}
}
lo as i32
}
/** LC 35. lower_bound: everything left of lo stays strictly less than target. */
export function searchInsert(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length; // exclusive hi lets lo land one past the end
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// LC 35. lower_bound: the invariant is that everything left of lo is strictly
// less than the target, so lo lands on the first element >= target.
func searchInsert(nums []int, target int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
// LC 35. lower_bound: the invariant is that everything left of lo is strictly
// less than the target, so lo lands on the first element >= target.
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
var lo = 0, hi = nums.count
while lo < hi {
let mid = lo + (hi - lo) / 2
if nums[mid] < target { lo = mid + 1 } else { hi = mid }
}
return lo
}
3. Guess Number Higher Or Lower
Easy · LC 374
An integer between 1 and n was picked, and the guess API reports whether a query is too high, too low, or correct; return the picked number. Binary search the range 1 to n, calling the API at each midpoint and keeping the half it points to. The predicate comes from the API instead of an array, and computing the midpoint as lo + (hi - lo) / 2 avoids integer overflow.
def guess_number(n: int, pick: int) -> int:
"""LC 374. Guess Number Higher or Lower.
Binary search 1..n where the predicate comes from the guess API
instead of an array: each verdict names the surviving half. The
midpoint is computed as lo + (hi - lo) // 2, the overflow-safe form
the judge expects in fixed-width languages. O(log n) time, O(1)
space.
"""
def guess(num: int) -> int:
# Simulates the hidden judge: -1 too high, 1 too low, 0 correct.
if num > pick:
return -1
if num < pick:
return 1
return 0
lo, hi = 1, n
while True: # the pick is guaranteed in range, so 0 always arrives
mid = lo + (hi - lo) // 2
verdict = guess(mid)
if verdict == 0:
return mid
if verdict == -1:
hi = mid - 1
else:
lo = mid + 1
// LC 374. The predicate comes from the guess API instead of an array; a
// lambda simulates the judge against the known pick.
int guessNumber(int n, int pick) {
// -1: query too high, 1: query too low, 0: correct (LeetCode's contract).
auto guess = [pick](int query) { return query > pick ? -1 : query < pick ? 1 : 0; };
int lo = 1, hi = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids overflow when hi is INT_MAX
int verdict = guess(mid);
if (verdict == 0) return mid;
if (verdict < 0) hi = mid - 1;
else lo = mid + 1;
}
return -1; // unreachable: the pick is always within [1, n]
}
/// LC 374. Binary search 1..=n where the predicate comes from the judge's
/// API instead of an array; a closure stands in for that API here. The pick
/// is guaranteed in range, so the loop always terminates at it.
pub fn guess_number(n: i32, pick: i32) -> i32 {
// The real API: -1 means the guess is too high, 1 too low, 0 correct.
let guess = |num: i32| (pick - num).signum();
let (mut lo, mut hi) = (1, n);
loop {
let mid = lo + (hi - lo) / 2; // midpoint form that cannot overflow
match guess(mid) {
0 => return mid,
1 => lo = mid + 1,
_ => hi = mid - 1,
}
}
}
/** LC 374. The predicate comes from the API; keep the half it points to. */
export function guessNumber(n: number, pick: number): number {
// simulated judge API: -1 the guess is too high, 1 too low, 0 correct
const guess = (num: number): number => (num > pick ? -1 : num < pick ? 1 : 0);
let lo = 1;
let hi = n;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // lo + (hi - lo) / 2: the overflow-proof form
const verdict = guess(mid);
if (verdict === 0) return mid;
if (verdict === -1) hi = mid - 1;
else lo = mid + 1;
}
return -1; // unreachable: pick is always in [1, n]
}
// LC 374. The predicate comes from the guess API instead of an array; a
// closure simulates the judge against the known pick.
func guessNumber(n int, pick int) int {
// -1: query too high, 1: query too low, 0: correct (LeetCode's contract).
guess := func(query int) int {
if query > pick {
return -1
}
if query < pick {
return 1
}
return 0
}
lo, hi := 1, n
for lo <= hi {
mid := lo + (hi-lo)/2 // avoids overflow when hi is the int32 max
verdict := guess(mid)
if verdict == 0 {
return mid
}
if verdict < 0 {
hi = mid - 1
} else {
lo = mid + 1
}
}
return -1 // unreachable: the pick is always within [1, n]
}
// LC 374. The predicate comes from the guess API instead of an array; a
// nested function simulates the judge against the known pick.
func guessNumber(_ n: Int, _ pick: Int) -> Int {
// -1: query too high, 1: query too low, 0: correct (LeetCode's contract).
func guess(_ query: Int) -> Int { return query > pick ? -1 : (query < pick ? 1 : 0) }
var lo = 1, hi = n
while lo <= hi {
let mid = lo + (hi - lo) / 2 // the overflow-safe form fixed-width judges expect
let verdict = guess(mid)
if verdict == 0 { return mid }
if verdict < 0 { hi = mid - 1 } else { lo = mid + 1 }
}
return -1 // unreachable: the pick is always within [1, n]
}
4. Sqrt(x)
Easy · LC 69
Given a non-negative integer x, return the integer square root, meaning the largest k with k*k <= x, truncating any decimal part. Binary search k over 0 to x, squaring the midpoint and keeping the highest value that does not exceed x. Frame it as the last k satisfying k*k <= x rather than the first failure, and compare via k <= x / k or use 64-bit math so the square never overflows.
def my_sqrt(x: int) -> int:
"""LC 69. Sqrt(x).
Binary search for the LAST k satisfying k*k <= x rather than the
first failure: record every feasible midpoint before probing
higher. Python ints never overflow, but the frame mirrors the
64-bit-safe version. O(log x) time, O(1) space.
"""
lo, hi = 0, x
floor_root = 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
floor_root = mid # feasible; only a larger k can beat it
lo = mid + 1
else:
hi = mid - 1
return floor_root
// LC 69. Largest k with k*k <= x; 64-bit math keeps the square from
// overflowing near INT_MAX.
int mySqrt(int x) {
long long lo = 0, hi = x;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (mid * mid <= x) lo = mid + 1;
else hi = mid - 1;
}
return static_cast<int>(hi); // hi settles on the last k whose square fits
}
/// LC 69. Search for the LAST k with k*k <= x rather than the first failure:
/// bias mid upward so lo = mid still makes progress, and square in u64 so
/// mid * mid can never overflow.
pub fn my_sqrt(x: i32) -> i32 {
let x = x as u64;
let (mut lo, mut hi) = (0u64, x);
while lo < hi {
// +1 bias: without it, lo = mid loops forever once hi = lo + 1.
let mid = (lo + hi + 1) / 2;
if mid * mid <= x {
lo = mid;
} else {
hi = mid - 1;
}
}
lo as u64 as i32
}
/** LC 69. Last k with k*k <= x; hi lands on it when the loop exits. */
export function mySqrt(x: number): number {
let lo = 0;
// sqrt(2^31 - 1) < 65536, so capping hi keeps mid * mid inside safe integers
let hi = Math.min(x, 65536);
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid <= x) lo = mid + 1; // mid still fits: the answer is mid or larger
else hi = mid - 1;
}
return hi;
}
// LC 69. Largest k with k*k <= x; Go's 64-bit int keeps the square from
// overflowing near the int32 max.
func mySqrt(x int) int {
lo, hi := 0, x
for lo <= hi {
mid := lo + (hi-lo)/2
if mid*mid <= x {
lo = mid + 1
} else {
hi = mid - 1
}
}
return hi // hi settles on the last k whose square fits
}
// LC 69. Largest k with k*k <= x; hi settles on the last k whose square fits.
// Swift's 64-bit Int keeps mid * mid safe near Int32.max.
func mySqrt(_ x: Int) -> Int {
var lo = 0, hi = x
while lo <= hi {
let mid = lo + (hi - lo) / 2
if mid * mid <= x { lo = mid + 1 } else { hi = mid - 1 }
}
return hi
}
5. Search a 2D Matrix
Medium · LC 74
Given an m x n matrix where each row is sorted and the first element of each row exceeds the last of the previous row, determine whether a target exists. Run one binary search over indexes 0 to m*n - 1, mapping each index to matrix[idx / n][idx % n]. The grid is one sorted array in disguise, so row and column come from a single division and modulo, giving O(log(mn)).
def search_matrix(matrix: list[list[int]], target: int) -> bool:
"""LC 74. Search a 2D Matrix.
The grid is one sorted array in disguise: binary search flat
indices 0..rows*cols - 1 and map each back to a cell with a single
division and modulo. O(log(rows * cols)) time, O(1) space.
"""
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
// LC 74. The grid is one sorted array in disguise: one binary search over
// [0, rows*cols), mapping each index via a single division and modulo.
bool searchMatrix(vector<vector<int>> matrix, int target) {
int rows = static_cast<int>(matrix.size());
int cols = static_cast<int>(matrix[0].size());
int lo = 0, hi = rows * cols - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
/// LC 74. The row-sorted grid is one sorted array in disguise: binary search
/// indexes 0..m*n and map each index back with one division and one modulo,
/// for O(log(mn)) total.
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let cols = matrix[0].len();
let (mut lo, mut hi) = (0i32, (matrix.len() * cols) as i32 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let value = matrix[mid as usize / cols][mid as usize % cols];
if value == target {
return true;
} else if value < target {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
false
}
/** LC 74. The grid is one sorted array: idx maps to [idx / cols][idx % cols]. */
export function searchMatrix(matrix: number[][], target: number): boolean {
const cols = matrix[0].length;
let lo = 0;
let hi = matrix.length * cols - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const value = matrix[Math.floor(mid / cols)][mid % cols];
if (value === target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
// LC 74. The grid is one sorted array in disguise: one binary search over
// [0, rows*cols), mapping each index via a single division and modulo.
func searchMatrix(matrix [][]int, target int) bool {
rows, cols := len(matrix), len(matrix[0])
lo, hi := 0, rows*cols-1
for lo <= hi {
mid := lo + (hi-lo)/2
value := matrix[mid/cols][mid%cols]
if value == target {
return true
}
if value < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return false
}
// LC 74. The grid is one sorted array in disguise: one binary search over
// [0, rows*cols), mapping each index via a single division and modulo.
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let rows = matrix.count, cols = matrix[0].count
var lo = 0, hi = rows * cols - 1
while lo <= hi {
let mid = lo + (hi - lo) / 2
let value = matrix[mid / cols][mid % cols]
if value == target { return true }
if value < target { lo = mid + 1 } else { hi = mid - 1 }
}
return false
}
6. Koko Eating Bananas
Medium · LC 875
Given banana pile sizes and a deadline of h hours, find the minimum integer eating speed k where each pile takes ceil(pile / k) hours and the total must not exceed h. Binary search k from 1 to the largest pile, summing hours at each candidate and keeping the smallest feasible speed. The search runs over the answer space, not the array; hours decrease monotonically as k grows, so feasibility forms a clean boundary.
def min_eating_speed(piles: list[int], h: int) -> int:
"""LC 875. Koko Eating Bananas.
Binary search the ANSWER space, speeds 1..max(piles), not the
array: hours spent fall monotonically as speed grows, so
feasibility forms a clean boundary and the search converges on the
smallest speed that finishes within h hours. O(n log max(piles))
time, O(1) space.
"""
def hours_needed(speed: int) -> int:
# ceil(pile / speed) without floats: (pile + speed - 1) // speed.
return sum((pile + speed - 1) // speed for pile in piles)
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if hours_needed(mid) <= h:
hi = mid # mid works, so it must stay a candidate
else:
lo = mid + 1
return lo
// LC 875. Binary search the answer space [1, max pile]: hours needed shrink
// monotonically as speed grows, so feasibility forms a clean boundary.
int minEatingSpeed(vector<int> piles, int h) {
auto hoursAt = [&piles](int speed) {
long long hours = 0;
// 1LL keeps pile + speed - 1 in 64 bits (both can be near 1e9).
for (int pile : piles) hours += (pile + speed - 1LL) / speed;
return hours;
};
int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (hoursAt(mid) <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}
/// LC 875. Binary search the ANSWER space: speeds from 1 to the largest
/// pile. Total hours decrease monotonically as speed grows, so feasibility
/// (hours <= h) forms a clean boundary; keep the smallest feasible speed.
pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
let (mut lo, mut hi) = (1i64, *piles.iter().max().unwrap() as i64);
while lo < hi {
let speed = (lo + hi) / 2;
// ceil(pile / speed) without floats: (pile + speed - 1) / speed.
let hours: i64 = piles.iter().map(|&pile| (pile as i64 + speed - 1) / speed).sum();
if hours <= h as i64 {
hi = speed;
} else {
lo = speed + 1;
}
}
lo as i32
}
/** LC 875. Binary search the answer space 1..max(pile); hours fall as k grows. */
export function minEatingSpeed(piles: number[], h: number): number {
let lo = 1;
let hi = Math.max(...piles);
while (lo < hi) {
const speed = (lo + hi) >> 1;
let hours = 0;
for (const pile of piles) hours += Math.ceil(pile / speed);
if (hours <= h) hi = speed; // feasible: a slower speed might still work
else lo = speed + 1;
}
return lo;
}
// LC 875. Binary search the answer space [1, max pile]: hours needed shrink
// monotonically as speed grows, so feasibility forms a clean boundary.
func minEatingSpeed(piles []int, h int) int {
hoursAt := func(speed int) int {
hours := 0
// ceil(pile / speed) without floats: (pile + speed - 1) / speed.
for _, pile := range piles {
hours += (pile + speed - 1) / speed
}
return hours
}
lo, hi := 1, piles[0]
for _, pile := range piles {
if pile > hi {
hi = pile
}
}
for lo < hi {
mid := lo + (hi-lo)/2
if hoursAt(mid) <= h {
hi = mid // mid works, so it must stay a candidate
} else {
lo = mid + 1
}
}
return lo
}
// LC 875. Binary search the answer space [1, max pile]: hours needed shrink
// monotonically as speed grows, so feasibility forms a clean boundary.
func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
func hoursAt(_ speed: Int) -> Int {
// ceil(pile / speed) without floats: (pile + speed - 1) / speed.
return piles.reduce(0) { $0 + ($1 + speed - 1) / speed }
}
var lo = 1, hi = piles.max()!
while lo < hi {
let mid = lo + (hi - lo) / 2
if hoursAt(mid) <= h { hi = mid } else { lo = mid + 1 }
}
return lo
}
7. Capacity to Ship Packages Within D Days
Medium · LC 1011
Given package weights shipped in order and a limit of d days, find the minimum ship capacity that delivers everything on time. Binary search capacity between the heaviest package and the total weight, and for each candidate greedily fill days, starting a new day whenever the next package would overflow. The greedy check is valid because packages cannot be reordered, and the lower bound matters: capacity below the heaviest package can never ship it.
def ship_within_days(weights: list[int], days: int) -> int:
"""LC 1011. Capacity to Ship Packages Within D Days.
Binary search capacity between the heaviest package (anything
lighter can never ship it) and the total weight (one day ships
everything). Each candidate is checked by greedily filling days in
order, starting a new day when the next package would overflow --
valid only because packages cannot be reordered. O(n log(sum -
max)) time, O(1) space.
"""
def days_needed(capacity: int) -> int:
days_used, deck_load = 1, 0
for weight in weights:
if deck_load + weight > capacity:
days_used += 1
deck_load = 0
deck_load += weight
return days_used
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid
else:
lo = mid + 1
return lo
// LC 1011. Binary search capacity in [heaviest package, total weight]; the
// greedy day-filling check is valid because packages cannot be reordered.
int shipWithinDays(vector<int> weights, int days) {
auto daysAt = [&weights](int capacity) {
int daysUsed = 1, loadToday = 0;
for (int weight : weights) {
if (loadToday + weight > capacity) { // next package overflows: start a new day
++daysUsed;
loadToday = 0;
}
loadToday += weight;
}
return daysUsed;
};
int lo = *max_element(weights.begin(), weights.end());
int hi = accumulate(weights.begin(), weights.end(), 0);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysAt(mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
/// LC 1011. Binary search capacity between the heaviest package (anything
/// less can never ship it) and the total weight. The greedy day-filling
/// check is valid because packages must stay in order.
pub fn ship_within_days(weights: Vec<i32>, days: i32) -> i32 {
let (mut lo, mut hi) = (*weights.iter().max().unwrap(), weights.iter().sum::<i32>());
while lo < hi {
let capacity = lo + (hi - lo) / 2;
let mut days_needed = 1;
let mut load = 0;
for &weight in &weights {
// Overflowing the ship starts a fresh day for this package.
if load + weight > capacity {
days_needed += 1;
load = 0;
}
load += weight;
}
if days_needed <= days {
hi = capacity;
} else {
lo = capacity + 1;
}
}
lo
}
/** LC 1011. Search capacity in [max weight, total]; greedy day-fill checks it. */
export function shipWithinDays(weights: number[], days: number): number {
let lo = Math.max(...weights); // below the heaviest package nothing ships
let hi = weights.reduce((sum, weight) => sum + weight, 0);
while (lo < hi) {
const capacity = (lo + hi) >> 1;
let daysNeeded = 1;
let loadToday = 0;
for (const weight of weights) {
if (loadToday + weight > capacity) {
daysNeeded++; // next package overflows today: start a new day
loadToday = 0;
}
loadToday += weight;
}
if (daysNeeded <= days) hi = capacity;
else lo = capacity + 1;
}
return lo;
}
// LC 1011. Binary search capacity in [heaviest package, total weight]; the
// greedy day-filling check is valid because packages cannot be reordered.
func shipWithinDays(weights []int, days int) int {
daysAt := func(capacity int) int {
daysUsed, loadToday := 1, 0
for _, weight := range weights {
if loadToday+weight > capacity { // next package overflows: start a new day
daysUsed++
loadToday = 0
}
loadToday += weight
}
return daysUsed
}
lo, hi := 0, 0
for _, weight := range weights {
if weight > lo {
lo = weight
}
hi += weight
}
for lo < hi {
mid := lo + (hi-lo)/2
if daysAt(mid) <= days {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
// LC 1011. Binary search capacity in [heaviest package, total weight]; the
// greedy day-filling check is valid because packages cannot be reordered.
func shipWithinDays(_ weights: [Int], _ days: Int) -> Int {
func daysAt(_ capacity: Int) -> Int {
var daysUsed = 1, loadToday = 0
for weight in weights {
if loadToday + weight > capacity { // next package overflows: start a new day
daysUsed += 1
loadToday = 0
}
loadToday += weight
}
return daysUsed
}
var lo = weights.max()!, hi = weights.reduce(0, +)
while lo < hi {
let mid = lo + (hi - lo) / 2
if daysAt(mid) <= days { hi = mid } else { lo = mid + 1 }
}
return lo
}
8. Find Minimum In Rotated Sorted Array
Medium · LC 153
Given a sorted array of distinct values rotated at an unknown pivot, return the minimum element in O(log n). Binary search comparing nums[mid] against nums[hi]: if mid's value is greater, the minimum lies strictly right of mid, otherwise it is at mid or to its left. The comparison must be against the right end; checking nums[lo] breaks on an already sorted array, and hi moves to mid, never past the candidate.
def find_min(nums: list[int]) -> int:
"""LC 153. Find Minimum in Rotated Sorted Array.
Compare nums[mid] against nums[hi]: a larger mid value puts the
minimum strictly right of mid; otherwise mid itself may be the
minimum. The comparison must be against the right end -- checking
nums[lo] breaks on an already sorted array. O(log n) time, O(1)
space.
"""
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop, and the minimum, lie right of mid
else:
hi = mid # mid could BE the minimum; mid - 1 would skip it
return nums[lo]
// LC 153. Compare nums[mid] against nums[hi]: greater means the minimum lies
// strictly right of mid, otherwise mid itself stays a candidate. Comparing
// against nums[lo] instead would break on an already sorted array.
int findMin(vector<int> nums) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
/// LC 153. Compare nums[mid] against nums[hi], never nums[lo]: greater means
/// the rotation point (and minimum) lies strictly right of mid, otherwise
/// mid itself may be the minimum so hi only moves onto it, never past.
pub fn find_min(nums: Vec<i32>) -> i32 {
let (mut lo, mut hi) = (0, nums.len() - 1);
while lo < hi {
let mid = (lo + hi) / 2;
// Checking nums[lo] instead would break on an already sorted array.
if nums[mid] > nums[hi] {
lo = mid + 1;
} else {
hi = mid;
}
}
nums[lo]
}
/** LC 153. Compare mid against nums[hi]; hi moves to mid, never past it. */
export function findMin(nums: number[]): number {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
// comparing against nums[lo] instead breaks on an already sorted array
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid; // mid itself may be the minimum
}
return nums[lo];
}
// LC 153. Compare nums[mid] against nums[hi]: greater means the minimum lies
// strictly right of mid, otherwise mid itself stays a candidate. Comparing
// against nums[lo] instead would break on an already sorted array.
func findMin(nums []int) int {
lo, hi := 0, len(nums)-1
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] > nums[hi] {
lo = mid + 1
} else {
hi = mid
}
}
return nums[lo]
}
// LC 153. Compare nums[mid] against nums[hi]: greater means the minimum lies
// strictly right of mid, otherwise mid itself stays a candidate. Comparing
// against nums[lo] instead would break on an already sorted array.
func findMin(_ nums: [Int]) -> Int {
var lo = 0, hi = nums.count - 1
while lo < hi {
let mid = lo + (hi - lo) / 2
if nums[mid] > nums[hi] { lo = mid + 1 } else { hi = mid }
}
return nums[lo]
}
9. Search In Rotated Sorted Array
Medium · LC 33
Given a rotated sorted array of distinct values and a target, return its index or -1 in O(log n). At each step compare nums[lo] with nums[mid] to decide which half is sorted, then check whether the target falls inside that sorted half's range to choose where to recurse. The invariant is that at least one half is always properly sorted, and the range test must handle its boundaries carefully so the target is never skipped.
def search_rotated(nums: list[int], target: int) -> int:
"""LC 33. Search in Rotated Sorted Array.
At least one half is always properly sorted. Compare nums[lo]
against nums[mid] to identify it, then test whether the target
falls inside that half's value range to pick a side. O(log n)
time, O(1) space.
"""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # <= so a one-element half counts as sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
// LC 33. At least one half is always properly sorted; test whether the target
// falls inside that half's range to choose a side.
int searchRotated(vector<int> nums, int target) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half is the sorted one
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is the sorted one
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
/// LC 33. At least one half around mid is always properly sorted: compare
/// nums[lo] with nums[mid] to identify it, then a plain range test on that
/// sorted half decides which side the target can live on.
pub fn search_rotated(nums: Vec<i32>, target: i32) -> i32 {
let (mut lo, mut hi) = (0i32, nums.len() as i32 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let (l, m, h) = (lo as usize, mid as usize, hi as usize);
if nums[m] == target {
return mid;
}
if nums[l] <= nums[m] {
// Left half sorted: keep it only if the target fits its range.
if nums[l] <= target && target < nums[m] {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
// Right half sorted: same range test, mirrored.
if nums[m] < target && target <= nums[h] {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
-1
}
/** LC 33. One half is always sorted; test if target sits inside its range. */
export function searchRotated(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) {
// left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
// LC 33. At least one half is always properly sorted; test whether the target
// falls inside that half's range to choose a side.
func searchRotated(nums []int, target int) int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target {
return mid
}
if nums[lo] <= nums[mid] { // left half is the sorted one
if nums[lo] <= target && target < nums[mid] {
hi = mid - 1
} else {
lo = mid + 1
}
} else { // right half is the sorted one
if nums[mid] < target && target <= nums[hi] {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return -1
}
// LC 33. At least one half is always properly sorted; test whether the target
// falls inside that half's range to choose a side.
func searchRotated(_ nums: [Int], _ target: Int) -> Int {
var lo = 0, hi = nums.count - 1
while lo <= hi {
let mid = lo + (hi - lo) / 2
if nums[mid] == target { return mid }
if nums[lo] <= nums[mid] { // left half is the sorted one
if nums[lo] <= target && target < nums[mid] { hi = mid - 1 } else { lo = mid + 1 }
} else { // right half is the sorted one
if nums[mid] < target && target <= nums[hi] { lo = mid + 1 } else { hi = mid - 1 }
}
}
return -1
}
10. Search In Rotated Sorted Array II
Medium · LC 81
Given a rotated sorted array that may contain duplicates and a target, return whether the target exists. Use the same sorted-half logic as the distinct version, but when nums[lo], nums[mid], and nums[hi] are all equal nothing can be inferred, so shrink both ends by one and continue. Those equal-edge shrinks are the trick; duplicates can hide which half is sorted, and they degrade the worst case to O(n) while typical cases stay logarithmic.
def search_rotated_ii(nums: list[int], target: int) -> bool:
"""LC 81. Search in Rotated Sorted Array II.
Same sorted-half logic as LC 33, but when nums[lo], nums[mid], and
nums[hi] are all equal nothing identifies the sorted half, so both
ends shrink by one and the loop continues. Duplicates degrade the
worst case to O(n); typical cases stay O(log n). O(1) space.
"""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return True
if nums[lo] == nums[mid] == nums[hi]:
# Equal edges hide which half is sorted; neither end can be the
# missed target, so shrinking both by one is the only safe move.
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
// LC 81. Same sorted-half logic, but when nums[lo], nums[mid], and nums[hi]
// all tie nothing can be inferred, so shrink both ends by one (this is what
// degrades the worst case to O(n)).
bool searchRotatedII(vector<int> nums, int target) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
++lo;
--hi;
} else if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
/// LC 81. Same sorted-half logic as LC 33, plus the duplicate escape hatch:
/// when nums[lo] == nums[mid] == nums[hi] nothing identifies the sorted
/// half, so peel one element off each end. Worst case degrades to O(n).
pub fn search_rotated_ii(nums: Vec<i32>, target: i32) -> bool {
let (mut lo, mut hi) = (0i32, nums.len() as i32 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let (l, m, h) = (lo as usize, mid as usize, hi as usize);
if nums[m] == target {
return true;
}
if nums[l] == nums[m] && nums[m] == nums[h] {
// All three probes equal: duplicates hide the sorted half.
lo += 1;
hi -= 1;
} else if nums[l] <= nums[m] {
if nums[l] <= target && target < nums[m] {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if nums[m] < target && target <= nums[h] {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
false
}
/** LC 81. Same as LC 33, but equal lo/mid/hi reveal nothing: shrink both ends. */
export function searchRotatedII(nums: number[], target: number): boolean {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return true;
if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) {
// duplicates hide which half is sorted; this degrades worst case to O(n)
lo++;
hi--;
} else if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
// LC 81. Same sorted-half logic, but when nums[lo], nums[mid], and nums[hi]
// all tie nothing can be inferred, so shrink both ends by one (this is what
// degrades the worst case to O(n)).
func searchRotatedII(nums []int, target int) bool {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target {
return true
}
if nums[lo] == nums[mid] && nums[mid] == nums[hi] {
lo++
hi--
} else if nums[lo] <= nums[mid] {
if nums[lo] <= target && target < nums[mid] {
hi = mid - 1
} else {
lo = mid + 1
}
} else {
if nums[mid] < target && target <= nums[hi] {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return false
}
// LC 81. Same sorted-half logic, but when nums[lo], nums[mid], and nums[hi]
// all tie nothing can be inferred, so shrink both ends by one (this is what
// degrades the worst case to O(n)).
func searchRotatedII(_ nums: [Int], _ target: Int) -> Bool {
var lo = 0, hi = nums.count - 1
while lo <= hi {
let mid = lo + (hi - lo) / 2
if nums[mid] == target { return true }
if nums[lo] == nums[mid] && nums[mid] == nums[hi] {
lo += 1
hi -= 1
} else if nums[lo] <= nums[mid] {
if nums[lo] <= target && target < nums[mid] { hi = mid - 1 } else { lo = mid + 1 }
} else {
if nums[mid] < target && target <= nums[hi] { lo = mid + 1 } else { hi = mid - 1 }
}
}
return false
}
11. Time Based Key Value Store
Medium · LC 981
Design a store with set(key, value, timestamp) and get(key, timestamp), where get returns the value with the largest timestamp at or before the query, or an empty string. Keep a hash map from key to a list of (timestamp, value) pairs and binary search for the rightmost timestamp not exceeding the query. The lists stay sorted for free because timestamps strictly increase, and get is a floor search, not an exact match.
class TimeMap:
"""LC 981. Time Based Key-Value Store.
Map each key to a list of (timestamp, value) pairs; the lists stay
sorted for free because set() arrives with strictly increasing
timestamps. get() is a FLOOR search, not an exact match: binary
search for the rightmost timestamp at or before the query. set is
O(1), get is O(log n), O(n) space overall.
"""
def __init__(self) -> None:
self.history: dict[str, list[tuple[int, str]]] = {}
def set(self, key: str, value: str, timestamp: int) -> None:
self.history.setdefault(key, []).append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
stamped_values = self.history.get(key, [])
floor_value = ""
lo, hi = 0, len(stamped_values) - 1
while lo <= hi:
mid = (lo + hi) // 2
if stamped_values[mid][0] <= timestamp:
floor_value = stamped_values[mid][1] # best floor so far
lo = mid + 1 # a later timestamp might still qualify
else:
hi = mid - 1
return floor_value
// LC 981. Timestamps strictly increase across set() calls, so each key's list
// stays sorted for free; get() is a floor search, not an exact match.
class TimeMap {
unordered_map<string, vector<pair<int, string>>> history;
public:
void set(string key, string value, int timestamp) {
history[key].emplace_back(timestamp, move(value));
}
string get(string key, int timestamp) {
auto it = history.find(key);
if (it == history.end()) return "";
const vector<pair<int, string>>& entries = it->second;
int lo = 0, hi = static_cast<int>(entries.size()) - 1, floorIdx = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (entries[mid].first <= timestamp) { // candidate floor, look right for a later one
floorIdx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return floorIdx == -1 ? "" : entries[floorIdx].second;
}
};
/// LC 981. Hash map from key to a (timestamp, value) list. Set timestamps
/// strictly increase per key, so plain pushes keep each list sorted for
/// free; get is a floor search (rightmost stamp <= query), not exact match.
pub struct TimeMap {
store: HashMap<String, Vec<(i32, String)>>,
}
impl TimeMap {
pub fn new() -> Self {
TimeMap { store: HashMap::new() }
}
pub fn set(&mut self, key: String, value: String, timestamp: i32) {
self.store.entry(key).or_default().push((timestamp, value));
}
pub fn get(&self, key: String, timestamp: i32) -> String {
let entries = match self.store.get(&key) {
Some(entries) => entries,
None => return String::new(),
};
// Upper bound: lo lands one past the last stamp <= timestamp.
let (mut lo, mut hi) = (0usize, entries.len());
while lo < hi {
let mid = (lo + hi) / 2;
if entries[mid].0 <= timestamp {
lo = mid + 1;
} else {
hi = mid;
}
}
if lo == 0 {
String::new() // every stored stamp is newer than the query
} else {
entries[lo - 1].1.clone()
}
}
}
/** LC 981. Per-key [timestamp, value] list, sorted for free; get is a floor search. */
export class TimeMap {
private history = new Map<string, [number, string][]>();
set(key: string, value: string, timestamp: number): void {
if (!this.history.has(key)) this.history.set(key, []);
this.history.get(key)!.push([timestamp, value]); // timestamps strictly increase
}
get(key: string, timestamp: number): string {
const entries = this.history.get(key);
if (!entries) return "";
let lo = 0;
let hi = entries.length - 1;
let answer = "";
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (entries[mid][0] <= timestamp) {
answer = entries[mid][1]; // candidate floor: keep it, look for a later one
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return answer;
}
}
// LC 981. Timestamps strictly increase across set() calls, so each key's list
// stays sorted for free; get() is a floor search, not an exact match.
type TimeMap struct {
history map[string][]stampedValue
}
type stampedValue struct {
timestamp int
value string
}
func newTimeMap() *TimeMap {
return &TimeMap{history: map[string][]stampedValue{}}
}
func (t *TimeMap) set(key string, value string, timestamp int) {
t.history[key] = append(t.history[key], stampedValue{timestamp, value})
}
func (t *TimeMap) get(key string, timestamp int) string {
entries := t.history[key]
lo, hi, floorIdx := 0, len(entries)-1, -1
for lo <= hi {
mid := lo + (hi-lo)/2
if entries[mid].timestamp <= timestamp { // candidate floor, look right for a later one
floorIdx = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
if floorIdx == -1 {
return ""
}
return entries[floorIdx].value
}
// LC 981. Timestamps strictly increase across set() calls, so each key's list
// stays sorted for free; get() is a floor search, not an exact match.
class TimeMap {
var history: [String: [(timestamp: Int, value: String)]] = [:]
func set(_ key: String, _ value: String, _ timestamp: Int) {
history[key, default: []].append((timestamp, value))
}
func get(_ key: String, _ timestamp: Int) -> String {
guard let entries = history[key] else { return "" }
var lo = 0, hi = entries.count - 1
var floorValue = ""
while lo <= hi {
let mid = lo + (hi - lo) / 2
if entries[mid].timestamp <= timestamp { // candidate floor, look right for a later one
floorValue = entries[mid].value
lo = mid + 1
} else {
hi = mid - 1
}
}
return floorValue
}
}
12. Split Array Largest Sum
Hard · LC 410
Given an array of non-negative integers and an integer k, split it into k contiguous subarrays so the largest subarray sum is minimized, returning that value. Binary search the answer between the maximum element and the total sum, and for each candidate cap greedily count how many pieces it forces. Feasibility means the count is at most k, and it is monotone in the cap, the property that justifies binary searching the answer.
def split_array(nums: list[int], k: int) -> int:
"""LC 410. Split Array Largest Sum.
Binary search the answer between max(nums) (every element must fit
in some piece) and sum(nums) (one piece holds all). For each
candidate cap, greedily count how many pieces it forces; that
count is monotone in the cap, which is what justifies binary
searching the answer. Feasible means at most k pieces. O(n
log(sum - max)) time, O(1) space.
"""
def pieces_forced(cap: int) -> int:
pieces, piece_sum = 1, 0
for num in nums:
if piece_sum + num > cap:
pieces += 1
piece_sum = 0
piece_sum += num
return pieces
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if pieces_forced(mid) <= k:
hi = mid
else:
lo = mid + 1
return lo
// LC 410. Binary search the answer (largest allowed piece sum) between the
// maximum element and the total; the piece count a cap forces is monotone in
// the cap, which justifies the search.
int splitArray(vector<int> nums, int k) {
auto piecesUnder = [&nums](long long cap) {
int pieces = 1;
long long pieceSum = 0;
for (int num : nums) {
if (pieceSum + num > cap) { // num would burst the cap: open a new piece
++pieces;
pieceSum = 0;
}
pieceSum += num;
}
return pieces;
};
long long lo = *max_element(nums.begin(), nums.end());
long long hi = accumulate(nums.begin(), nums.end(), 0LL);
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (piecesUnder(mid) <= k) hi = mid;
else lo = mid + 1;
}
return static_cast<int>(lo);
}
/// LC 410. Binary search the answer: a cap between the maximum element and
/// the total sum. For each cap, greedily count the pieces it forces; the
/// count is monotone in the cap, which justifies searching the answer space.
pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
let mut lo = *nums.iter().max().unwrap() as i64;
let mut hi = nums.iter().map(|&num| num as i64).sum::<i64>();
while lo < hi {
let cap = lo + (hi - lo) / 2;
let mut pieces = 1;
let mut running_sum = 0i64;
for &num in &nums {
if running_sum + num as i64 > cap {
pieces += 1;
running_sum = 0;
}
running_sum += num as i64;
}
// Fewer than k pieces is fine: splitting further never raises the max.
if pieces <= k {
hi = cap;
} else {
lo = cap + 1;
}
}
lo as i32
}
/** LC 410. Search the cap in [max, sum]; greedy piece count is monotone in it. */
export function splitArray(nums: number[], k: number): number {
let lo = Math.max(...nums); // every piece must hold its largest element
let hi = nums.reduce((sum, num) => sum + num, 0);
while (lo < hi) {
const cap = (lo + hi) >> 1;
let pieces = 1;
let pieceSum = 0;
for (const num of nums) {
if (pieceSum + num > cap) {
pieces++; // num would overflow this piece: start the next one
pieceSum = 0;
}
pieceSum += num;
}
if (pieces <= k) hi = cap; // cap achievable: try a tighter one
else lo = cap + 1;
}
return lo;
}
// LC 410. Binary search the answer (largest allowed piece sum) between the
// maximum element and the total; the piece count a cap forces is monotone in
// the cap, which justifies the search.
func splitArray(nums []int, k int) int {
piecesUnder := func(pieceCap int) int {
pieces, pieceSum := 1, 0
for _, num := range nums {
if pieceSum+num > pieceCap { // num would burst the cap: open a new piece
pieces++
pieceSum = 0
}
pieceSum += num
}
return pieces
}
lo, hi := 0, 0
for _, num := range nums {
if num > lo {
lo = num
}
hi += num
}
for lo < hi {
mid := lo + (hi-lo)/2
if piecesUnder(mid) <= k {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
// LC 410. Binary search the answer (largest allowed piece sum) between the
// maximum element and the total; the piece count a cap forces is monotone in
// the cap, which justifies the search.
func splitArray(_ nums: [Int], _ k: Int) -> Int {
func piecesUnder(_ cap: Int) -> Int {
var pieces = 1, pieceSum = 0
for num in nums {
if pieceSum + num > cap { // num would burst the cap: open a new piece
pieces += 1
pieceSum = 0
}
pieceSum += num
}
return pieces
}
var lo = nums.max()!, hi = nums.reduce(0, +)
while lo < hi {
let mid = lo + (hi - lo) / 2
if piecesUnder(mid) <= k { hi = mid } else { lo = mid + 1 }
}
return lo
}
13. Median of Two Sorted Arrays
Hard · LC 4
Given two sorted arrays, return the median of their merged order in O(log(min(m, n))) time. Binary search a cut in the smaller array; the cut in the larger one is then forced so the two left halves hold half of all elements combined. A cut is valid when each left maximum is at most the opposite right minimum; sentinel infinities handle empty sides, and searching the smaller array keeps the cut in bounds.
def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
"""LC 4. Median of Two Sorted Arrays.
Binary search a cut in the SMALLER array; the cut in the larger
one is then forced so the two left halves together hold half of
all elements (the extra one parks on the left when the total is
odd). A cut is valid when each left maximum is at most the
opposite right minimum; sentinel infinities stand in for empty
sides. O(log(min(m, n))) time, O(1) space.
"""
short, long = nums1, nums2
if len(short) > len(long):
short, long = long, short
total = len(short) + len(long)
left_half_size = (total + 1) // 2 # odd totals put the extra on the left
lo, hi = 0, len(short)
while True: # a valid cut always exists, so the loop returns from inside
short_cut = (lo + hi) // 2
long_cut = left_half_size - short_cut
short_left = short[short_cut - 1] if short_cut > 0 else float("-inf")
short_right = short[short_cut] if short_cut < len(short) else float("inf")
long_left = long[long_cut - 1] if long_cut > 0 else float("-inf")
long_right = long[long_cut] if long_cut < len(long) else float("inf")
if short_left <= long_right and long_left <= short_right:
if total % 2:
return float(max(short_left, long_left))
return (max(short_left, long_left) + min(short_right, long_right)) / 2
if short_left > long_right:
hi = short_cut - 1 # short gave too much to the left; cut earlier
else:
lo = short_cut + 1
// LC 4. Binary search a cut in the smaller array; the cut in the larger one
// is forced so both left halves hold half of all elements. A cut is valid
// when each left max is at most the opposite right min, with sentinel
// infinities standing in for empty sides.
double findMedianSortedArrays(vector<int> shorter, vector<int> longer) {
if (shorter.size() > longer.size()) swap(shorter, longer);
int m = static_cast<int>(shorter.size()), n = static_cast<int>(longer.size());
int half = (m + n + 1) / 2; // odd totals put the extra element on the left side
int lo = 0, hi = m;
while (true) {
int cutShort = lo + (hi - lo) / 2;
int cutLong = half - cutShort;
int leftShortMax = cutShort == 0 ? INT_MIN : shorter[cutShort - 1];
int rightShortMin = cutShort == m ? INT_MAX : shorter[cutShort];
int leftLongMax = cutLong == 0 ? INT_MIN : longer[cutLong - 1];
int rightLongMin = cutLong == n ? INT_MAX : longer[cutLong];
if (leftShortMax > rightLongMin) hi = cutShort - 1; // took too much from the shorter array
else if (leftLongMax > rightShortMin) lo = cutShort + 1; // took too little
else {
if ((m + n) % 2) return max(leftShortMax, leftLongMax);
return (max(leftShortMax, leftLongMax) + min(rightShortMin, rightLongMin)) / 2.0;
}
}
}
/// LC 4. Binary search a cut in the SMALLER array; the cut in the larger one
/// is forced so the two left halves hold half of all elements. A cut is
/// valid when each left max is at most the opposite right min; i32 MIN/MAX
/// sentinels stand in for the missing neighbors of an empty side.
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
// Cutting the smaller array keeps the forced cut in the larger in bounds.
let (short, long) = if nums1.len() <= nums2.len() {
(&nums1, &nums2)
} else {
(&nums2, &nums1)
};
let total = short.len() + long.len();
let left_size = (total + 1) / 2; // odd totals park the extra on the left
let (mut lo, mut hi) = (0usize, short.len());
loop {
let short_cut = (lo + hi) / 2;
let long_cut = left_size - short_cut;
let short_left = if short_cut == 0 { i32::MIN } else { short[short_cut - 1] };
let short_right = if short_cut == short.len() { i32::MAX } else { short[short_cut] };
let long_left = if long_cut == 0 { i32::MIN } else { long[long_cut - 1] };
let long_right = if long_cut == long.len() { i32::MAX } else { long[long_cut] };
if short_left <= long_right && long_left <= short_right {
return if total % 2 == 1 {
short_left.max(long_left) as f64
} else {
(short_left.max(long_left) as f64 + short_right.min(long_right) as f64) / 2.0
};
} else if short_left > long_right {
hi = short_cut - 1; // short contributed too much to the left half
} else {
lo = short_cut + 1;
}
}
}
/** LC 4. Cut the smaller array; the other cut is forced. Valid when left maxes <= opposite right mins. */
export function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length;
const n = nums2.length;
const leftTotal = Math.floor((m + n + 1) / 2); // left halves take the extra element on odd totals
let lo = 0;
let hi = m;
while (lo <= hi) {
const cut1 = (lo + hi) >> 1;
const cut2 = leftTotal - cut1;
// Infinity sentinels stand in for the empty side of a cut
const left1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
const right1 = cut1 === m ? Infinity : nums1[cut1];
const left2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
const right2 = cut2 === n ? Infinity : nums2[cut2];
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 === 1) return Math.max(left1, left2);
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
}
if (left1 > right2) hi = cut1 - 1; // cut1 took too many from nums1
else lo = cut1 + 1;
}
return 0; // unreachable for valid sorted input
}
// LC 4. Binary search a cut in the smaller array; the cut in the larger one
// is forced so both left halves hold half of all elements. A cut is valid
// when each left max is at most the opposite right min, with sentinel
// infinities standing in for empty sides.
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
shorter, longer := nums1, nums2
if len(shorter) > len(longer) {
shorter, longer = longer, shorter
}
m, n := len(shorter), len(longer)
half := (m + n + 1) / 2 // odd totals put the extra element on the left side
lo, hi := 0, m
for { // a valid cut always exists, so the loop returns from inside
cutShort := lo + (hi-lo)/2
cutLong := half - cutShort
leftShortMax, rightShortMin := math.MinInt32, math.MaxInt32
if cutShort > 0 {
leftShortMax = shorter[cutShort-1]
}
if cutShort < m {
rightShortMin = shorter[cutShort]
}
leftLongMax, rightLongMin := math.MinInt32, math.MaxInt32
if cutLong > 0 {
leftLongMax = longer[cutLong-1]
}
if cutLong < n {
rightLongMin = longer[cutLong]
}
if leftShortMax > rightLongMin { // took too much from the shorter array
hi = cutShort - 1
} else if leftLongMax > rightShortMin { // took too little
lo = cutShort + 1
} else {
leftMax := leftShortMax
if leftLongMax > leftMax {
leftMax = leftLongMax
}
if (m+n)%2 == 1 {
return float64(leftMax)
}
rightMin := rightShortMin
if rightLongMin < rightMin {
rightMin = rightLongMin
}
return float64(leftMax+rightMin) / 2.0
}
}
}
// LC 4. Binary search a cut in the smaller array; the cut in the larger one
// is forced so both left halves hold half of all elements. A cut is valid
// when each left max is at most the opposite right min, with sentinel
// infinities standing in for empty sides.
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var shorter = nums1, longer = nums2
if shorter.count > longer.count { swap(&shorter, &longer) }
let m = shorter.count, n = longer.count
let half = (m + n + 1) / 2 // odd totals put the extra element on the left side
var lo = 0, hi = m
while true { // a valid cut always exists, so the loop returns from inside
let cutShort = lo + (hi - lo) / 2
let cutLong = half - cutShort
let leftShortMax = cutShort == 0 ? Int.min : shorter[cutShort - 1]
let rightShortMin = cutShort == m ? Int.max : shorter[cutShort]
let leftLongMax = cutLong == 0 ? Int.min : longer[cutLong - 1]
let rightLongMin = cutLong == n ? Int.max : longer[cutLong]
if leftShortMax > rightLongMin {
hi = cutShort - 1 // took too much from the shorter array
} else if leftLongMax > rightShortMin {
lo = cutShort + 1 // took too little
} else {
if (m + n) % 2 == 1 { return Double(max(leftShortMax, leftLongMax)) }
return (Double(max(leftShortMax, leftLongMax)) + Double(min(rightShortMin, rightLongMin))) / 2.0
}
}
}
14. Find in Mountain Array
Hard · LC 1095
Given an interactive mountain array, strictly increasing then strictly decreasing, return the smallest index of a target, or -1, using a limited number of get calls. First binary search for the peak by comparing each mid against its right neighbor, then run an ascending search on the left slope and a descending one on the right. Searching the left slope first guarantees the smallest index, and locating the peak restores sortedness to each half.
def find_in_mountain_array(target: int, mountain: list[int]) -> int:
"""LC 1095. Find in Mountain Array.
Binary search for the peak by comparing each mid against its right
neighbor -- locating it restores sortedness to each slope -- then
search the ascending left slope FIRST (any hit there is the
smallest index) and the descending right slope only if needed.
O(log n) time, O(1) space.
"""
def search_slope(lo: int, hi: int, ascending: bool) -> int:
while lo <= hi:
mid = (lo + hi) // 2
if mountain[mid] == target:
return mid
# On a descending slope "value too small" means look LEFT, so
# the comparison flips with the slope's direction.
if (mountain[mid] < target) == ascending:
lo = mid + 1
else:
hi = mid - 1
return -1
lo, hi = 0, len(mountain) - 1
while lo < hi:
mid = (lo + hi) // 2
if mountain[mid] < mountain[mid + 1]:
lo = mid + 1 # still climbing: the peak is right of mid
else:
hi = mid # mid could BE the peak; mid - 1 would skip it
peak = lo
on_the_way_up = search_slope(0, peak, ascending=True)
if on_the_way_up != -1:
return on_the_way_up
return search_slope(peak + 1, len(mountain) - 1, ascending=False)
// LC 1095. Locate the peak by comparing each mid with its right neighbor
// (restoring sortedness to each slope), then search the ascending left slope
// first so the smallest index wins, falling back to the descending right one.
int findInMountainArray(int target, vector<int> mountain) {
int n = static_cast<int>(mountain.size());
auto get = [&mountain](int idx) { return mountain[idx]; }; // stands in for the call-limited MountainArray API
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (get(mid) < get(mid + 1)) lo = mid + 1; // still on the climb, peak is right of mid
else hi = mid;
}
int peak = lo;
auto slopeSearch = [&get, target](int slopeLo, int slopeHi, bool ascending) {
while (slopeLo <= slopeHi) {
int mid = slopeLo + (slopeHi - slopeLo) / 2;
int value = get(mid);
if (value == target) return mid;
// On a descending slope "too small" means the target lies left.
if ((value < target) == ascending) slopeLo = mid + 1;
else slopeHi = mid - 1;
}
return -1;
};
int leftSlopeHit = slopeSearch(0, peak, true);
if (leftSlopeHit != -1) return leftSlopeHit;
return slopeSearch(peak + 1, n - 1, false);
}
/// LC 1095. Three binary searches: find the peak by comparing each mid with
/// its right neighbor, then search the ascending left slope, then the
/// descending right slope. Left slope first guarantees the smallest index.
pub fn find_in_mountain_array(target: i32, mountain: Vec<i32>) -> i32 {
// Peak = first index whose right neighbor is smaller.
let (mut lo, mut hi) = (0usize, mountain.len() - 1);
while lo < hi {
let mid = (lo + hi) / 2;
if mountain[mid] < mountain[mid + 1] {
lo = mid + 1;
} else {
hi = mid;
}
}
let peak = lo;
let (mut lo, mut hi) = (0i32, peak as i32);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let value = mountain[mid as usize];
if value == target {
return mid;
} else if value < target {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
let (mut lo, mut hi) = (peak as i32, mountain.len() as i32 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let value = mountain[mid as usize];
if value == target {
return mid;
} else if value > target {
lo = mid + 1; // descending slope: the comparisons flip
} else {
hi = mid - 1;
}
}
-1
}
/** LC 1095. Find the peak, then search the ascending slope before the descending one. */
export function findInMountainArray(target: number, mountain: number[]): number {
// stands in for the call-limited MountainArray API's get
const get = (index: number): number => mountain[index];
let lo = 0;
let hi = mountain.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
// still climbing if the right neighbor is bigger; peak is the first descent
if (get(mid) < get(mid + 1)) lo = mid + 1;
else hi = mid;
}
const peak = lo;
const slopeSearch = (left: number, right: number, ascending: boolean): number => {
while (left <= right) {
const mid = (left + right) >> 1;
const value = get(mid);
if (value === target) return mid;
// a value below target moves right only when the slope rises
if ((value < target) === ascending) left = mid + 1;
else right = mid - 1;
}
return -1;
};
// left slope first guarantees the smallest index on a cross-slope duplicate
const onAscent = slopeSearch(0, peak, true);
if (onAscent !== -1) return onAscent;
return slopeSearch(peak + 1, mountain.length - 1, false);
}
// LC 1095. Locate the peak by comparing each mid with its right neighbor
// (restoring sortedness to each slope), then search the ascending left slope
// first so the smallest index wins, falling back to the descending right one.
func findInMountainArray(target int, mountain []int) int {
n := len(mountain)
get := func(idx int) int { return mountain[idx] } // stands in for the call-limited MountainArray API
lo, hi := 0, n-1
for lo < hi {
mid := lo + (hi-lo)/2
if get(mid) < get(mid+1) {
lo = mid + 1 // still on the climb, peak is right of mid
} else {
hi = mid
}
}
peak := lo
slopeSearch := func(slopeLo, slopeHi int, ascending bool) int {
for slopeLo <= slopeHi {
mid := slopeLo + (slopeHi-slopeLo)/2
value := get(mid)
if value == target {
return mid
}
// On a descending slope "too small" means the target lies left.
if (value < target) == ascending {
slopeLo = mid + 1
} else {
slopeHi = mid - 1
}
}
return -1
}
if leftSlopeHit := slopeSearch(0, peak, true); leftSlopeHit != -1 {
return leftSlopeHit
}
return slopeSearch(peak+1, n-1, false)
}
// LC 1095. Locate the peak by comparing each mid with its right neighbor
// (restoring sortedness to each slope), then search the ascending left slope
// first so the smallest index wins, falling back to the descending right one.
func findInMountainArray(_ target: Int, _ mountain: [Int]) -> Int {
let n = mountain.count
func get(_ idx: Int) -> Int { return mountain[idx] } // stands in for the call-limited MountainArray API
var lo = 0, hi = n - 1
while lo < hi {
let mid = lo + (hi - lo) / 2
if get(mid) < get(mid + 1) { lo = mid + 1 } else { hi = mid } // still climbing: peak is right of mid
}
let peak = lo
func slopeSearch(_ slopeLo: Int, _ slopeHi: Int, _ ascending: Bool) -> Int {
var lo = slopeLo, hi = slopeHi
while lo <= hi {
let mid = lo + (hi - lo) / 2
let value = get(mid)
if value == target { return mid }
// On a descending slope "too small" means the target lies left.
if (value < target) == ascending { lo = mid + 1 } else { hi = mid - 1 }
}
return -1
}
let leftSlopeHit = slopeSearch(0, peak, true)
if leftSlopeHit != -1 { return leftSlopeHit }
return slopeSearch(peak + 1, n - 1, false)
}