Every question from the "Binary search" block of your DSA Pattern Sheet (#21 to #33). Each one goes brute force → better → best, with the code, time and space, the Java you pick up along the way, and the cost of every collection or API call used. After the main approaches, an Other approaches block adds techniques from other topics, because those questions won't come back. Where only two real approaches exist, the note says so.
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1; // low = insert positionBoth ends are candidates, so loop while low <= high. Always move past mid (you already checked it).
int low = 0, high = n; // n means "none"
while (low < high) {
int mid = low + (high - low) / 2;
if (condition(mid)) high = mid; // keep mid
else low = mid + 1; // mid fails
}
return low; // the first trueUsed by: Search Insert, Find Min in Rotated, Find Peak. Needs a condition that goes false, false, ..., true, true.
int low = minAnswer, high = maxAnswer;
while (low < high) {
int mid = low + (high - low) / 2;
if (works(mid)) high = mid; // try smaller
else low = mid + 1; // go bigger
}
return low;Used by: Koko, Ship Packages, Bouquets, Split Array. Steps: (1) range of answers, (2) greedy yes/no check works(x), (3) Template 2. Valid only if "works at x" implies "works at every bigger x".
while (low <= high), high = mid - 1 | Looking for one exact value. Template 1. |
while (low < high), high = mid | Looking for a boundary (first true) or a minimum. Templates 2 and 3. |
low = mid (no +1) | Avoid. Because mid rounds down it can loop forever. |
| Each step halves the range | O(log n) |
| Binary search on an array | O(log n) |
| Search on the answer with an O(n) check | O(n log range) |
Arrays.binarySearch(a, key) (sorted only) | O(log n) |
| Recursive version: stack depth | O(log n) |
Arrays.binarySearch returns the index if found, otherwise -(insertionPoint) - 1. With duplicates it may return any matching index. | |
a[i], a.length, matrix[r][c] | O(1) |
Arrays.sort(int[]) | O(n log n) |
clone(), new int[n] | O(n) |
Math.max, Math.min, %, / | O(1) |
Math.sqrt(x) (double) | O(1) |
Midpoint: use low + (high - low) / 2, never (low + high) / 2. | |
Products and sums: cast BEFORE multiplying: (long) mid * mid. (long) (mid * mid) is too late. | |
Ceiling division: (x - 1) / y + 1 for positive ints, safer than (x + y - 1) / y. | |
Integer.MAX_VALUE is about 2.1 × 10⁹. int overflow wraps to negative silently. |
All snippets assume import java.util.*; and are static methods, so you can paste them into a class and call them from main.
Spot it: Sorted array, find a value. Each look at the middle element throws away half of what is left.
Scan left to right until you find it. Ignores that the array is sorted.
static int searchBrute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) return i;
}
return -1;
}Look at the middle. Equal: done. Middle too small: the answer can only be to the right, so search mid + 1 .. high. Middle too big: search low .. mid - 1. Stop when low > high, the range is empty. Correct and short, but every halving is a new method call on the stack.
static int searchBetter(int[] nums, int target) {
return searchRec(nums, target, 0, nums.length - 1);
}
private static int searchRec(int[] nums, int target, int low, int high) {
if (low > high) return -1; // empty range: not found
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) return searchRec(nums, target, mid + 1, high);
return searchRec(nums, target, low, mid - 1);
}Same logic as a loop: no stack, O(1) space. This is Template 1 on the cheat sheet. Learn it until you can write it with your eyes closed, because every other question in this block is a variation of it.
static int searchBest(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Java ships the algorithm. It returns the index if found, otherwise a negative number: -(insertionPoint) - 1. Check >= 0 for found. With duplicates it may return any one of them.
When it fits: Fine in real code. In an interview you're expected to write the loop yourself.
static int searchLibrary(int[] nums, int target) {
int idx = Arrays.binarySearch(nums, target);
return idx >= 0 ? idx : -1; // negative means not found
}low + (high - low) / 2, not (low + high) / 2low and high are both near 2 billion, low + high overflows int and goes negative. This form can't. (low + high) >>> 1 is the other safe version.while (low <= high)low == high) must still be checked. With < you would skip the last element.mid + 1 and mid - 1mid, so exclude it. Writing low = mid here can loop forever.(0 + 1) / 2 = 0. mid leans left when the range has an even length. This is why templates that use low = mid need extra care.Arrays.binarySearch(arr, key)-(insertionPoint) - 1 (always negative). Requires a sorted array or the result is undefined.| Array access nums[mid] | O(1) |
| Arrays.binarySearch | O(log n) |
| Recursion depth | O(log n) stack frames |
Remember: Binary search needs only one thing: a sorted order (or a yes/no that flips once). Everything else in this block is that idea in a costume.
Spot it: Binary search, but when the value is missing you return where it would go. That is exactly the 'first index with a value >= target' question, called lower bound.
Walk from the left and return the first index whose value is >= target. If none, the target belongs at the end.
static int searchInsertBrute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i;
}
return nums.length;
}lowTime O(log n)Space O(1)Run the normal search. If it never finds the target, the loop ends with low sitting exactly where the target belongs: everything left of low is smaller, everything from low on is bigger.
static int searchInsertBetter(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low; // not found: low is the insertion point
}Search for the FIRST position where the condition nums[i] >= target becomes true. high starts at n, because 'insert at the end' is a legal answer. If mid satisfies the condition it might be the answer, so keep it (high = mid). If not, it's too small (low = mid + 1). This is Template 2 on the cheat sheet and it's the one used in Koko, Ship Packages, Bouquets and Split Array.
static int searchInsertBest(int[] nums, int target) {
int low = 0, high = nums.length; // high = n: "insert at the end" is allowed
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] >= target) high = mid; // mid might be the answer, keep it
else low = mid + 1; // mid is too small
}
return low;
}When the value is missing, Arrays.binarySearch returns -(insertionPoint) - 1. Undo that formula to get the insertion point: -idx - 1.
When it fits: Good to know the encoding. The distinct-values guarantee in this problem makes it safe.
static int searchInsertLibrary(int[] nums, int target) {
int idx = Arrays.binarySearch(nums, target);
if (idx >= 0) return idx;
return -idx - 1; // decode: -(insertionPoint) - 1
}low <= high vs low < high<= is for 'find this exact value'. < is for 'find the first place where something becomes true'. In the second style the loop stops when low == high and that single index is the answer.high = n vs high = n - 1[0, n]. You never read nums[n], because mid is always less than high.Arrays.binarySearch returns -(insertionPoint) - 1 when missing. To get the insertion point: int idx = Arrays.binarySearch(a, t); return idx >= 0 ? idx : -idx - 1;.| Array access nums[mid] | O(1) |
| Arrays.binarySearch | O(log n) |
Remember: 'Where does it go' and 'first element >= x' are the same question. Lower bound is the most reusable binary search you will write.
Spot it: Find the biggest integer r with r * r <= x. 'Biggest number that still passes a test' is a binary search on the answer: small numbers pass, big numbers fail, and it flips once.
Only two real tiers here: loop up, or binary search the answer. Newton's method and Math.sqrt are listed below as extras.
Try 0, 1, 2, ... until the square passes x. Use long for the square, or i * i overflows int for big x.
static int mySqrtBrute(int x) {
long i = 0;
while ((i + 1) * (i + 1) <= x) {
i++;
}
return (int) i;
}The answer is between 0 and x. Pick mid. If mid * mid is too big, go left. If it's small enough, mid is a valid answer, so remember it and look for a bigger one on the right. When the loop ends, the last remembered value is the largest that fits.
static int mySqrtBest(int x) {
int low = 0, high = x;
int ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
long square = (long) mid * mid; // long: mid * mid can overflow int
if (square == x) return mid;
if (square < x) {
ans = mid; // mid fits, try something bigger
low = mid + 1;
} else {
high = mid - 1; // mid is too big
}
}
return ans;
}Start with r = x and repeatedly replace r with the average of r and x / r. The estimate drops fast: the number of correct digits roughly doubles each round. Stop when r * r <= x.
When it fits: Very fast in practice (about 5 to 6 rounds even for the largest int). Harder to explain than binary search, so know it exists.
static int mySqrtNewton(int x) {
if (x == 0) return 0;
long r = x;
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int) r;
}Take the floating-point square root and cut off the decimals. Correct for every int because a double holds integers up to 2^53 exactly.
When it fits: Interviewers normally ban it for this question. Fine in real code.
static int mySqrtLibrary(int x) {
return (int) Math.sqrt(x);
}(long) mid * mid makes the multiplication happen in long. (long) (mid * mid) multiplies as int first, overflows, and only then converts. Wrong answer with no error.ans records the best passing valueans when the test passes and keep going.Math.sqrt returns a double(int) Math.sqrt(x). For every int x the floor is correct. Interviewers usually ban it, but know it exists.i++ on a longint. Use long for counters whose squares might be large.| Integer / long arithmetic | O(1) |
| Math.sqrt | O(1) |
Remember: When the problem says 'largest x such that something holds' and the thing holds for small x and stops holding for big x, binary search the answer.
Spot it: Sorted array with duplicates. You need the first and the last index of a value. Two binary searches: one that keeps going left after a hit, one that keeps going right.
Scan once, remember the first index where you see the target and the latest one.
static int[] searchRangeBrute(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};
}Binary search finds ANY occurrence. Then walk left and right while the neighbour is the same value. Fast when the value appears a few times, but if the whole array is one value it still walks the whole array: O(n) worst case.
static int[] searchRangeBetter(int[] nums, int target) {
int low = 0, high = nums.length - 1, found = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) { found = mid; break; }
if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
if (found == -1) return new int[]{-1, -1};
int left = found, right = found;
while (left > 0 && nums[left - 1] == target) left--;
while (right < nums.length - 1 && nums[right + 1] == target) right++;
return new int[]{left, right};
}Two small searches that never stop early, they always run until low and high cross. findFirst: go left whenever nums[mid] >= target (high = mid - 1), otherwise go right. When the loop ends, low is the first index with a value >= target, so if nums[low] equals the target that's the first occurrence. findLast: go left only when nums[mid] > target, otherwise go right (low = mid + 1). When it ends, high is the last index with a value <= target, so if nums[high] equals the target that's the last occurrence. The only difference between the two is >= vs >. searchRange calls findFirst, and only if the target exists does it call findLast.
static int findFirst(int[] nums, int target) {
int n = nums.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] >= target) high = mid - 1; // equal also goes left: we want the FIRST one
else low = mid + 1;
}
if (low < n && nums[low] == target) { // low = first index with value >= target
return low;
}
return -1;
}
static int findLast(int[] nums, int target) {
int n = nums.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] > target) high = mid - 1; // only strictly bigger goes left
else low = mid + 1; // equal goes right: we want the LAST one
}
if (high >= 0 && nums[high] == target) { // high = last index with value <= target
return high;
}
return -1;
}
static int[] searchRangeBest(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int first = findFirst(nums, target);
if (first == -1) return new int[]{-1, -1};
int last = findLast(nums, target);
return new int[]{first, last};
}Write one function lowerBound(x) = the first index with nums[i] >= x. The first occurrence of target is lowerBound(target). The last occurrence is lowerBound(target + 1) - 1: one step before the first element bigger than target. Only one search loop to remember.
When it fits: Neat and short. target + 1 can overflow if target is Integer.MAX_VALUE, which the problem's limits rule out.
static int[] searchRangeLowerBound(int[] nums, int target) {
int first = lowerBound(nums, target);
if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
int last = lowerBound(nums, target + 1) - 1;
return new int[]{first, last};
}
private static int lowerBound(int[] nums, int x) { // first index with nums[i] >= x
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] >= x) high = mid;
else low = mid + 1;
}
return low;
}return inside the looplow and high cross, then look at where they landed. After findFirst's loop, low is the first index with value >= target. After findLast's loop, high is the last index with value <= target.>= vs > is the whole differencenums[low] == target confirms it exists. In findLast, high ends at -1 if every element is bigger than the target, so check high >= 0 before reading nums[high].new int[]{a, b}. For more complex pairs, use a small class or int[].&&left > 0 && nums[left - 1] == target: if the first part is false, the second isn't evaluated, so you never read nums[-1]. Order matters.| Array access nums[mid] | O(1) |
| new int[]{a, b} | O(1) |
Remember: Binary search can find a boundary, not just a match. Keep the hit, then push toward the side you care about.
Spot it: A sorted array that was rotated, like [4,5,6,7,0,1,2]. It is not sorted overall, but at every mid at least one half is sorted. Check which half is sorted, see if the target is inside it, and discard the other half.
Linear scan.
static int searchRotatedBrute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) return i;
}
return -1;
}Step 1: binary search for the index of the smallest value (the rotation point, same as the next question). Step 2: binary search the whole array as if it were un-rotated, by turning each 'virtual' index into a real one with (mid + pivot) % n. Two clean binary searches, no tricky branching.
static int searchRotatedBetter(int[] nums, int target) {
int n = nums.length;
int low = 0, high = n - 1;
while (low < high) { // find the index of the smallest value
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]) low = mid + 1;
else high = mid;
}
int pivot = low;
low = 0;
high = n - 1;
while (low <= high) { // binary search the "virtual" sorted array
int mid = low + (high - low) / 2;
int real = (mid + pivot) % n;
if (nums[real] == target) return real;
if (nums[real] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}At each mid: if nums[low] <= nums[mid], the left half is sorted. If the target lies inside that sorted range, go left, otherwise go right. If the left half isn't sorted, the right half is: check the same way. One loop, same O(log n), and it's the version interviewers expect.
static int searchRotatedBest(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[low] <= nums[mid]) { // left half is sorted
if (nums[low] <= target && target < nums[mid]) high = mid - 1; // target is in it
else low = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[high]) low = mid + 1; // target is in it
else high = mid - 1;
}
}
return -1;
}Nothing else to add that's genuinely different. The pivot-then-search and sorted-half versions above are the two standard ideas.
(mid + pivot) % n<= in nums[low] <= nums[mid]low == mid the left 'half' is a single element, which is trivially sorted. With < that case goes to the wrong branch.nums[low] == nums[mid] == nums[high] is ambiguous, so you shrink by one (low++, high--) and the worst case becomes O(n).| Array access | O(1) |
| Integer % and / | O(1) |
Remember: In a rotated sorted array, one half is always sorted. Find it, decide, discard.
Spot it: Rotated sorted array, distinct values, find the smallest. The smallest value is the rotation point. Compare mid with the LAST element: if nums[mid] is bigger, the drop is to the right; otherwise the minimum is at mid or to the left.
Only two real tiers: scan, or binary search. A faster variant with an early exit is listed as an extra.
Look at every element, keep the smallest.
static int findMinBrute(int[] nums) {
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < min) min = nums[i];
}
return min;
}If nums[mid] > nums[high], the array 'breaks' somewhere after mid, so the minimum is to the right: low = mid + 1. Otherwise mid is on the same sorted stretch as high, so the minimum is at mid or before it: high = mid (keep mid, it could be the answer). The loop is low < high and ends with low == high on the minimum.
static int findMinBest(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]) low = mid + 1; // minimum is to the right of mid
else high = mid; // mid could be the minimum
}
return nums[low];
}If nums[low] < nums[high] the current range isn't rotated at all, so the smallest is nums[low]. Return immediately. Same big-O, but fully sorted input finishes in one step.
When it fits: A small optimisation. The plain version is simpler and just as correct.
static int findMinEarlyExit(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
if (nums[low] < nums[high]) return nums[low]; // this range is sorted
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]) low = mid + 1;
else high = mid;
}
return nums[low];
}nums[high], not nums[low]nums[low] fails when the array isn't rotated at all (it's fully sorted). Comparing with nums[high] handles both cases without a special case.high = mid, never high = mid - 1mid could be the minimum itself. Dropping it would lose the answer.low < high loopnums[low]| Array access | O(1) |
Remember: Searching for a boundary with a low < high loop and high = mid is the first-true template. You will see it again in every answer-search question.
Spot it: Any element bigger than both neighbours counts, and the array is NOT sorted. Binary search still works: at mid, if the next element is bigger you are on an uphill, so a peak must exist to the right. Otherwise a peak exists at mid or to the left.
Check every index against both neighbours. Treat the outside of the array as negative infinity, so the first and last elements only need one neighbour check.
static int findPeakBrute(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
boolean leftOk = (i == 0) || nums[i] > nums[i - 1];
boolean rightOk = (i == n - 1) || nums[i] > nums[i + 1];
if (leftOk && rightOk) return i;
}
return -1;
}Walk until the first nums[i] > nums[i + 1]. Everything before i was going up, so i is a peak. If you never go down, the last element is a peak. Half the comparisons, still linear.
static int findPeakBetter(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) return i; // started going down: i is a peak
}
return nums.length - 1; // went up all the way
}Compare nums[mid] with nums[mid + 1]. Going up: a peak exists to the right (the array has to come down eventually, or it ends, and the end counts as a peak). Going down: mid or something to its left is a peak. Always keep a side that provably contains a peak.
static int findPeakBest(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < nums[mid + 1]) low = mid + 1; // uphill: a peak is to the right
else high = mid; // downhill: mid or left of it
}
return low;
}The biggest element in the array is always a peak: nothing around it can be bigger. Scan for it.
When it fits: Valid, but O(n). It exists as a fallback and as a way to check your binary search in tests.
static int findPeakMax(int[] nums) {
int best = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[best]) best = i;
}
return best;
}nums[mid + 1] is safelow < high, mid < high, so mid + 1 is always a valid index.boolean helper variablesleftOk and rightOk make the edge-of-array conditions readable. The || short-circuits so you never read index -1 or n.| Array access | O(1) |
Remember: Binary search = 'keep a half that must contain an answer'. Sorted order is just one way to get that guarantee.
Spot it: Every row is sorted and each row starts after the previous one ends, so read row by row the whole matrix is ONE sorted list. Binary search it without flattening: index mid lives at row mid / cols, column mid % cols.
Check every cell.
static boolean searchMatrixBrute(int[][] matrix, int target) {
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
if (matrix[r][c] == target) return true;
}
}
return false;
}The only row that can hold the target is the first one whose LAST value is >= target. Find it with a loop over rows, then binary search inside that row.
static boolean searchMatrixBetter(int[][] matrix, int target) {
int cols = matrix[0].length;
for (int r = 0; r < matrix.length; r++) {
if (target <= matrix[r][cols - 1]) { // the only row that can contain it
int low = 0, high = cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (matrix[r][mid] == target) return true;
if (matrix[r][mid] < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
}
return false;
}Pretend there are rows * cols elements in one array. Normal binary search on indices 0 .. rows*cols - 1. To read index mid, convert it: row = mid / cols, column = mid % cols. No flattening, no extra memory.
static boolean searchMatrixBest(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int low = 0, high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int value = matrix[mid / cols][mid % cols]; // 1D index -> 2D cell
if (value == target) return true;
if (value < target) low = mid + 1;
else high = mid - 1;
}
return false;
}First binary search over rows: compare the target with each row's first and last value to pick the one row that can hold it. Then a normal binary search inside that row. Two loops, but each one is easy to reason about with no / and % mapping.
When it fits: O(log m + log n) which is the same as O(log(m · n)). Choose whichever you find easier to write without mistakes.
static boolean searchMatrixTwoSearches(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int low = 0, high = rows - 1, row = -1;
while (low <= high) { // 1) find the row
int mid = low + (high - low) / 2;
if (target < matrix[mid][0]) high = mid - 1;
else if (target > matrix[mid][cols - 1]) low = mid + 1;
else { row = mid; break; }
}
if (row == -1) return false;
low = 0;
high = cols - 1;
while (low <= high) { // 2) search inside that row
int mid = low + (high - low) / 2;
if (matrix[row][mid] == target) return true;
if (matrix[row][mid] < target) low = mid + 1;
else high = mid - 1;
}
return false;
}Start at the top-right cell. If it's bigger than the target, nothing below it in that column can help, so move left. If it's smaller, nothing to its left in that row can help, so move down. Each step removes a whole row or column.
When it fits: Slower here (O(m + n)) but it is THE technique for Search a 2D Matrix II, where rows and columns are sorted but rows are not chained. Worth knowing.
static boolean searchMatrixStaircase(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int r = 0, c = cols - 1; // top-right corner
while (r < rows && c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] > target) c--; // too big: go left
else r++; // too small: go down
}
return false;
}/ and %row = i / cols, col = i % cols. Going back: i = row * cols + col. You'll use this for any grid stored as a flat array.matrix[0].length is the column countmatrix.length is rows. Both are O(1).rows * cols can overflowlong if both could be large.| 2D array access m[r][c] | O(1) |
| Integer / and % | O(1) |
Remember: If you can compute element i in O(1), you can binary search it without storing it.
Spot it: 'Find the smallest speed such that the job finishes in time.' The array is NOT sorted, but the speeds are ordered: a faster speed never makes things worse, so 'can finish in h hours' goes from false to true exactly once as speed grows. Binary search the SPEED, not the array.
Two real tiers: try every speed, or binary search the speed. A tighter starting range is listed as an extra.
Try speeds 1, 2, 3, ... and return the first one that finishes in time. The answer can never be more than the biggest pile (one pile per hour is the most you can need), so loop up to that.
private static boolean canFinish(int[] piles, int speed, int h) {
long hours = 0;
for (int pile : piles) {
hours += (pile - 1) / speed + 1; // ceil(pile / speed)
}
return hours <= h;
}
static int minEatingSpeedBrute(int[] piles, int h) {
int max = 0;
for (int pile : piles) max = Math.max(max, pile);
for (int speed = 1; speed <= max; speed++) {
if (canFinish(piles, speed, h)) return speed;
}
return max;
}Search range is 1 .. max(piles). For a middle speed, check whether Koko finishes in time. If yes, this speed works, but a slower one might too, so high = mid. If not, too slow: low = mid + 1. First-true template.
static int minEatingSpeedBest(int[] piles, int h) {
int max = 0;
for (int pile : piles) max = Math.max(max, pile);
int low = 1, high = max;
while (low < high) {
int mid = low + (high - low) / 2;
if (canFinish(piles, mid, h)) high = mid; // fast enough: try slower
else low = mid + 1; // too slow: need faster
}
return low;
}Koko needs at least ceil(total / h) per hour just to eat the total in h hours, so that is a better low than 1. Same loop, a slightly smaller search range.
When it fits: Saves a few iterations. Worth mentioning as a follow-up, not needed to pass.
static int minEatingSpeedTighter(int[] piles, int h) {
long total = 0;
int max = 0;
for (int pile : piles) {
total += pile;
max = Math.max(max, pile);
}
int low = (int) Math.max(1, (total + h - 1) / h); // can't be slower than total / h
int high = max;
while (low < high) {
int mid = low + (high - low) / 2;
if (canFinish(piles, mid, h)) high = mid;
else low = mid + 1;
}
return low;
}(pile - 1) / speed + 1 is ceil(pile / speed) for positive integers. The version (pile + speed - 1) / speed also works but can overflow near 2 billion.longint range with many large piles. Using long hours costs nothing.canFinish(speed) is the whole problem: binary search only decides which speed to test next. Write the checker first and test it by hand.| Loop over the array (the check) | O(n) |
| Integer arithmetic | O(1) |
Remember: Binary search on the answer: (1) pick the range of possible answers, (2) write a yes/no check, (3) binary search the first 'yes'.
Spot it: Same shape as Koko. Packages must ship in the given order, you want the SMALLEST ship capacity that finishes in D days. Bigger capacity never needs more days, so binary search the capacity.
Two real tiers. The range is the key: the capacity must be at least the heaviest package, and never needs to exceed the total weight.
Try capacities from the heaviest package upwards, return the first one that ships in days days or fewer. The check loads packages greedily: add to today's load until the next one doesn't fit, then start a new day.
private static int daysNeeded(int[] weights, int capacity) {
int days = 1, load = 0;
for (int w : weights) {
if (load + w > capacity) { // doesn't fit today: start a new day
days++;
load = 0;
}
load += w;
}
return days;
}
static int shipWithinDaysBrute(int[] weights, int days) {
int max = 0, sum = 0;
for (int w : weights) {
max = Math.max(max, w);
sum += w;
}
for (int capacity = max; capacity <= sum; capacity++) {
if (daysNeeded(weights, capacity) <= days) return capacity;
}
return sum;
}low = heaviest package (a smaller ship can't carry it at all). high = total weight (ship everything in one day). Test the middle capacity. If it works, try smaller: high = mid. Otherwise low = mid + 1.
static int shipWithinDaysBest(int[] weights, int days) {
int low = 0, high = 0;
for (int w : weights) {
low = Math.max(low, w); // must carry the heaviest package
high += w; // one day carries everything
}
while (low < high) {
int mid = low + (high - low) / 2;
if (daysNeeded(weights, mid) <= days) high = mid; // works, try smaller
else low = mid + 1; // needs more days, go bigger
}
return low;
}Nothing else to add. It's the same template as Koko with a different check function, and that's the point of the pattern.
low and high carefullylow = max(weights) is not an optimisation, it is required: a ship smaller than the heaviest package can never finish.Math.max inside the loophigh can be the sumint for this problem's limits. For larger inputs use long.| Loop over the array (the check) | O(n) |
| Math.max | O(1) |
Remember: Order doesn't change here: packages go in the given order, so the greedy pack is exactly right. If you could reorder, it'd be a different problem.
Spot it: 'Smallest day such that I can make m bouquets of k ADJACENT flowers.' After day d, a flower is usable if it has bloomed. A later day never has fewer usable flowers, so feasibility flips once. Binary search the day.
First check there are enough flowers at all (m * k <= n, otherwise return -1). Then try day 1, 2, 3, ... up to the latest bloom, and return the first day that works. The check counts runs of k consecutive bloomed flowers.
private static boolean canMake(int[] bloomDay, int day, int m, int k) {
int bouquets = 0, run = 0;
for (int bloom : bloomDay) {
if (bloom <= day) { // flower is open
run++;
if (run == k) { // a full bouquet of k adjacent flowers
bouquets++;
run = 0;
}
} else {
run = 0; // a closed flower breaks the run
}
}
return bouquets >= m;
}
static int minDaysBrute(int[] bloomDay, int m, int k) {
if ((long) m * k > bloomDay.length) return -1;
int max = 0;
for (int b : bloomDay) max = Math.max(max, b);
for (int day = 1; day <= max; day++) {
if (canMake(bloomDay, day, m, k)) return day;
}
return -1;
}The answer must be one of the bloom days (nothing changes between blooms). Sort a copy, then test each distinct bloom day in order. This skips the huge empty stretches between values, but it is still a linear number of checks.
static int minDaysBetter(int[] bloomDay, int m, int k) {
if ((long) m * k > bloomDay.length) return -1;
int[] days = bloomDay.clone();
Arrays.sort(days);
for (int i = 0; i < days.length; i++) {
if (canMake(bloomDay, days[i], m, k)) return days[i];
}
return -1;
}Search range: the earliest bloom to the latest bloom. Test the middle day with the same check. Works: high = mid. Doesn't: low = mid + 1.
static int minDaysBest(int[] bloomDay, int m, int k) {
if ((long) m * k > bloomDay.length) return -1;
int low = Integer.MAX_VALUE, high = 0;
for (int b : bloomDay) {
low = Math.min(low, b);
high = Math.max(high, b);
}
while (low < high) {
int mid = low + (high - low) / 2;
if (canMake(bloomDay, mid, m, k)) high = mid;
else low = mid + 1;
}
return low;
}Nothing else to add beyond the three above. It's the same template as Koko and Ship Packages: range of answers, greedy check, first-true search.
(long) m * km * k can reach about 10^10 with the problem's limits, which overflows int. Cast one side to long first.-1 once at the top. Without it, the binary search would 'succeed' with a wrong answer.Integer.MAX_VALUE as the starting minimumMath.min replaces it. Standard trick from the arrays notes.run and bouquetsrun to 0. A full run of k makes a bouquet and also resets. Greedy is right because using flowers as early as possible never hurts.| Arrays.sort(int[]) | O(n log n) |
| array.clone() | O(n) |
| Loop over the array (the check) | O(n) |
Remember: Every 'minimum days / speed / capacity' question: (1) range of answers, (2) greedy yes/no check, (3) first-true binary search.
Spot it: Split into k contiguous pieces so the biggest piece sum is as small as possible. 'Minimise the maximum' is the classic sign of binary search on the answer: if a limit L works, any bigger limit works too.
The first piece ends somewhere. For each possible end, the cost is max(first piece sum, best answer for the rest with one fewer piece). Take the minimum over all choices. Recomputes the same sub-problems again and again, so it is exponential.
static int splitArrayBrute(int[] nums, int k) {
return splitFrom(nums, 0, k);
}
private static int splitFrom(int[] nums, int start, int parts) {
int n = nums.length;
if (parts == 1) { // last piece takes everything left
int sum = 0;
for (int i = start; i < n; i++) sum += nums[i];
return sum;
}
int best = Integer.MAX_VALUE, sum = 0;
for (int end = start; end <= n - parts; end++) { // leave enough elements for the other pieces
sum += nums[end];
int rest = splitFrom(nums, end + 1, parts - 1);
best = Math.min(best, Math.max(sum, rest));
}
return best;
}dp[i][j] = smallest possible largest sum when splitting the first i elements into j pieces. To fill it, try every place p where the last piece starts: the answer is max(dp[p][j-1], sum of nums[p..i-1]), and you want the minimum over p. A prefix sum array makes each piece sum O(1).
static int splitArrayBetter(int[] nums, int k) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) dp[i][1] = prefix[i]; // one piece: just the sum
for (int j = 2; j <= k; j++) {
for (int i = j; i <= n; i++) { // need at least j elements
int best = Integer.MAX_VALUE;
for (int p = j - 1; p < i; p++) { // last piece is nums[p..i-1]
int lastPiece = prefix[i] - prefix[p];
best = Math.min(best, Math.max(dp[p][j - 1], lastPiece));
}
dp[i][j] = best;
}
}
return dp[n][k];
}The answer is between the biggest single element (low) and the sum of everything (high). For a candidate limit, greedily pack numbers into a piece until the next one would exceed the limit, then start a new piece, and count the pieces. If you need at most k pieces, the limit works, so try smaller (high = mid). If you need more than k, the limit is too small (low = mid + 1).
private static int piecesNeeded(int[] nums, int limit) {
int pieces = 1, current = 0;
for (int x : nums) {
if (current + x > limit) { // doesn't fit: start a new piece
pieces++;
current = 0;
}
current += x;
}
return pieces;
}
static int splitArrayBest(int[] nums, int k) {
int low = 0, high = 0;
for (int x : nums) {
low = Math.max(low, x); // a piece must hold the biggest element
high += x; // one piece holds everything
}
while (low < high) {
int mid = low + (high - low) / 2;
if (piecesNeeded(nums, mid) <= k) high = mid; // fits in k pieces: try smaller
else low = mid + 1; // too many pieces: raise the limit
}
return low;
}A DP with a monotone-queue or memoised recursion exists, but binary search on the answer is the intended solution and the one to learn. Note it's the same shape as Ship Packages.
dp arraysnew int[n + 1][k + 1] makes an (n+1) by (k+1) grid of zeros. dp[i][j] is row i, column j.at most k pieces is fineend <= n - parts| 2D array access dp[i][j] | O(1) |
| Prefix sum array | O(n) to build, O(1) per range |
| Loop over the array (the check) | O(n) |
Remember: Minimise the maximum (or maximise the minimum) ⇒ binary search the value, with a greedy check.
Spot it: Two sorted arrays, find the median of all elements together in O(log(m + n)). Merging is O(m + n). The fast version binary searches how many elements the SMALLER array puts on the left side of the combined sorted order.
Merge the two sorted arrays like merge sort, then read the middle one (odd total) or average the two middle ones (even total).
static double findMedianBrute(int[] a, int[] b) {
int total = a.length + b.length;
int[] merged = new int[total];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) merged[k++] = a[i++];
else merged[k++] = b[j++];
}
while (i < a.length) merged[k++] = a[i++];
while (j < b.length) merged[k++] = b[j++];
if (total % 2 == 1) return merged[total / 2];
return ((double) merged[total / 2 - 1] + merged[total / 2]) / 2.0;
}You only need the elements at the middle positions, so walk through both arrays with two pointers and stop after total / 2 + 1 steps. Keep the last two values seen. No merged array: O(1) space.
static double findMedianBetter(int[] a, int[] b) {
int total = a.length + b.length;
int i = 0, j = 0;
int prev = 0, cur = 0;
for (int step = 0; step <= total / 2; step++) {
prev = cur;
if (i < a.length && (j >= b.length || a[i] <= b[j])) cur = a[i++];
else cur = b[j++];
}
if (total % 2 == 1) return cur;
return ((double) prev + cur) / 2.0;
}Imagine cutting both arrays so the LEFT sides together hold (m + n + 1) / 2 elements. The cut is right when every left element is <= every right element. Because each array is already sorted, that only needs two checks: aLeft <= bRight and bLeft <= aRight. Binary search where to cut the smaller array (i elements on its left side); the cut in the other array is then forced: j = half - i. If aLeft is too big, move the cut left; if bLeft is too big, move it right. Use ±infinity for 'nothing on that side'.
static double findMedianBest(int[] a, int[] b) {
if (a.length > b.length) return findMedianBest(b, a); // always search the smaller array
int m = a.length, n = b.length;
int half = (m + n + 1) / 2; // elements on the left side
int low = 0, high = m;
while (low <= high) {
int i = low + (high - low) / 2; // elements taken from a
int j = half - i; // elements taken from b
int aLeft = (i == 0) ? Integer.MIN_VALUE : a[i - 1];
int aRight = (i == m) ? Integer.MAX_VALUE : a[i];
int bLeft = (j == 0) ? Integer.MIN_VALUE : b[j - 1];
int bRight = (j == n) ? Integer.MAX_VALUE : b[j];
if (aLeft <= bRight && bLeft <= aRight) { // correct cut
if ((m + n) % 2 == 1) return Math.max(aLeft, bLeft);
return ((double) Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
} else if (aLeft > bRight) {
high = i - 1; // took too many from a
} else {
low = i + 1; // took too few from a
}
}
throw new IllegalArgumentException("arrays must be sorted");
}The median is the K-th smallest with K = total / 2 (and + 1 for the second middle when the total is even). To find the K-th: compare the K/2-th element of each array. The array with the smaller one can't contain the K-th, so throw away its first K/2 elements and repeat with a smaller K. Each step removes about half of K.
When it fits: O(log(m + n)). A second way to reach the same bound, and it generalises to 'K-th of many sorted arrays'.
static double findMedianKth(int[] a, int[] b) {
int total = a.length + b.length;
if (total % 2 == 1) return kthSmallest(a, 0, b, 0, total / 2 + 1);
int left = kthSmallest(a, 0, b, 0, total / 2);
int right = kthSmallest(a, 0, b, 0, total / 2 + 1);
return ((double) left + right) / 2.0;
}
// k-th smallest (k starts at 1) of a[i..] and b[j..]
private static int kthSmallest(int[] a, int i, int[] b, int j, int k) {
if (i >= a.length) return b[j + k - 1];
if (j >= b.length) return a[i + k - 1];
if (k == 1) return Math.min(a[i], b[j]);
int half = k / 2;
int aVal = (i + half - 1 < a.length) ? a[i + half - 1] : Integer.MAX_VALUE;
int bVal = (j + half - 1 < b.length) ? b[j + half - 1] : Integer.MAX_VALUE;
if (aVal < bVal) return kthSmallest(a, i + half, b, j, k - half); // drop half of a
return kthSmallest(a, i, b, j + half, k - half); // drop half of b
}Integer.MIN_VALUE / Integer.MAX_VALUE as sentinelsifs.double before adding((double) x + y) / 2.0. If you add two ints first they can overflow, and (x + y) / 2 would do integer division and drop the .5.(m + n + 1) / 2 for the left sizea is the smaller arrayj from going negative and gives the O(log(min)) bound.throw new IllegalArgumentException(...)| Array access | O(1) |
| Math.max / Math.min | O(1) |
| new int[total] | O(total) |
Remember: It's a stretch question. Know the merge approaches cold and be able to explain the partition idea in words; writing it perfectly from memory is a bonus.
| Exact match (Template 1) | Binary Search, Search Insert Position (return low), Search a 2D Matrix |
| First true / lower bound (Template 2) | Search Insert Position, First and Last Position, Find Minimum in Rotated Array, Find Peak Element |
| Keep the half that MUST contain the answer | Search in Rotated Sorted Array (find the sorted half), Find Minimum (compare with last), Find Peak (compare with the next) |
| Binary search on the answer (Template 3) | Sqrt(x), Koko Eating Bananas, Capacity To Ship Packages, Days to Make Bouquets, Split Array Largest Sum |
| Greedy check inside the search | Koko, Ship Packages, Bouquets, Split Array: each has an O(n) "does this value work" function |
| Virtual array | Search a 2D Matrix (/ and %), Rotated Search with (mid + pivot) % n |
| Partition search | Median of Two Sorted Arrays |