Binary Search

Master this topic with zero to advance depth.

Binary Search: The Art of Halving

$O(\\log N)$ is the gold standard for searching in massive datasets. Instead of looking at every element, we discard half the possibilities at every step.

1. The Core Prerequisites

For Binary Search to work, the search space must be Monotonic. This usually means:

The array is Sorted (increasing or decreasing).
A Boolean function $f(x)$ changes from $False$ to $True$ at exactly one point (Binary Search on Answer).

2. The Three Pillars

Pillar	Detail	Why?
Search Space	The range $[low, high]$ of possible answers.	Defines where to hunt.
Mid Point	$mid = low + \\lfloor (high - low) / 2 \\rfloor$	Prevents integer overflow.
Decision Logic	Determining if we should look in the left half or right half.	Discards $N/2$ elements.

3. Common Templates

Standard Search: Find an exact value. Loop: while (low <= high), Update: low = mid + 1 or high = mid - 1.
Boundary Search: Find first or last occurrence (Lower/Upper Bound). Loop: while (low < high), Update: high = mid to keep candidate.
Monotonic Function: Find the smallest $X$ satisfying a condition. Check function: if (possible(X)) high = mid.

4. Mental Model: The Phone Book

If you're looking for "Pallav" in a phone book, you don't start at page 1. You open the middle, see "M", realize "P" is later, and discard everything before "M". You repeat this until you land on the page.

Binary Search

Given a sorted array of integers nums and a target value target, return the index of target if it exists. Otherwise, return -1. You must write an algorithm with $O(\\log N)$ runtime complexity.

Easy

Examples

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
9 exists at index 4.

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
2 does not exist in the array.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

The most basic way to find a target is to check every element one by one. While simple, it fails to exploit the 'sorted' property of the input.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

Step	Index	Value	Match?
1	0	-1	No
2	1	0	No
3	2	3	No
4	3	5	No
5	4	9	Yes (Return 4)

java

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

Approach 2

Level II: Recursive Binary Search

Intuition

Binary search naturally follows a 'Divide and Conquer' pattern. We check the middle, and then solve the same problem on a smaller subarray (either left or right half).

⏱ $O(\\log N)$💾 $O(\\log N)$ due to recursion stack depth.

Detailed Dry Run

Target: 9, Range: [0, 5]

mid = 2 (val 3). 3 < 9. Recurse right half [3, 5].
mid = 4 (val 9). 9 == 9. Return 4.

java

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
    private int binarySearch(int[] nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) return binarySearch(nums, target, mid + 1, r);
        return binarySearch(nums, target, l, mid - 1);
    }
}

Approach 3

Level III: Optimal (Iterative Binary Search)

Intuition

Iterative binary search is the industry standard. It achieves the same $O(\\log N)$ time but uses $O(1)$ constant space by avoiding recursion. Key point: Always use mid = l + (r - l) / 2 to avoid integer overflow.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Decision
1	0	5	2	3	3 < 9 → L = 3
2	3	5	4	9	9 == 9 → Return 4

java

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
}

Search Insert Position

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Your algorithm must run in $O(\\log N)$ time.

Easy

Examples

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Since the array is sorted, we can simply find the first element that is greater than or equal to the target. That index is our insertion point.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,3,5,6], target = 2

0: 1 < 2
1: 3 >= 2. Return 1.

java

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) return i;
        }
        return nums.length;
    }
}

Approach 2

Level III: Optimal (Binary Search - Lower Bound)

Intuition

Binary search finds the 'lower bound'—the first index where nums[index] >= target. When the loop while (l <= r) exits, the l pointer naturally lands on the correct insertion index.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Decision
1	0	3	1	3	3 > 2 → R = 0
2	0	0	0	1	1 < 2 → L = 1
Exit	1	0	-	-	Return L = 1

java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
}

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with $O(\\log N)$ runtime complexity.

Medium

Examples

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1, -1]

Approach 1

Level I: Brute Force (Two Pass Linear Scan)

Intuition

Scan from the left to find the first occurrence, and from the right to find the last. While simple, it takes $O(N)$ time, missing the efficiency of sorted bounds.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [5,7,7,8,8,10], target = 8

First: index 0(5), 1(7), 2(7), 3(8) -> 3
Last: index 5(10), 4(8) -> 4 Result: [3, 4]

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return new int[]{first, last};
    }
}

Approach 2

Level II: Optimal (Built-in Library)

Intuition

Most languages provide built-in binary search functions (like bisect_left and bisect_right in Python, or lower_bound/upper_bound in C++). These are highly optimized and should be used in production.

⏱ $O(\log N)$💾 $O(1)$

Detailed Dry Run

nums = [5,7,7,8,8,10], target = 8

lower_bound finds first index where val >= 8: index 3.
upper_bound finds first index where val > 8: index 5.
Result: [3, 5-1=4].

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) return new int[]{-1, -1};
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }
    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1; else r = mid;
        }
        return l;
    }
}

Approach 3

Level III: Optimal (Two Binary Searches)

Intuition

We perform two separate binary searches. In the first search (find left bound), when nums[mid] == target, we continue searching left (high = mid - 1). In the second search (find right bound), we continue searching right (low = mid + 1).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

nums = [5,7,7,8,8,10], target = 8

Search First: mid = 2 (val 7). 7 < 8 -> L=3. mid = 4 (val 8). 8==8 -> save 4, R=3. mid = 3 (val 8). 8==8 -> save 3, R=2. End. Result index 3.
Search Last: Similar logic searching right. Result index 4.

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findBound(nums, target, true);
        if (first == -1) return new int[]{-1, -1};
        int last = findBound(nums, target, false);
        return new int[]{first, last};
    }
    private int findBound(int[] nums, int target, boolean isFirst) {
        int l = 0, r = nums.length - 1, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                ans = mid;
                if (isFirst) r = mid - 1;
                else l = mid + 1;
            } else if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
}

Find Peak Element

A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -\\infty. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

Input: nums = [1,2,3,1]
Output: 2
3 is a peak element and its index is 2.

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Your function can return either index 1 where the peak element is 2, or index 5 where the peak element is 6.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Since any element that is greater than its next neighbor is a potential peak (because we know the previous element was smaller, or it's the first element), we can just scan linearly.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,2,3,1]

0: 1 < 2
1: 2 < 3
2: 3 > 1. Return 2.

java

class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) return i;
        }
        return nums.length - 1;
    }
}

Approach 2

Level II: Recursive Binary Search

Intuition

Divide the array and check the middle element's slope. If we are going up, a peak must exist on the right. If we are going down, a peak must exist on the left.

⏱ $O(\log N)$💾 $O(\log N)$ due to recursion stack.

Detailed Dry Run

nums = [1,2,3,1]. L=0, R=3.

mid=1. nums[1]=2 < nums[2]=3. Search [2, 3].
mid=2. nums[2]=3 > nums[3]=1. Search [2, 2].
L=R=2. Return 2.

java

class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    private int search(int[] nums, int l, int r) {
        if (l == r) return l;
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

Approach 3

Level III: Optimal (Binary Search on Slope)

Intuition

We can use binary search by looking at the slope. If nums[mid] < nums[mid+1], it means we are on a rising slope, and a peak must exist to the right. If nums[mid] > nums[mid+1], we are on a falling slope, and a peak must exist to the left (including mid).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	nums[Mid+1]	Decision
1	0	6	3	3	5	3 < 5 → L = 4
2	4	6	5	6	4	6 > 4 → R = 5
3	4	5	4	5	6	5 < 6 → L = 5
Exit	5	5	-	-	-	Return L = 5

java

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

Input: nums = [3,4,5,1,2]
Output: 1
The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Simply scan the array and find the minimum element. We don't exploit the sorted/rotated property.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [3,4,5,1,2]. Min starts at 3. Compare with 4, 5, 1 (new min), 2. Result: 1.

java

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int n : nums) if (n < min) min = n;
        return min;
    }
}

Approach 2

Level III: Optimal (Binary Search)

Intuition

In a rotated sorted array, if nums[mid] > nums[right], the minimum must be in the right half (excluding mid). Otherwise, it's in the left half (including mid).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	nums[R]	Decision
1	0	4	2	5	2	5 > 2 → L = 3
2	3	4	3	1	2	1 < 2 → R = 3
Exit	3	3	-	-	-	Return nums[3] = 1

java

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) l = mid + 1;
            else r = mid;
        }
        return nums[l];
    }
}

Search in Rotated Sorted Array

Given the array nums after a possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. All values in nums are unique. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Approach 1

Level I: Brute Force

Intuition

The simplest way is to iterate through the entire array and check if any element equals the target.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [4,5,6,7,0,1,2], target = 0

i=0: 4 != 0
i=1: 5 != 0
i=2: 6 != 0
i=3: 7 != 0
i=4: 0 == 0. Return 4.

java

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

Approach 2

Level II: Find Pivot + Two Binary Searches

Intuition

First, find the index of the minimum element (the pivot). This splits the array into two sorted halves. Perform a standard binary search on the appropriate half.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

nums = [4,5,6,7,0,1,2], target = 0

Find pivot (min element): nums[4] = 0. Pivot index is 4.
Target 0 >= nums[4] and 0 <= nums[6] (2). Target is in right half [4..6].
Binary search on [4..6] for 0. Found at index 4.

java

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) l = mid + 1;
            else r = mid;
        }
        int pivot = l;
        l = 0; r = n - 1;
        if (target >= nums[pivot] && target <= nums[r]) l = pivot;
        else r = pivot - 1;
        
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
}

Approach 3

Level III: Optimal (Single Pass Binary Search)

Intuition

In every step, at least one half of the current range must be sorted. We check which half is sorted and determine if the target lies within it. This avoids finding the pivot separately.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Sorted?	Target In?	Decision
1	0	6	3	7	Left [0..3]	No (0 < 4 or 0 > 7)	L = 4
2	4	6	5	1	Right [5..6]	No (0 < 1 or 0 > 2)	R = 4
3	4	4	4	0	Found!	-	Return 4

java

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) { // Left half is sorted
                if (target >= nums[l] && target < nums[mid]) r = mid - 1;
                else l = mid + 1;
            } else { // Right half is sorted
                if (target > nums[mid] && target <= nums[r]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    }
}

Search a 2D Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. The matrix has the following properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row.

Medium

Examples

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Approach 1

Level I: Brute Force

Intuition

Iterate through every row and every column to find the target. This does not take advantage of any sorting.

⏱ $O(M \\times N)$💾 $O(1)$

Detailed Dry Run

Searching for 3 in [[1,3,5...], ...]

[0][0]: 1
[0][1]: 3. Found!

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int val : row) {
                if (val == target) return true;
            }
        }
        return false;
    }
}

Approach 2

Level II: Row-wise Binary Search

Intuition

First, binary search through the first column to find which row could potentially contain the target. Then, perform a binary search within that specific row.

⏱ $O(\\log M + \\log N)$💾 $O(1)$

Detailed Dry Run

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Search first column [1, 10, 23] for row where target could be. Matrix[0][0] <= 3 < Matrix[1][0] (10). Row index 0.
Binary search Row 0 [1,3,5,7] for 3. Found at index 1.

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int up = 0, down = m - 1;
        while (up <= down) {
            int mid = up + (down - up) / 2;
            if (matrix[mid][0] <= target && target <= matrix[mid][n - 1]) {
                return binarySearch(matrix[mid], target);
            } else if (matrix[mid][0] > target) down = mid - 1;
            else up = mid + 1;
        }
        return false;
    }
    private boolean binarySearch(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) return true;
            if (arr[mid] < target) l = mid + 1; else r = mid - 1;
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Flattened Binary Search)

Intuition

Treat the entire $m \\times n$ matrix as a single sorted array of size $m \\times n$ . We can map a 1D index idx to 2D coordinates using row = idx / n and col = idx % n.

⏱ $O(\\log(M \\times N))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Row=Mid/4	Col=Mid%4	Val	Decision
1	0	11	5	1	1	11	11 > 3 → R = 4
2	0	4	2	0	2	5	5 > 3 → R = 1
3	0	1	0	0	0	1	1 < 3 → L = 1
4	1	1	1	0	1	3	Found!

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int row = mid / n, col = mid % n;
            if (matrix[row][col] == target) return true;
            if (matrix[row][col] < target) l = mid + 1; else r = mid - 1;
        }
        return false;
    }
}

Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Your solution must run in $O(\\log N)$ time and $O(1)$ space.

Medium

Examples

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Approach 1

Level I: XOR Manipulation

Intuition

XORing a number with itself results in 0. XORing 0 with any number results in that number. If we XOR all elements, the pairs will cancel out, leaving the single element.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2] 1 ^ 1 ^ 2 = 0 ^ 2 = 2. Result: 2.

java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int n : nums) res ^= n;
        return res;
    }
}

Approach 2

Level II: Linear Scan (Pairs)

Intuition

Since the array is sorted, we can check elements in pairs. If nums[i] is not equal to nums[i+1], then nums[i] is the single element.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2,3,3]

i=0: nums[0]==nums[1] (1==1). Continue.
i=2: nums[2]!=nums[3] (2!=3). Return nums[2]=2.

java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}

Approach 3

Level III: Optimal (Binary Search on Even Indices)

Intuition

In a paired array, pairs start at even indices: (0,1), (2,3), etc. Before the single element, nums[even] == nums[even+1]. After the single element, this pattern breaks. We search for the first index where nums[even] != nums[even+1].

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Mid_Even	nums[M_E] == nums[M_E+1]	Decision
1	0	8	4	4	3 == 4 (No)	R = 4
2	0	4	2	2	2 == 3 (No)	R = 2
Exit	2	2	-	-	-	Return nums[2] = 2

java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) l = mid + 2;
            else r = mid;
        }
        return nums[l];
    }
}

Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

Examples

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Approach 1

Level I: Brute Force (Sort by Distance)

Intuition

Calculate the absolute difference of each element from $x$ . Sort the array based on these distances. In case of a tie, the smaller element comes first. Return the first $k$ elements.

⏱ $O(N \\log N)$💾 $O(N)$

Detailed Dry Run

arr = [1,2,3,4,5], k = 4, x = 3

Distances: [2, 1, 0, 1, 2]
Sorted by (dist, val): [(0,3), (1,2), (1,4), (2,1), (2,5)]
Take k=4: [3, 2, 4, 1]
Sort Result: [1, 2, 3, 4].

java

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        for (int n : arr) list.add(n);
        Collections.sort(list, (a, b) -> {
            int d1 = Math.abs(a - x);
            int d2 = Math.abs(b - x);
            if (d1 == d2) return a - b;
            return d1 - d2;
        });
        List<Integer> res = list.subList(0, k);
        Collections.sort(res);
        return res;
    }
}

Approach 2

Level II: Binary Search + Two Pointers

Intuition

Use binary search to find the position closest to $x$ . Then expand outwards using two pointers to find the $k$ closest elements.

⏱ $O(\\log N + K)$💾 $O(K)$

Detailed Dry Run

arr = [1,2,3,4,5], k=4, x=3

BS for 3: index 2.
L=1, R=3. Compare arr[1]=2 and arr[3]=4.
Keep expanding until k=4 is reached.

java

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int l = 0, r = n - 1;
        int pos = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] <= x) {
                pos = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        l = pos; r = pos + 1;
        while (r - l - 1 < k) {
            if (l < 0) r++;
            else if (r >= n) l--;
            else if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) l--;
            else r++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = l + 1; i < r; i++) res.add(arr[i]);
        return res;
    }
}

Approach 3

Level III: Optimal (Binary Search on Window Start)

Intuition

We want a contiguous window of k elements from the sorted array. Binary search for the LEFT endpoint of that window. For a candidate window starting at mid, compare if x - arr[mid] (distance to left edge) is greater than arr[mid+k] - x (distance to right edge). If left edge is farther, shift window right.

⏱ O(log(N-K)) — binary search on start index.💾 O(1) extra — the result itself is O(K).

Detailed Dry Run

Input: arr=[1,2,3,4,5], k=4, x=3 | Step | l | r | mid | arr[mid] | arr[mid+k] | dist left | dist right | Decision | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | 0 | 1 | 0 | 1 | 5 | 3-1=2 | 5-3=2 | Equal, go left: r=0 | | l==r==0 → window=[arr[0]..arr[3]]=[1,2,3,4]** |

java

import java.util.*;

public class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0, r = arr.length - k; // r is the max valid start index
        while (l < r) {
            int mid = l + (r - l) / 2;
            // Compare distances of left and right edges of the window
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1; // left too far, shift right
            else r = mid;                                        // right too far or equal, shift left
        }
        List<Integer> res = new ArrayList<>();
        for (int i = l; i < l + k; i++) res.add(arr[i]);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); // [1,2,3,4]
        System.out.println(sol.findClosestElements(new int[]{1,2,3,4,5}, 4, -1)); // [1,2,3,4]
    }
}

⚠️ Common Pitfalls & Tips

The search bounds are [0, N-K] (not [0, N-1]). The tie-breaking rule is: when x - arr[mid] == arr[mid+k] - x, prefer the smaller element (i.e., r = mid, not l = mid+1).

Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within days days. The i-th package on the conveyor belt has a weight of weights[i]. Find the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Medium

Examples

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Approach 1

Level I: Brute Force (Try Every Capacity)

Intuition

The minimum possible capacity is max(weights) (must ship heaviest package) and maximum is sum(weights) (all in one day). Try each value from min ascending and try to simulate — find the first one that ships all packages within D days.

⏱ O(N * (Sum-Max)) — for each candidate capacity we simulate the entire ship.💾 O(1) — constant variables.

Detailed Dry Run

Input: weights=[1,2,3,4,5,6,7,8,9,10], days=5 Min capacity = max = 10. Try 10: simulate → days used = 10 (too many). Try 15: simulate [1-5=15], [6-8=21 split], check... Actually enumerate until 15 fits in 5 days.

java

public class Solution {
    private int daysNeeded(int[] weights, int cap) {
        int days = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { days++; cur = 0; }
            cur += w;
        }
        return days;
    }
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        for (int cap = lo; cap <= hi; cap++) {
            if (daysNeeded(weights, cap) <= days) return cap;
        }
        return hi;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
    }
}

⚠️ Common Pitfalls & Tips

This tries every integer from max to sum. It's TLE for large inputs. Binary Search on Answer reduces this from O(Sum) iterations to O(log(Sum)) iterations.

Approach 2

Level II: Recursive Binary Search on Answer

Intuition

Wrap the binary search logic in a recursive function. The search space is still the same: [max(weights), sum(weights)].

⏱ $O(N \log(Sum))$💾 $O(\log(Sum))$ due to recursion stack.

Detailed Dry Run

lo=10, hi=55. mid=32. feasible? Yes. Recurse [10, 32].

java

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        return search(weights, days, lo, hi);
    }
    private int search(int[] weights, int days, int lo, int hi) {
        if (lo >= hi) return lo;
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) return search(weights, days, lo, mid);
        return search(weights, days, mid + 1, hi);
    }
    private boolean canShip(int[] weights, int days, int cap) {
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { need++; cur = 0; }
            cur += w;
        }
        return need <= days;
    }
}

Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The answer (minimum capacity) lies in the range [max(weights), sum(weights)]. This range is MONOTONE: if capacity C works, C+1 also works. If capacity C doesn't work, C-1 doesn't either. This is the 'feasibility check + binary search' pattern — search for the LEFT boundary of feasible capacities.

⏱ O(N log(Sum)) — binary search * feasibility simulation.💾 O(1) — constant variables.

Detailed Dry Run

weights=[1,2,3,4,5,6,7,8,9,10], days=5. Range: lo=10, hi=55

Step	lo	hi	mid	simulate(mid)	days needed	<=5?	Action
1	10	55	32	[1..6]=21,[7,8]=15,[9]=9,[10]=10	4	Yes	hi=32
2	10	32	21	[1..6]=21,[7,8]=15,[9,10]=19	3	Yes	hi=21
3	10	21	15	[1-5]=15,[6-8]=21 wait 21>15, split...	5	Yes	hi=15
4	10	15	12	[1-5]=15? 15>12, split...	6	No	lo=13
5	13	15	14	simulate → 5 days	Yes	hi=14
6	13	14	13	simulate → 6	No	lo=14
lo==hi==15... → return 15

java

public class Solution {
    private boolean canShip(int[] weights, int days, int cap) {
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { need++; cur = 0; }
            cur += w;
        }
        return need <= days;
    }
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid; // feasible, try smaller
            else lo = mid + 1;                          // not feasible, need larger
        }
        return lo;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
        System.out.println(sol.shipWithinDays(new int[]{3,2,2,4,1,4}, 3));           // 6
    }
}

⚠️ Common Pitfalls & Tips

The search range is [max(weights), sum(weights)]. Use lo < hi (not <=). When feasible, set hi = mid (not mid-1) to keep candidate in range. The feasibility function simulates greedy packing: always add to current day until capacity exceeded, then start new day.

Split Array Largest Sum

Given an integer array nums and an integer k, split the array into k non-empty contiguous subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.

Hard

Examples

Input: nums = [7,2,5,10,8], k = 2
Output: 18

Input: nums = [1,2,3,4,5], k = 2
Output: 9

Approach 1

Level I: Dynamic Programming

Intuition

Try all possible ways to split the array using recursion with memoization. dp[i][j] represents the minimum largest sum for the subarray nums[i:] split into j parts.

⏱ $O(N^2 \\cdot K)$💾 $O(N \\cdot K)$

Detailed Dry Run

nums = [7,2,5], k=2

Split at index 1: max(7, 2+5=7) = 7
Split at index 2: max(7+2=9, 5) = 9 Min results: 7.

java

class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length, pSum[] = new int[n+1];
        for (int i=0; i<n; i++) pSum[i+1] = pSum[i] + nums[i];
        return solve(0, k, n, pSum, new Integer[n][k+1]);
    }
    private int solve(int i, int k, int n, int[] pSum, Integer[][] memo) {
        if (k == 1) return pSum[n] - pSum[i];
        if (memo[i][k] != null) return memo[i][k];
        int res = Integer.MAX_VALUE;
        for (int j=i; j<=n-k; j++) {
            res = Math.min(res, Math.max(pSum[j+1]-pSum[i], solve(j+1, k-1, n, pSum, memo)));
        }
        return memo[i][k] = res;
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The minimum largest sum ranges from max(nums) to sum(nums). This range is monotonic: if a max-sum $X$ is feasible with $k$ splits, $X+1$ is also feasible. We binary search for the smallest $X$ .

⏱ $O(N \\cdot \\log(Sum))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Count	Decision
1	10	32	21	2	R = 21
2	10	21	15	3	L = 16
3	16	21	18	2	R = 18
Exit	-	-	-	-	Return 18

java

class Solution {
    public int splitArray(int[] nums, int k) {
        int l = 0, r = 0;
        for (int n : nums) { l = Math.max(l, n); r += n; }
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (can(nums, k, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean can(int[] nums, int k, int limit) {
        int count = 1, sum = 0;
        for (int n : nums) {
            if (sum + n > limit) { count++; sum = 0; }
            sum += n;
        }
        return count <= k;
    }
}

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be $O(\\log (m+n))$ .

Hard

Examples

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000

Approach 1

Level I: Merge and Find

Intuition

Use the merge step of merge sort to combine the two arrays into one sorted array. Then find the middle element(s).

⏱ $O(M + N)$💾 $O(M + N)$

Detailed Dry Run

nums1 = [1,3], nums2 = [2] Merged: [1,2,3]. n=3. Median: Index 1 (Value 2).

java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) merged[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
        int total = m + n;
        if (total % 2 == 1) return merged[total / 2];
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
}

Approach 2

Level II: Recursive K-th Element

Intuition

Find the $k$ -th smallest element in two sorted arrays by comparing the middle elements of each array (divided by 2 at each step).

⏱ $O(\log(M+N))$💾 $O(\log(M+N))$ due to recursion stack.

Detailed Dry Run

Find 5th element in [1,3,5,...] and [2,4,6,...]. Compare 2nd elements...

java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        if (n % 2 == 1) return getKth(nums1, 0, nums2, 0, n / 2 + 1);
        return (getKth(nums1, 0, nums2, 0, n / 2) + getKth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
    }
    private int getKth(int[] a, int aS, int[] b, int bS, int k) {
        if (aS >= a.length) return b[bS + k - 1];
        if (bS >= b.length) return a[aS + k - 1];
        if (k == 1) return Math.min(a[aS], b[bS]);
        int aMid = aS + k/2 - 1 < a.length ? a[aS + k/2 - 1] : Integer.MAX_VALUE;
        int bMid = bS + k/2 - 1 < b.length ? b[bS + k/2 - 1] : Integer.MAX_VALUE;
        if (aMid < bMid) return getKth(a, aS + k/2, b, bS, k - k/2);
        return getKth(a, aS, b, bS + k/2, k - k/2);
    }
}

Approach 3

Level III: Optimal (Binary Search on Partitions)

Intuition

We can binary search for the correct partition point in the smaller array. A partition is correct if all elements on the left side are smaller than all elements on the right side.

⏱ $O(\\log(\\min(M, N)))$💾 $O(1)$

Detailed Dry Run

nums1 = [1,3], nums2 = [2]

BS on nums1. Low=0, High=2. i=1. j = (2+1+1)/2 - 1 = 1.
LeftA=1, RightA=3, LeftB=2, RightB=inf.
LeftA <= RightB (1 <= inf) and LeftB <= RightA (2 <= 3). Correct!
Median: max(1, 2) = 2.0.

java

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        if (A.length > B.length) return findMedianSortedArrays(B, A);
        int m = A.length, n = B.length;
        int low = 0, high = m;
        while (low <= high) {
            int i = low + (high - low) / 2;
            int j = (m + n + 1) / 2 - i;
            int LA = (i == 0) ? Integer.MIN_VALUE : A[i - 1];
            int RA = (i == m) ? Integer.MAX_VALUE : A[i];
            int LB = (j == 0) ? Integer.MIN_VALUE : B[j - 1];
            int RB = (j == n) ? Integer.MAX_VALUE : B[j];
            if (LA <= RB && LB <= RA) {
                if ((m + n) % 2 == 0) return (Math.max(LA, LB) + Math.min(RA, RB)) / 2.0;
                return Math.max(LA, LB);
            } else if (LA > RB) high = i - 1;
            else low = i + 1;
        }
        return 0.0;
    }
}

Find K-th Smallest Pair Distance

The distance of a pair of integers a and b is defined as the absolute difference between a and b. Given an integer array nums and an integer k, return the k-th smallest distance among all the pairs nums[i] and nums[j] where $0 \\le i < j < N$ .

Hard

Examples

Input: nums = [1,3,1], k = 1
Output: 0

Input: nums = [1,1,1], k = 2
Output: 0

Approach 1

Level I: Brute Force (Iterate All Pairs)

Intuition

Calculate every possible pair distance, store them, and pick the $k$ -th smallest.

⏱ $O(N^2)$💾 $O(N^2)$

Detailed Dry Run

nums = [1,3,1], k=1 Distances: |1-3|=2, |1-1|=0, |3-1|=2. Sorted: [0, 2, 2]. Result: 0.

java

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length, ds[] = new int[n * (n - 1) / 2], idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) ds[idx++] = Math.abs(nums[i] - nums[j]);
        }
        Arrays.sort(ds);
        return ds[k - 1];
    }
}

Approach 2

Level II: Min-Heap (Heap of Pairs)

Intuition

Sort the array. Adjacent pairs $(i, i+1)$ have the smallest gaps. Use a min-heap to explore larger gaps $(i, j+1)$ sequentially.

⏱ $O((N + K) \\log N)$💾 $O(N)$

Detailed Dry Run

nums=[1,1,3], k=1 Heap: (0,1) dist 0, (1,2) dist 2. Pop (0,1). Result 0.

java

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (nums[a[1]]-nums[a[0]]) - (nums[b[1]]-nums[b[0]]));
        for (int i = 0; i < nums.length-1; i++) pq.offer(new int[]{i, i+1});
        for (int i = 0; i < k-1; i++) {
            int[] cur = pq.poll();
            if (cur[1]+1 < nums.length) pq.offer(new int[]{cur[0], cur[1]+1});
        }
        int[] res = pq.poll();
        return nums[res[1]] - nums[res[0]];
    }
}

Approach 3

Level III: Optimal (Binary Search + Sliding Window)

Intuition

Binary search for the distance $D$ such that there are at least $k$ pairs with distance $\\le D$ . Counting is done in $O(N)$ using two pointers.

⏱ $O(N \\log N + N \\log(Max))$💾 $O(1)$

Detailed Dry Run

nums=[1,1,3], k=1. Sorted: [1,1,3]. L=0, R=2. Mid=1. Count=2 >= 1. R=1. L=0, R=1. Mid=0. Count=1 >= 1. R=0. Result 0.

java

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length-1]-nums[0];
        while (l < r) {
            int mid = l + (r-l)/2;
            if (count(nums, mid) >= k) r = mid; else l = mid + 1;
        }
        return l;
    }
    int count(int[] nums, int d) {
        int c = 0, l = 0;
        for (int r = 0; r < nums.length; r++) {
            while (nums[r]-nums[l] > d) l++;
            c += r - l;
        }
        return c;
    }
}

Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the $i$ -th bus to complete one trip. Return the minimum time required for all buses to complete at least totalTrips trips.

Medium

Examples

Input: time = [1,2,3], totalTrips = 5
Output: 3

Approach 1

Level I: Brute Force

Intuition

Iterate from time $T=1$ upwards and check if the total trips $\\sum \\lfloor T / time[i] \\rfloor$ reaches totalTrips.

⏱ $O(MinTime \\cdot TotalTrips)$💾 $O(1)$

Detailed Dry Run

time = [1,2,3], totalTrips = 5

T=1: trips = 1/1 + 1/2 + 1/3 = 1 < 5
T=2: trips = 2/1 + 2/2 + 2/3 = 3 < 5
T=3: trips = 3/1 + 3/2 + 3/3 = 5 >= 5. Return 3.

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long t = 1;
        while (true) {
            long trips = 0;
            for (int b : time) trips += t / b;
            if (trips >= totalTrips) return t;
            t++;
        }
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The number of trips is monotone relative to time. We can binary search the answer range [1, min(time) * totalTrips].

⏱ $O(N \\cdot \\log(MinTime \\cdot TotalTrips))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Trips	Decision
1	1	5	3	5	R = 3
2	1	3	2	3	L = 3
Exit	-	-	-	-	Return 3

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long l = 1, r = (long)time[0] * totalTrips;
        for (int t : time) r = Math.min(r, (long)t * totalTrips);
        while (l < r) {
            long m = l + (r - l) / 2, trips = 0;
            for (int t : time) trips += m / t;
            if (trips >= totalTrips) r = m; else l = m + 1;
        }
        return l;
    }
}

Maximum Running Time of N Computers

You have n computers and batteries. Return the maximum number of minutes you can run all n computers simultaneously.

Hard

Examples

Input: n = 2, batteries = [3,3,3]
Output: 4

Approach 1

Level I: Brute Force

Intuition

The maximum possible time is the average energy: $\\sum(batteries) / n$ .

⏱ $O(M)$💾 $O(1)$

Detailed Dry Run

n=2, batteries=[3,3,3]. Sum=9. Average=4.5. Result: 4.

java

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long sum = 0;
        for (int b : batteries) sum += b;
        return sum / n;
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

For a time $T$ , a battery with capacity $B$ can contribute at most $\\min(B, T)$ minutes. Check if $\\sum \\min(B_i, T) \\ge n \\times T$ .

⏱ $O(M \\log(Sum/N))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Energy	Needed	Decision
1	1	4	3	9	6	L = 3
2	3	4	4	9	8	L = 4
Exit	-	-	-	-	-	Return 4

java

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long l = 1, r = 0;
        for (int b : batteries) r += b;
        r /= n;
        while (l < r) {
            long m = l + (r - l + 1) / 2;
            if (can(n, batteries, m)) l = m; else r = m - 1;
        }
        return l;
    }
    private boolean can(int n, int[] b, long t) {
        long energy = 0;
        for (int x : b) energy += Math.min((long)x, t);
        return energy >= (long)n * t;
    }
}

Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the k-th smallest element.

Medium

Examples

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13

Approach 1

Level I: Min-Heap (K-Way Merge)

Intuition

This is equivalent to merging $N$ sorted lists. Use a min-heap to pick the smallest available element $k$ times.

⏱ $O(K \\log N)$💾 $O(N)$

Detailed Dry Run

matrix = [[1,5,9],[10,11,13],[12,13,15]], k=8 Heap: [(1,0,0), (10,1,0), (12,2,0)] Pop (1,0,0) -> Push (5,0,1). Pop (5,0,1) -> Push (9,0,2). ... 8th pop = 13.

java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < matrix.length; i++) pq.offer(new int[]{matrix[i][0], i, 0});
        for (int i = 0; i < k - 1; i++) {
            int[] cur = pq.poll();
            if (cur[2] + 1 < matrix.length) pq.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
        }
        return pq.poll()[0];
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The value space is [matrix[0][0], matrix[n-1][n-1]]. For a value mid, we can count elements $\\le$ mid in $O(N)$ by starting from the bottom-left corner.

⏱ $O(N \\cdot \\log(Max - Min))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Count	Decision
1	1	15	8	2	L = 9
2	9	15	12	6	L = 13
3	13	15	14	9	R = 14
Exit	-	-	-	-	Return 13

java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length, l = matrix[0][0], r = matrix[n - 1][n - 1];
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (count(matrix, mid) < k) l = mid + 1; else r = mid;
        }
        return l;
    }
    int count(int[][] matrix, int mid) {
        int n = matrix.length, c = 0, j = n - 1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && matrix[i][j] > mid) j--;
            c += (j + 1);
        }
        return c;
    }
}

Swim in Rising Water

On an $N \times N$ grid, elevation at (i, j) is grid[i][j]. Return the least time $T$ such that you can swim from top-left to bottom-right.

Hard

Examples

Input: grid = [[0,2],[1,3]]
Output: 3

Approach 1

Level I: Dijkstra (Min-Max Path)

Intuition

This is a variant of shortest path where the 'cost' of a path is $\\max($ elevations on path $)$ . Dijkstra's algorithm with a min-priority queue works perfectly.

⏱ $O(N^2 \\log N)$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]].

Start (0,0) elev 0.
Neighbors: (0,1) cost 2, (1,0) cost 1.
Smallest max: (1,0) cost 1.
Neighbor of (1,0) is (1,1) cost 3.
Result: 3.

java

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        boolean[][] vis = new boolean[n][n];
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (vis[cur[1]][cur[2]]) continue; vis[cur[1]][cur[2]] = true;
            if (cur[1] == n - 1 && cur[2] == n - 1) return cur[0];
            for (int[] d : dirs) {
                int ni = cur[1] + d[0], nj = cur[2] + d[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !vis[ni][nj])
                    pq.offer(new int[]{Math.max(cur[0], grid[ni][nj]), ni, nj});
            }
        }
        return -1;
    }
}

Approach 2

Level II: Optimal (Union Find / Kruskal's)

Intuition

Treat the grid as a graph where each edge has a weight equal to the maximum elevation of its two endpoints. Sort all possible edge weights (or cell elevations). Add cells one by one in increasing order of elevation and connect them with their visited neighbors. The first time the top-left and bottom-right are in the same component, the current elevation is the answer.

⏱ $O(N^2 \\log N^2)$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]].

Cells sorted by elevation: (0,0):0, (1,0):1, (0,1):2, (1,1):3.
Add (0,0). Add (1,0), connect to (0,0).
Add (0,1), connect to (0,0).
Add (1,1), connect to (1,0) and (0,1).
(0,0) and (1,1) are connected. Result: 3.

java

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] positions = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) positions[grid[i][j]] = new int[]{i, j};
        }
        UnionFind uf = new UnionFind(n * n);
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int t = 0; t < n * n; t++) {
            int r = positions[t][0], c = positions[t][1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] <= t) {
                    uf.union(r * n + c, nr * n + nc);
                }
            }
            if (uf.connected(0, n * n - 1)) return t;
        }
        return -1;
    }
    class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        void union(int i, int j) {
            int rootI = find(i), rootJ = find(j);
            if (rootI != rootJ) parent[rootI] = rootJ;
        }
        boolean connected(int i, int j) { return find(i) == find(j); }
    }
}

Approach 3

Level III: Optimal (Binary Search + DFS/BFS)

Intuition

The answer $T$ lies in $[0, N^2-1]$ . For a fixed $T$ , we check if a path exists using only squares with elevation $\\le T$ using BFS/DFS.

⏱ $O(N^2 \\cdot \\log(N^2))$💾 $O(N^2)$

Detailed Dry Run

grid = [[0,2],[1,3]]. BS on range [0, 3]. Try T=2: Path (0,0)->(1,0) works, but (1,0) neighbors are (1,1) elev 3 > 2. Fails. Try T=3: Path (0,0)->(1,0)->(1,1) works! Possible. Result: 3.

java

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length, l = grid[0][0], r = n * n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canReach(grid, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean canReach(int[][] g, int t) {
        int n = g.length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        boolean[][] vis = new boolean[n][n]; vis[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n-1 && cur[1] == n-1) return true;
            for (int[] d : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
                int ni = cur[0]+d[0], nj = cur[1]+d[1];
                if (ni>=0 && ni<n && nj>=0 && nj<n && !vis[ni][nj] && g[ni][nj] <= t) {
                    vis[ni][nj] = true; q.offer(new int[]{ni, nj});
                }
            }
        }
        return false;
    }
}

Minimum Number of Days to Make m Bouquets

Return the minimum number of days $D$ such that you can make $m$ bouquets using $k$ adjacent flowers each. Each bouquet must consist of $k$ adjacent flowers.

Medium

Examples

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3

Approach 1

Level I: Brute Force (Iterate Days)

Intuition

Try every possible day from $\\min(bloomDay)$ to $\\max(bloomDay)$ . For each day, check if it's possible to form $m$ bouquets.

⏱ $O(Range \\cdot N)$💾 $O(1)$

Detailed Dry Run

bloomDay = [1,10,3,10,2], m=3, k=1. Sorted unique days: [1,2,3,10]. Day 1: 1 bouquet. Day 2: 2 bouquets. Day 3: 3 bouquets. Return 3.

java

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int maxD = 0; for (int d : bloomDay) maxD = Math.max(maxD, d);
        for (int d = 1; d <= maxD; d++) {
            if (canMake(bloomDay, m, k, d)) return d;
        }
        return -1;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouquets = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouquets++; count = 0; } } else count = 0;
        }
        return bouquets >= m;
    }
}

Approach 2

Level II: Optimal (Optimization with Sorted Days)

Intuition

Instead of checking every day from 1 to maxD, only check days where at least one flower blooms. These are the unique values in bloomDay.

⏱ $O(N \\log N + N \\cdot \\text{UniqueDays})$💾 $O(N)$

Detailed Dry Run

bloomDay = [1,10,3,10,2], m=3, k=1. Unique days sorted: [1, 2, 3, 10]. Check 1: 1 (fail), 2: 2 (fail), 3: 3 (pass). Result 3.

java

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int[] sortedDays = Arrays.stream(bloomDay).distinct().sorted().toArray();
        for (int d : sortedDays) {
            if (canMake(bloomDay, m, k, d)) return d;
        }
        return -1;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouquets = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouquets++; count = 0; } } else count = 0;
        }
        return bouquets >= m;
    }
}

Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The number of bouquets possible is a monotonic function of days. We can binary search the result in the range $[\\min(bloomDay), \\max(bloomDay)]$ .

⏱ $O(N \\log(Max - Min))$💾 $O(1)$

Detailed Dry Run

bloomDay = [1,10,3,10,2], m=3, k=1. Range [1, 10].

Mid 5: [B, No, B, No, B] -> 3 bouquets. OK, R=5.
Mid 2: [B, No, No, No, B] -> 2 bouquets. Too few, L=3.
Mid 3: [B, No, B, No, B] -> 3 bouquets. OK, R=3. Result: 3.

java

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int l = 1, r = 1000000000;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canMake(bloomDay, m, k, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouq = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouq++; count = 0; } } else count = 0;
        }
        return bouq >= m;
    }
}

Find the Smallest Divisor Given a Threshold

Given an array nums and an integer threshold, find the smallest divisor $d$ such that the sum of the division results (rounded up) is $\\le$ threshold.

Medium

Examples

Input: nums = [1,2,5,9], threshold = 6
Output: 5

Approach 1

Level I: Brute Force

Intuition

Try every divisor $d$ from 1 up to $\\max(nums)$ and check the sum condition.

⏱ $O(MaxValue \\cdot N)$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6.

d=4: ceil(1/4)+ceil(2/4)+ceil(5/4)+ceil(9/4) = 1+1+2+3 = 7 > 6.
d=5: ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5) = 1+1+1+2 = 5 <= 6. Return 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int maxVal = 0; for (int n : nums) maxVal = Math.max(maxVal, n);
        for (int d = 1; d <= maxVal; d++) {
            int sum = 0;
            for (int n : nums) sum += (n + d - 1) / d;
            if (sum <= threshold) return d;
        }
        return maxVal;
    }
}

Approach 2

Level II: Optimal (Mathematical Bound Optimization)

Intuition

Instead of starting the brute force from $d=1$ , we can observe that $d$ must be at least $\\lceil \\frac{\\sum nums}{\\text{threshold}} \\rceil$ . This provides a tighter lower bound for our search.

⏱ $O((MaxValue - LowerBound) \\cdot N)$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6. Sum=17. Lower bound $d = \\lceil 17/6 \\rceil = 3$ .

d=3: sum = 7 > 6.
d=4: sum = 7 > 6.
d=5: sum = 5 <= 6. Return 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        long sumAll = 0; for (int n : nums) sumAll += n;
        int start = (int)Math.ceil((double)sumAll / threshold);
        for (int d = start; ; d++) {
            int sum = 0;
            for (int n : nums) sum += (n + d - 1) / d;
            if (sum <= threshold) return d;
        }
    }
}

Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The sum of division results is a non-increasing function of the divisor $d$ . Binary search in the range $[1, \\max(nums)]$ .

⏱ $O(N \\log(MaxValue))$💾 $O(1)$

Detailed Dry Run

nums=[1,2,5,9], threshold=6. [1, 9].

Mid 5: sum = 5 <= 6. R=5.
Mid 2: sum = 1+1+3+5 = 10 > 6. L=3.
Mid 3: sum = 1+1+2+3 = 7 > 6. L=4.
Mid 4: sum = 1+1+2+3 = 7 > 6. L=5. Result 5.

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int l = 1, r = 1000000;
        for (int n : nums) r = Math.max(r, n);
        while (l < r) {
            int mid = l + (r - l) / 2, sum = 0;
            for (int n : nums) sum += (n + mid - 1) / mid;
            if (sum <= threshold) r = mid; else l = mid + 1;
        }
        return l;
    }
}

Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards will come back in h hours. Koko can decide her bananas-per-hour eating speed 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 will not eat any more bananas during this hour. Return the minimum integer k such that she can eat all the bananas within h hours.

Medium

Examples

Input: piles = [3,6,7,11], h = 8
Output: 4

Approach 1

Level I: Brute Force

Intuition

Try every speed k starting from 1 upwards until we find one that allows Koko to finish in h hours.

⏱ $O(Max(Piles) \cdot N)$💾 $O(1)$

Detailed Dry Run

piles=[3,6,7,11], h=8. Try k=1, 2, 3... until 4 fits.

java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        for (int k = 1; ; k++) {
            long hours = 0;
            for (int p : piles) hours += (p + k - 1) / k;
            if (hours <= h) return k;
        }
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The time spent eating is a monotonic function of the speed k. We can binary search in the range [1, max(piles)].

⏱ $O(N \cdot \log(Max))$💾 $O(1)$

Detailed Dry Run

piles=[3,6,7,11], h=8. L=1, R=11.

Mid 6: 1+1+2+2 = 6 <= 8. R=6.
Mid 3: 1+2+3+4 = 10 > 8. L=4.
Mid 5: 1+2+2+3 = 8 <= 8. R=5.
Mid 4: 1+2+2+3 = 8 <= 8. R=4. Result 4.

java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = 1000000000;
        for (int p : piles) if (p > r) r = p;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canFinish(piles, h, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    private boolean canFinish(int[] piles, int h, int k) {
        long total = 0;
        for (int p : piles) total += (p + k - 1) / k;
        return total <= h;
    }
}

← Previous TopicLinked List Patterns

Next Topic →Dynamic Programming

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.