Binary Search, Monotonic Stack/Deque and Intervals (Java + Kotlin)

What this is: the three techniques that win by exploiting order instead of re-scanning. The centrepiece is binary-search-on-the-answer - the move that turns "minimize the maximum" into a log-factor problem and reads as senior in the room. Every template here is in Kotlin and Java, and every snippet compiled and passed its tests before it went in.

Series map: 00 playbook · 01 two-pointers & sliding window · 02 binary search, stacks & intervals (this file) · 03 trees & graphs · 04 recursion & backtracking · 05 dynamic programming · 06 Staff+ practical coding & OOD. Companion (separate track): data-structures-java-kotlin-study-guide.md owns collection choice and JVM/DS internals - PriorityQueue/heap, ArrayDeque, TreeMap mechanics, boxing, cache locality. When this guide needs a heap or deque as a tool, it uses it and points you there for the internals; the text here is about the algorithm.

The mental model#

All three techniques buy speed with the same currency: order. They never look at data they can prove is irrelevant.

Binary search halves a search space each step because a monotonic predicate holds: everything left of the boundary is one answer, everything right is the other. O(log n). The data doesn't have to be a sorted array - it only needs a true…true false…false (or false…false true…true) structure in some dimension.
A monotonic stack/deque keeps its contents in sorted order, so each index is pushed once and popped once across the whole run. The inner while looks like it makes the loop O(n²); the amortized accounting - one push, at most one pop per element - makes it O(n).
Interval problems collapse the moment you sort by a boundary and sweep left to right. Overlap, which looks like an all-pairs O(n²) question, becomes a single linear pass because after sorting you only ever compare a new interval to the running frontier.

The unifying senior insight: you don't need the input sorted - you need a monotonic predicate. The instant you can define a boolean feasible(x) that is false for small x and true for large x (or vice-versa), you binary-search the boundary between them even though nothing in the input array is sorted. That reframing - "the answer space is monotonic in X, so I binary-search the boundary" - is the highest-leverage sentence in this entire series, and §2 is built around it.

Three rules that everything below obeys:

Pick one binary-search convention and never deviate. Off-by-one and infinite loops come from mixing half-open [lo, hi) with closed [lo, hi]. This guide's default is half-open; §3's exact-search uses closed and says so loudly.
Monotonic stacks store indices, not values. You almost always need the distance/width between positions, and you can always read the value back as a[stack.top].
For intervals, the sort key is the whole game. Sort by start for merging/sweeping; sort by end for greedy "keep the most intervals." Choosing the wrong key is the single most common interval bug.

1. Binary search - the one template you never get wrong#

Recognition cue: input is sorted (or rotated-sorted, §3), or the problem reduces to "find the boundary where a condition flips." Target complexity smells like O(log n) - constraints up to 10⁹, or "do it faster than a linear scan."

Most binary-search bugs are self-inflicted: people re-derive the loop each time and get the boundary update or the termination wrong. Don't. Memorise one template - lower_bound on a half-open interval - and derive everything else (exact search, last occurrence, count) from it.

The template: `lower_bound` (first index with `a[i] >= target`)#

Invariant: the answer lives in [lo, hi] at all times; the interval is half-open [lo, hi) so hi is one past the last candidate. Loop while lo < hi; when it exits, lo == hi is the answer.

kotlin

// First index i in [0, a.size] such that a[i] >= target. a is sorted ascending.
fun lowerBound(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size                      // half-open: hi is one PAST the last real index
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2     // overflow-safe; NEVER (lo + hi) / 2
        if (a[mid] < target) lo = mid + 1   // mid too small -> answer is strictly right
        else hi = mid                        // a[mid] >= target -> answer is mid or left
    }
    return lo                            // in [0, a.size]; == a.size means "all smaller"
}

// First index i such that a[i] > target.
fun upperBound(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] <= target) lo = mid + 1   // only difference from lowerBound: <= vs <
        else hi = mid
    }
    return lo
}

java

// First index i in [0, a.length] such that a[i] >= target. a is sorted ascending.
static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;               // half-open: hi is one PAST the last real index
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;        // overflow-safe; NEVER (lo + hi) / 2
        if (a[mid] < target) lo = mid + 1;   // mid too small -> answer is strictly right
        else hi = mid;                        // a[mid] >= target -> answer is mid or left
    }
    return lo;                                // == a.length means "target bigger than all"
}

static int upperBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;  // only change vs lowerBound: <= instead of <
        else hi = mid;
    }
    return lo;
}

Why this template is bug-proof: hi never becomes negative, mid is never re-examined (each branch strictly shrinks the interval), and the loop cannot spin because lo = mid + 1 always advances and hi = mid always shrinks (since mid < hi when lo < hi). There is no mid ± 1 guesswork on the hi side to get wrong.

Everything derives from those two#

kotlin

fun findExact(a: IntArray, target: Int): Int {          // classic search, or -1
    val i = lowerBound(a, target)
    return if (i < a.size && a[i] == target) i else -1
}

fun firstOccurrence(a: IntArray, target: Int): Int {    // leftmost index of target, or -1
    val i = lowerBound(a, target)
    return if (i < a.size && a[i] == target) i else -1
}

fun lastOccurrence(a: IntArray, target: Int): Int {     // rightmost index of target, or -1
    val i = upperBound(a, target) - 1
    return if (i >= 0 && a[i] == target) i else -1
}

fun countOccurrences(a: IntArray, target: Int): Int =   // how many equal to target
    upperBound(a, target) - lowerBound(a, target)

java

static int findExact(int[] a, int target) {
    int i = lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}
static int lastOccurrence(int[] a, int target) {
    int i = upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}
static int countOccurrences(int[] a, int target) {
    return upperBound(a, target) - lowerBound(a, target);   // [lower, upper) is the equal run
}

Complexity: O(log n) time, O(1) space. count is two O(log n) searches - still O(log n).

The library methods - know the exact return contract, then usually don't use them#

The JVM ships binary search, but the "not found" encoding trips people up, and duplicates make it worse.

API	Found	Not found	Duplicates
`Arrays.binarySearch(int[], key)` (Java)	an index of key	`-(insertionPoint) - 1`	returns an arbitrary matching index, not first/last
`Collections.binarySearch(list, key)` (Java)	an index	`-(insertionPoint) - 1`	arbitrary
`List<T>.binarySearch(element)` (Kotlin)	an index	`-(insertionPoint) - 1`	arbitrary

insertionPoint is where the key would go to keep the array sorted - which equals lowerBound, the count of elements strictly less than the key. Recover it safely:

kotlin

val idx = list.binarySearch(key)                 // Kotlin stdlib on a sorted List
val insertionPoint = if (idx >= 0) idx else -(idx + 1)   // -idx - 1

java

int idx = Arrays.binarySearch(a, key);
int insertionPoint = idx >= 0 ? idx : -(idx + 1);   // == lowerBound(a, key) when absent

Opinion: in an interview, roll your own lowerBound. The library's -(insertionPoint) - 1 is a documented foot-gun (it's -1 for "insert at 0", not "found at 0"), and with duplicates it won't give you first/last anyway. Reach for the library only when you truly want "present? yes/no" on unique keys. State this tradeoff out loud - it reads as someone who's been burned by it.

Traps in §1:

mid = (lo + hi) / 2 overflows for large indices/values. Always lo + (hi - lo) / 2. (Famous JDK bug, fixed 2006.)
Mixing conventions: half-open uses hi = mid and lo < hi; closed uses hi = mid - 1 and lo <= hi. Pick one per function.
Reading a[lo] after the loop without checking lo < a.size - lower_bound legitimately returns a.size.

2. Binary search ON THE ANSWER - the highest-leverage senior move#

Recognition cue: the problem says "minimize the maximum", "maximize the minimum", "smallest/largest X such that it's still possible", or gives a huge value range with a small n. There's no sorted array to search - but the answer is monotonic: if x works, every larger x works too (or every smaller). That monotonicity is the sorted axis.

The move: define a boolean feasible(x) that is monotone in x, then binary-search the boundary between infeasible and feasible. You are running lower_bound over the answer space with feasible as the comparator.

The template#

kotlin

// Smallest x in [lo, hi] with feasible(x) == true, assuming false...false true...true.
fun searchAnswer(lo: Int, hi: Int, feasible: (Int) -> Boolean): Int {
    var l = lo
    var h = hi                            // h must itself be feasible (a valid upper bound)
    while (l < h) {
        val mid = l + (h - l) / 2
        if (feasible(mid)) h = mid        // mid works -> answer is mid or smaller
        else l = mid + 1                  // mid too small -> must go larger
    }
    return l
}
// "maximize the minimum" flips it: search for the LARGEST feasible x -> on the feasible branch
// keep `l = mid` (else branch does `h = mid - 1`), with mid = l + (h - l + 1) / 2 (round up) to avoid an infinite loop.

java

static int searchAnswer(int lo, int hi, java.util.function.IntPredicate feasible) {
    int l = lo, h = hi;                   // h must be a valid (feasible) upper bound
    while (l < h) {
        int mid = l + (h - l) / 2;
        if (feasible.test(mid)) h = mid;  // mid works -> shrink toward smaller answers
        else l = mid + 1;                 // mid infeasible -> need larger
    }
    return l;
}

The whole skill is (a) spotting the monotonicity and (b) writing feasible. The search itself is the §1 template. Two-thirds of the difficulty of these "hard" problems evaporates once you say the magic sentence.

Koko eating bananas (min eating speed in `h` hours)#

feasible(speed) = "can finish all piles in ≤ h hours at this speed." Faster speed → fewer hours → monotone. Search speed in [1, max(piles)].

kotlin

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    fun hoursAt(speed: Int): Long {
        var hours = 0L
        for (p in piles) hours += (p.toLong() + speed - 1) / speed   // ceil(p / speed)
        return hours
    }
    var lo = 1
    var hi = piles.max()                 // Kotlin 2: max() throws on empty, fine here
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (hoursAt(mid) <= h) hi = mid  // feasible -> try a slower (smaller) speed
        else lo = mid + 1
    }
    return lo
}

java

static int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursAt(piles, mid) <= h) hi = mid;   // feasible -> slower is fine
        else lo = mid + 1;
    }
    return lo;
}
static long hoursAt(int[] piles, int speed) {
    long hours = 0;
    for (int p : piles) hours += (p + (long) speed - 1) / speed;   // ceil, promoted to long
    return hours;
}

Capacity to ship packages within D days#

feasible(cap) = "greedily filling days without exceeding cap uses ≤ D days." Bigger capacity → fewer days → monotone. The lower bound is max(weights) (a single package must fit); the upper bound is sum(weights) (ship it all in one day). The same shape solves split array largest sum and allocate books/painters - identical feasible, different names.

kotlin

fun shipWithinDays(weights: IntArray, days: Int): Int {
    fun daysNeeded(cap: Int): Int {
        var d = 1
        var load = 0
        for (w in weights) {
            if (load + w > cap) { d++; load = 0 }   // overflow this day -> open a new one
            load += w
        }
        return d
    }
    var lo = weights.max()               // a package must fit in a single day
    var hi = weights.sum()               // everything in one day
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (daysNeeded(mid) <= days) hi = mid   // feasible -> try a smaller ship
        else lo = mid + 1
    }
    return lo
}

java

static 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 (daysNeeded(weights, mid) <= days) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
static int daysNeeded(int[] weights, int cap) {
    int d = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { d++; load = 0; }   // open a new day
        load += w;
    }
    return d;
}

Split array largest sum (min the max subarray sum over k parts)#

Proof that it's the same problem: "largest allowed piece sum = cap, count pieces, is pieces <= k?"

kotlin

fun splitArray(nums: IntArray, k: Int): Int {
    fun pieces(cap: Int): Int {
        var count = 1
        var sum = 0
        for (x in nums) {
            if (sum + x > cap) { count++; sum = 0 }
            sum += x
        }
        return count
    }
    var lo = nums.max()
    var hi = nums.sum()
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (pieces(mid) <= k) hi = mid   // fewer/equal pieces -> cap can shrink
        else lo = mid + 1
    }
    return lo
}

java

static int splitArray(int[] nums, int k) {
    int lo = 0, hi = 0;
    for (int x : nums) { lo = Math.max(lo, x); hi += x; }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 1, sum = 0;
        for (int x : nums) {
            if (sum + x > mid) { count++; sum = 0; }
            sum += x;
        }
        if (count <= k) hi = mid;        // feasible -> shrink the max allowed sum
        else lo = mid + 1;
    }
    return lo;
}

Complexity: O(n · log(range)) time, O(1) space. The log factor is over the value range (sum here), not n - which is exactly why it beats a DP when the array is long but the totals are bounded.

Traps in §2:

Non-monotone feasible. If "works" isn't monotone in x, binary search is invalid - you'd need DP/greedy. Sanity-check: does making x more generous never turn a yes into a no?
Wrong bounds. lo must be the smallest conceivable answer, hi a value guaranteed feasible. For "min the max," lo = max(element) (any smaller can't hold the biggest single item), hi = sum.
Overflow in feasible. Sums of up to 10⁴ elements ×10⁹ overflow int; accumulate in long (Java) / Long (Kotlin). Shown above.
"Maximize the minimum" needs the round-up mid (mid = lo + (hi - lo + 1) / 2) and lo = mid on the feasible branch, or it infinite-loops when hi - lo == 1.

3. Binary search on rotated / structured-but-not-fully-sorted input#

Recognition cue: the data is locally ordered but not globally sorted - a rotated sorted array, a bitonic/peak shape, a matrix sorted along rows and columns, or a run of pairs with one odd element. You still get O(log n), but each step you first ask "which half is sorted?" and then decide which half can contain the target.

Here I switch to the closed interval [lo, hi] with lo <= hi for exact search, because you compare against concrete endpoints a[lo]/a[hi]. Stay consistent within the function.

Search in a rotated sorted array#

One of the two halves around mid is always properly sorted. Identify it, test whether the target lies inside its sorted range, and recurse into the half that can hold it.

kotlin

fun searchRotated(a: IntArray, target: Int): Int {
    var lo = 0
    var hi = a.size - 1                   // CLOSED interval here
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        when {
            a[mid] == target -> return mid
            a[lo] <= a[mid] -> {          // left half [lo..mid] is sorted
                if (target in a[lo]..<a[mid]) hi = mid - 1 else lo = mid + 1
            }
            else -> {                     // right half [mid..hi] is sorted
                if (target in (a[mid] + 1)..a[hi]) lo = mid + 1 else hi = mid - 1
            }
        }
    }
    return -1
}

java

static int searchRotated(int[] a, int target) {
    int lo = 0, hi = a.length - 1;        // CLOSED interval
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {            // left half sorted
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                          // right half sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Find the minimum in a rotated sorted array#

The minimum is the unique "cliff." Compare a[mid] to a[hi] (not a[lo], which is ambiguous when the array isn't rotated): if a[mid] > a[hi] the cliff is strictly right; otherwise it's mid or left. Half-open-ish lo < hi, converging on the answer index.

kotlin

fun findMin(a: IntArray): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] > a[hi]) lo = mid + 1   // min must be to the right of mid
        else hi = mid                       // min is mid or to its left
    }
    return a[lo]                            // lo == hi == index of the minimum
}

java

static int findMin(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1;   // min is to the right
        else hi = mid;                       // min is mid or left
    }
    return a[lo];
}

Why a[hi] not a[lo]? With a[lo], a non-rotated array ([1,2,3]) fools the "left half sorted" test into discarding the real minimum. Comparing to a[hi] is unambiguous: a[mid] <= a[hi] always means the right part is clean. Distinct duplicates break the O(log n) guarantee (LeetCode 154 degrades to O(n) worst case) - mention that.

Find a peak element (any local max)#

nums[-1] = nums[n] = -∞ by convention. Walk uphill: if a[mid] < a[mid+1] a peak must exist to the right; else mid is a peak or one is to its left. This is binary search with no sorted array at all - just a monotone "is the slope up?" predicate.

kotlin

fun findPeakElement(a: IntArray): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (a[mid] < a[mid + 1]) lo = mid + 1   // ascending -> peak on the right
        else hi = mid                            // descending/plateau-top -> peak here or left
    }
    return lo
}

java

static int findPeakElement(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1;   // go up-slope
        else hi = mid;
    }
    return lo;
}

Search a row- and column-sorted matrix (staircase)#

Rows sorted left→right, columns top→bottom. Start at the top-right corner. That cell is the max of its row and the min of its column, so each comparison eliminates a whole row or column: O(m + n), which beats binary-searching each row (O(m log n)).

kotlin

fun searchMatrix(m: Array<IntArray>, target: Int): Boolean {
    var r = 0
    var c = m[0].size - 1                 // top-right corner
    while (r < m.size && c >= 0) {
        when {
            m[r][c] == target -> return true
            m[r][c] > target -> c--       // this column's top is too big -> drop the column
            else -> r++                    // this row's right is too small -> drop the row
        }
    }
    return false
}

java

static boolean searchMatrix(int[][] m, int target) {
    int r = 0, c = m[0].length - 1;       // top-right corner
    while (r < m.length && c >= 0) {
        if (m[r][c] == target) return true;
        else if (m[r][c] > target) c--;   // eliminate the column
        else r++;                          // eliminate the row
    }
    return false;
}

Single element in a sorted array (every other element appears twice)#

Before the singleton, pairs start at even indices (a[2i] == a[2i+1]); after it, the pairing shifts by one. Binary-search on that parity break. Force mid even, then check the pair.

kotlin

fun singleNonDuplicate(a: IntArray): Int {
    var lo = 0
    var hi = a.size - 1
    while (lo < hi) {
        var mid = lo + (hi - lo) / 2
        if (mid % 2 == 1) mid--           // align mid to the even index of its pair
        if (a[mid] == a[mid + 1]) lo = mid + 2   // pairing intact -> singleton is to the right
        else hi = mid                             // pairing broken -> singleton is mid or left
    }
    return a[lo]
}

java

static int singleNonDuplicate(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if ((mid & 1) == 1) mid--;        // force even
        if (a[mid] == a[mid + 1]) lo = mid + 2;   // intact pair -> go right
        else hi = mid;                             // broken -> singleton here or left
    }
    return a[lo];
}

Complexity: all O(log n) except the staircase matrix at O(m + n). Traps: comparing rotated-min to a[lo]; forgetting duplicates degrade rotated search to O(n); starting the matrix walk at a corner that doesn't disambiguate (top-left and bottom-right don't - both neighbours move the same direction).

4. Monotonic stack - each element pushed and popped once#

Recognition cue: "next/previous greater or smaller element," stock span, daily temperatures, largest rectangle in a histogram, trapping rain water, or "build the smallest/largest subsequence by removing k." Whenever you're scanning and repeatedly asking "what's the nearest bigger/smaller thing on one side," it's a monotonic stack.

Template: keep a stack that is monotone (increasing or decreasing) in the values it references. When a new element violates the monotonicity, pop until it fits - each pop is the moment you've found the answer for the popped element. Store indices, read values as a[stack.top].

The amortization argument you say out loud: across the whole scan, every index is pushed exactly once and popped at most once, so the total pop work is ≤ n despite the nested while. Amortized O(n).

Daily temperatures (next strictly-greater, as a distance)#

Keep indices of a decreasing temperature stack. A warmer day pops everyone it beats and records the gap.

kotlin

fun dailyTemperatures(t: IntArray): IntArray {
    val ans = IntArray(t.size)            // 0 by default = "no warmer day ahead"
    val st = ArrayDeque<Int>()            // indices; temps strictly decreasing bottom->top
    for (i in t.indices) {
        while (st.isNotEmpty() && t[i] > t[st.last()]) {
            val j = st.removeLast()       // day j finally sees a warmer day at i
            ans[j] = i - j
        }
        st.addLast(i)
    }
    return ans
}

java

static int[] dailyTemperatures(int[] t) {
    int n = t.length;
    int[] ans = new int[n];               // 0 = no warmer day
    Deque<Integer> st = new ArrayDeque<>();   // indices; strictly decreasing temps
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && t[i] > t[st.peek()]) {
            int j = st.pop();             // resolved: i is j's next warmer day
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

Kotlin note: kotlin.collections.ArrayDeque uses addLast / removeLast / last() - there is no push/pop/peek. java.util.ArrayDeque (what the Java column uses) has push/pop/peek operating on the head. Both are correct stacks; just don't mix the vocabularies. See the companion guide for why ArrayDeque beats Stack/LinkedList here.

Next greater element II (circular array)#

Wrap by iterating 2n times with i % n; only push real indices (i < n).

kotlin

fun nextGreaterElements(a: IntArray): IntArray {
    val n = a.size
    val ans = IntArray(n) { -1 }
    val st = ArrayDeque<Int>()            // indices of not-yet-answered elements
    for (i in 0 until 2 * n) {
        val cur = a[i % n]
        while (st.isNotEmpty() && a[st.last()] < cur) ans[st.removeLast()] = cur
        if (i < n) st.addLast(i)          // second lap only resolves, never enqueues
    }
    return ans
}

java

static int[] nextGreaterElements(int[] a) {
    int n = a.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {
        int cur = a[i % n];
        while (!st.isEmpty() && a[st.peek()] < cur) ans[st.pop()] = cur;
        if (i < n) st.push(i);
    }
    return ans;
}

Largest rectangle in a histogram#

The signature monotonic-stack hard. Keep an increasing stack of bar indices. When a shorter bar arrives, each taller bar it pops is a rectangle whose height is that popped bar and whose width spans from the bar now below it (exclusive) to the current index (exclusive). Push a sentinel 0 at the end (i == n) to flush the stack.

kotlin

fun largestRectangleArea(h: IntArray): Int {
    val st = ArrayDeque<Int>()            // indices; heights strictly increasing
    var best = 0
    for (i in 0..h.size) {                // one extra step: virtual height 0 flushes all
        val cur = if (i == h.size) 0 else h[i]
        while (st.isNotEmpty() && h[st.last()] >= cur) {
            val height = h[st.removeLast()]
            val left = if (st.isEmpty()) -1 else st.last()   // first shorter bar to the left
            best = maxOf(best, height * (i - left - 1))       // width = right - left - 1
        }
        st.addLast(i)
    }
    return best
}

java

static int largestRectangleArea(int[] h) {
    int n = h.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();   // indices; increasing heights
    for (int i = 0; i <= n; i++) {            // i == n -> virtual bar of height 0
        int cur = (i == n) ? 0 : h[i];
        while (!st.isEmpty() && h[st.peek()] >= cur) {
            int height = h[st.pop()];
            int left = st.isEmpty() ? -1 : st.peek();
            int width = i - left - 1;
            best = Math.max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

Maximal rectangle (in a binary matrix) reduces to this: build a per-column "height" histogram row by row (reset to 0 on a 0, else +1), run largestRectangleArea on each row's histogram, keep the max. O(rows × cols).

Trapping rain water (stack version)#

Decreasing stack of indices; when a taller bar arrives it forms a basin with the bar below the one you pop. (The two-pointer version - see guide 01 - is O(1) space; the stack version is the one that generalizes to "bounded by walls" framing.)

kotlin

fun trap(h: IntArray): Int {
    val st = ArrayDeque<Int>()            // indices; heights non-increasing
    var water = 0
    for (i in h.indices) {
        while (st.isNotEmpty() && h[i] > h[st.last()]) {
            val bottom = st.removeLast()  // floor of the basin
            if (st.isEmpty()) break       // no left wall -> water spills off the left edge
            val left = st.last()
            val width = i - left - 1
            val bounded = minOf(h[left], h[i]) - h[bottom]   // min wall minus floor
            water += width * bounded
        }
        st.addLast(i)
    }
    return water
}

java

static int trap(int[] h) {
    Deque<Integer> st = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < h.length; i++) {
        while (!st.isEmpty() && h[i] > h[st.peek()]) {
            int bottom = st.pop();
            if (st.isEmpty()) break;      // no left wall -> nothing traps
            int left = st.peek();
            int width = i - left - 1;
            int bounded = Math.min(h[left], h[i]) - h[bottom];
            water += width * bounded;
        }
        st.push(i);
    }
    return water;
}

Remove k digits (build the smallest number)#

Greedy + monotonic stack: to make the smallest number, pop a larger digit whenever a smaller one arrives and you still have removals left. This is the general "smallest/largest subsequence" engine (also Remove Duplicate Letters, Create Maximum Number).

kotlin

fun removeKdigits(num: String, k: Int): String {
    var remaining = k
    val st = ArrayDeque<Char>()           // digits, non-decreasing bottom->top
    for (d in num) {
        while (remaining > 0 && st.isNotEmpty() && st.last() > d) {
            st.removeLast(); remaining--  // drop a bigger digit sitting to the left
        }
        st.addLast(d)
    }
    repeat(remaining) { st.removeLast() } // still owe removals -> shave from the top
    val s = st.joinToString("").trimStart('0')   // bottom->top is the number; kill leading 0s
    return s.ifEmpty { "0" }
}

java

static String removeKdigits(String num, int k) {
    Deque<Character> st = new ArrayDeque<>();   // used bottom->top as increasing digits
    for (char d : num.toCharArray()) {
        while (k > 0 && !st.isEmpty() && st.peekLast() > d) { st.pollLast(); k--; }
        st.addLast(d);
    }
    while (k-- > 0) st.pollLast();              // remove any leftover from the tail
    StringBuilder sb = new StringBuilder();
    for (char c : st) sb.append(c);            // ArrayDeque iterates head->tail = bottom->top
    while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);   // strip leading zeros
    return sb.length() == 0 ? "0" : sb.toString();   // everything removed -> "0"
}

Complexity: all O(n) time, O(n) space (the stack). Traps:

Storing values instead of indices. Daily temperatures and histograms need distances; with values you can't compute width. Store indices, read values as a[idx].
>= vs > in the pop test. For "next strictly greater" use >; for "next greater-or-equal" use >=. In the histogram, popping on >= (equal heights) is fine because an equal bar recomputes the same or larger width later - but you must be consistent or you double-count/skip.
Forgetting the flush. The largest-rectangle sentinel (i == n, height 0) is what empties the stack; without it, bars still on the stack at the end are never measured.

5. Monotonic deque - a sliding-window max/min in O(n)#

Recognition cue: you need the max or min of a sliding window as it moves, or a windowed extreme inside another algorithm (DP transitions, "shortest subarray with sum ≥ k"). A heap gives O(n log k); a monotonic deque gives O(n) because it discards dominated elements instead of lazily keeping them.

Why a deque beats a heap here: a max-heap holds every window element (O(k) space, O(log k) per op) and needs lazy deletion to drop the one that slid out. A monotonic deque keeps only elements that could still be the max - as soon as a new element arrives, every smaller element to its left is useless forever and gets dropped. The front is always the current max; both ends are O(1). Total work is O(n): each index enters and leaves once.

Sliding window maximum#

Deque holds indices, values decreasing front→back. Evict the front when it slides out of the window; evict the back while it's ≤ the incoming value (dominated).

kotlin

fun maxSlidingWindow(a: IntArray, k: Int): IntArray {
    val n = a.size
    val ans = IntArray(n - k + 1)
    val dq = ArrayDeque<Int>()            // indices; a[dq] strictly decreasing front->back
    for (i in 0 until n) {
        if (dq.isNotEmpty() && dq.first() <= i - k) dq.removeFirst()   // front left the window
        while (dq.isNotEmpty() && a[dq.last()] <= a[i]) dq.removeLast() // drop dominated
        dq.addLast(i)
        if (i >= k - 1) ans[i - k + 1] = a[dq.first()]                 // front = window max
    }
    return ans
}

java

static int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();   // indices; decreasing values front->back
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();      // expire front
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();   // pop dominated
        dq.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = a[dq.peekFirst()];               // front is the max
    }
    return ans;
}

Shortest subarray with sum at least k (handles negatives)#

The classic sliding window fails with negative numbers; this needs prefix sums + a monotonic deque of increasing prefix values. For each i, pop the front while pre[i] - pre[front] >= k (that front gives a valid subarray, and a shorter one can't use it again), then pop the back while its prefix is ≥ the current (dominated - a later, smaller prefix is strictly better).

kotlin

fun shortestSubarray(a: IntArray, k: Long): Int {
    val n = a.size
    val pre = LongArray(n + 1)
    for (i in 0 until n) pre[i + 1] = pre[i] + a[i]
    val dq = ArrayDeque<Int>()            // indices into pre; pre increasing front->back
    var best = Int.MAX_VALUE
    for (i in 0..n) {
        while (dq.isNotEmpty() && pre[i] - pre[dq.first()] >= k)
            best = minOf(best, i - dq.removeFirst())         // greedily close valid windows
        while (dq.isNotEmpty() && pre[dq.last()] >= pre[i])
            dq.removeLast()                                   // current prefix dominates
        dq.addLast(i)
    }
    return if (best == Int.MAX_VALUE) -1 else best
}

java

static int shortestSubarray(int[] a, long k) {
    int n = a.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
    Deque<Integer> dq = new ArrayDeque<>();   // indices into pre; increasing prefix values
    int best = Integer.MAX_VALUE;
    for (int i = 0; i <= n; i++) {
        while (!dq.isEmpty() && pre[i] - pre[dq.peekFirst()] >= k)
            best = Math.min(best, i - dq.pollFirst());
        while (!dq.isEmpty() && pre[dq.peekLast()] >= pre[i])
            dq.pollLast();
        dq.offerLast(i);
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

One light tie to your world: this is exactly the shape of a sliding-window rate limiter (guide 06 builds the ONS one) - a windowed count/extreme maintained in O(1) amortized per event, evicting from the front as time advances. Same deque, timestamps instead of indices.

Complexity: O(n) time, O(k) / O(n) space. Traps: popping the front on the wrong condition (must be index <= i - k for windows, or >= k for the sum problem); using < vs <= when evicting the back (<= keeps the deque strictly monotone and picks the leftmost max, which matters for "shortest"); forgetting prefix sums must be long (negatives + 10⁵ elements).

6. Intervals and the sweep line#

Recognition cue: the input is a list of [start, end] ranges and you must merge overlaps, insert one, intersect two lists, count concurrency ("meeting rooms"), or greedily keep the most non-overlapping ones. The universal first move: sort by a boundary, then sweep once.

Two templates, and choosing between them is the skill:

Sort-by-start + sweep a running frontier - for merging, inserting, "can attend all."
Event-based sweep (+1 at each start, -1 at each end, process in time order) - for "how many concurrent," peak load. Equivalent to a min-heap of end times.

Merge intervals (sort by START)#

Sort by start; keep the last merged interval; extend it if the next overlaps, else append.

kotlin

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val sorted = intervals.sortedBy { it[0] }        // by START
    val out = ArrayList<IntArray>()
    for (cur in sorted) {
        val last = out.lastOrNull()
        if (last == null || last[1] < cur[0]) out.add(intArrayOf(cur[0], cur[1]))  // gap
        else last[1] = maxOf(last[1], cur[1])         // overlap -> extend the frontier
    }
    return out.toTypedArray()
}

java

static int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[0]));   // by START
    List<int[]> out = new ArrayList<>();
    for (int[] cur : intervals) {
        int last = out.size() - 1;
        if (out.isEmpty() || out.get(last)[1] < cur[0]) out.add(new int[]{cur[0], cur[1]});
        else out.get(last)[1] = Math.max(out.get(last)[1], cur[1]);  // extend
    }
    return out.toArray(new int[0][]);
}

Overlap boundary: if touching intervals like [1,2] and [2,3] should merge, use last[1] < cur[0] (strict) for "gap". If they should not merge (half-open ranges), use last[1] <= cur[0]. Ask the interviewer which; it's a real clarifying question, not pedantry.

Insert interval into a sorted, non-overlapping list (O(n), no re-sort)#

Three phases: copy intervals entirely left of the new one, absorb all overlappers into the new one, copy the rest.

kotlin

fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    val out = ArrayList<IntArray>()
    val ni = newInterval.copyOf()
    var i = 0
    val n = intervals.size
    while (i < n && intervals[i][1] < ni[0]) out.add(intervals[i++])        // strictly left
    while (i < n && intervals[i][0] <= ni[1]) {                             // overlaps -> absorb
        ni[0] = minOf(ni[0], intervals[i][0])
        ni[1] = maxOf(ni[1], intervals[i][1])
        i++
    }
    out.add(ni)
    while (i < n) out.add(intervals[i++])                                    // strictly right
    return out.toTypedArray()
}

java

static int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> out = new ArrayList<>();
    int[] ni = newInterval.clone();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < ni[0]) out.add(intervals[i++]);       // left of new
    while (i < n && intervals[i][0] <= ni[1]) {                             // overlapping
        ni[0] = Math.min(ni[0], intervals[i][0]);
        ni[1] = Math.max(ni[1], intervals[i][1]);
        i++;
    }
    out.add(ni);
    while (i < n) out.add(intervals[i++]);                                   // right of new
    return out.toArray(new int[0][]);
}

Non-overlapping intervals (min removals) - sort by END, greedy#

To keep the most intervals, greedily keep the one that ends earliest - it leaves the most room. Sort by end; count anything whose start is before the running end as a removal. (This is interval scheduling, the canonical greedy; contrast with DP in guide 05.)

kotlin

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    val sorted = intervals.sortedBy { it[1] }        // by END - the greedy key
    var end = Int.MIN_VALUE
    var removed = 0
    for (cur in sorted) {
        if (cur[0] >= end) end = cur[1]              // no clash -> keep, advance frontier
        else removed++                                // clashes with kept -> must remove
    }
    return removed
}

java

static int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[1]));   // by END
    int end = Integer.MIN_VALUE, removed = 0;
    for (int[] cur : intervals) {
        if (cur[0] >= end) end = cur[1];   // keep it
        else removed++;                     // overlap -> drop
    }
    return removed;
}

Meeting rooms II (minimum rooms) - two equivalent lenses#

"Can attend all?" (Meeting Rooms I) is just: sort by start, return false if any start < previous end. "How many rooms?" is the concurrency peak - here are both canonical solutions.

Min-heap of end times. Sort by start; a heap holds end times of in-progress meetings. For each meeting, if the earliest-ending room is free by its start, reuse it (poll); always offer this meeting's end. The heap size is the answer.

kotlin

fun minMeetingRoomsHeap(intervals: Array<IntArray>): Int {
    val sorted = intervals.sortedBy { it[0] }        // by START
    val ends = PriorityQueue<Int>()                  // min-heap of end times (see companion)
    for (cur in sorted) {
        if (ends.isNotEmpty() && ends.peek() <= cur[0]) ends.poll()   // a room freed up -> reuse
        ends.offer(cur[1])
    }
    return ends.size                                  // peak concurrency = rooms needed
}

java

static int minMeetingRoomsHeap(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[0]));   // by START
    PriorityQueue<Integer> ends = new PriorityQueue<>();            // min-heap of end times
    for (int[] cur : intervals) {
        if (!ends.isEmpty() && ends.peek() <= cur[0]) ends.poll();  // reuse the earliest room
        ends.offer(cur[1]);
    }
    return ends.size();
}

Sweep line (+1/-1). Split into start and end events, sort each, two-pointer merge. A start bumps the room count; an end releases one. Track the peak.

kotlin

fun minMeetingRoomsSweep(intervals: Array<IntArray>): Int {
    val n = intervals.size
    val starts = IntArray(n) { intervals[it][0] }.also { it.sort() }
    val ends = IntArray(n) { intervals[it][1] }.also { it.sort() }
    var rooms = 0; var best = 0; var si = 0; var ei = 0
    while (si < n) {
        if (starts[si] < ends[ei]) { rooms++; si++; best = maxOf(best, rooms) }  // a start
        else { rooms--; ei++ }                                                    // an end
    }
    return best
}

java

static int minMeetingRoomsSweep(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int rooms = 0, best = 0, si = 0, ei = 0;
    while (si < n) {
        if (starts[si] < ends[ei]) { rooms++; si++; best = Math.max(best, rooms); }  // start
        else { rooms--; ei++; }                                                       // end
    }
    return best;
}

The double-counting trap, stated exactly: at a shared timestamp, a meeting that ends when another starts must not count as concurrent (a room ending at 10 is reusable at 10). That's why the sweep uses starts[si] < ends[ei] (strict): on a tie, the end wins and frees the room first. In event form: sort so that end events precede start events at equal time. Use <= instead and you over-count rooms. If the problem says touching does conflict, flip it - but say which you assumed.

Related one-liners you can now derive: Interval List Intersection (two-pointer over two sorted lists, intersect [max(starts), min(ends)], advance the one that ends first); Employee Free Time (merge all intervals, the gaps between merged blocks are the free time); My Calendar I (a TreeMap<start, end> - floorKey/ceilingKey to check the neighbours in O(log n) per booking).

Complexity: all O(n log n) (dominated by the sort). Traps: wrong sort key (start vs end - merging wants start, greedy-keep wants end); mutating the caller's array when you sort in place (clone if the contract forbids it); the tie-break above.

7. Quickselect vs the bounded heap - two ways to do top-k#

Recognition cue: "kth largest/smallest," "top k," "k most frequent," or a running/streaming median. Two tools, and the interview points you: Quickselect for a one-shot kth on an in-memory array (average O(n)); a bounded k-heap for a stream or when you must not mutate the input (O(n log k)).

Quickselect (Hoare's selection, Lomuto partition + random pivot)#

Partition around a random pivot; the pivot lands at its final sorted index p. If p is the index you want, done; else recurse into the one side that contains it. Because you only recurse one side, the average work is n + n/2 + n/4 + … = O(n).

kotlin

private val rng = java.util.Random()

fun findKthLargest(a: IntArray, k: Int): Int {
    val target = a.size - k               // kth largest == index (n-k) in ascending order
    var lo = 0
    var hi = a.size - 1
    while (lo < hi) {
        val p = partition(a, lo, hi)
        when {
            p == target -> break
            p < target -> lo = p + 1      // wanted index is to the right
            else -> hi = p - 1            // to the left
        }
    }
    return a[target]
}

private fun partition(a: IntArray, lo: Int, hi: Int): Int {
    val r = lo + rng.nextInt(hi - lo + 1) // RANDOM pivot -> defuses the sorted-input O(n^2)
    a.swap(r, hi)
    val pivot = a[hi]
    var i = lo
    for (j in lo until hi) if (a[j] < pivot) a.swap(i++, j)
    a.swap(i, hi)                          // pivot to its final position
    return i
}

private fun IntArray.swap(i: Int, j: Int) { val t = this[i]; this[i] = this[j]; this[j] = t }

java

static final java.util.Random RNG = new java.util.Random();

static int findKthLargest(int[] a, int k) {
    int target = a.length - k;            // kth largest == ascending index (n-k)
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int p = partition(a, lo, hi);
        if (p == target) break;
        else if (p < target) lo = p + 1;  // recurse right only
        else hi = p - 1;                   // recurse left only
    }
    return a[target];
}

static int partition(int[] a, int lo, int hi) {
    int r = lo + RNG.nextInt(hi - lo + 1); // RANDOM pivot: avoids O(n^2) on sorted input
    swap(a, r, hi);
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(a, i++, j);
    swap(a, i, hi);
    return i;
}
static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

Bounded k-heap - when the stream, or the input contract, wins#

Keep a min-heap of size k of the largest-seen elements: push each element, and if the heap exceeds k, evict the smallest. The heap's root is the kth largest. This never mutates the input, uses only O(k) memory, and works on a stream you can't hold in RAM.

kotlin

fun findKthLargestHeap(a: IntArray, k: Int): Int {
    val heap = PriorityQueue<Int>()       // MIN-heap; retains the k largest seen (see companion)
    for (x in a) {
        heap.offer(x)
        if (heap.size > k) heap.poll()    // drop the smallest -> heap holds the top k
    }
    return heap.peek()                    // root of a size-k min-heap = kth largest
}

java

static int findKthLargestHeap(int[] a, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();   // MIN-heap of the k largest
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();                  // evict smallest
    }
    return heap.peek();                                     // kth largest
}

	Quickselect	Bounded k-heap
Time	O(n) average, O(n²) worst (mitigated by random pivot)	O(n log k)
Space	O(1) in place	O(k)
Mutates input?	Yes (reorders)	No
Streaming / n too big for RAM?	No (needs the whole array)	Yes
Also returns the k elements?	Yes (`a[target..]` after)	Yes (drain the heap)
Stable / repeatable timing?	No (randomized)	Yes

When each wins: array in memory, one query, don't care about order among the top-k → Quickselect (beats sorting's O(n log n) and the heap's log factor). Stream, or "k most frequent over an event feed," or must preserve the caller's array → k-heap. For k-most-frequent, count with a hash map then run either selector over the (value,count) entries.

One light tie to your world: bounded-heap streaming top-k over session events - "top N chargepoints by energy this hour" over the OCPI session-event feed - is the k-heap, not Quickselect: the feed doesn't fit in memory and you can't reorder a stream. O(k) state per window, evict the min as new events arrive. (Heap internals: companion guide.)

Traps: non-random pivot makes Quickselect O(n²) on already-sorted input - always randomize (or median-of-three); off-by-one in target = n - k (kth largest is ascending index n-k, kth smallest is k-1); using a max-heap for "k largest" (you want a min-heap so the root is the eviction candidate); mutating the input when the caller needs it intact.

Problems & how to solve them#

Problem: the binary search never terminates (infinite loop). Root cause: hi = mid combined with lo <= hi, or lo = mid without rounding mid up. When hi - lo == 1, mid == lo, and a branch that keeps lo = mid never advances. Fix: match the update to the interval. Half-open [lo, hi) → while (lo < hi), hi = mid, lo = mid + 1. Closed [lo, hi] → while (lo <= hi), hi = mid - 1, lo = mid + 1. For "maximize the minimum" (keep lo = mid), round up: mid = lo + (hi - lo + 1) / 2.

Problem: off-by-one - you return an index one past, or miss the last element. Root cause: inconsistent boundary meaning - treating hi as inclusive in a half-open loop (or vice-versa), so the final element is never examined. Fix: fix the meaning of hi up front and never break it. Half-open: hi = a.size (one past the end), answer in [0, a.size]. Closed: hi = a.size - 1 (last valid index). Write the invariant in a comment and check it against n = 1.

Problem: mid overflows on large inputs. Root cause: (lo + hi) / 2 overflows int when lo + hi > 2³¹−1 (real at 10⁹-scale indices/values, common in binary-search-on-answer where you search a value range). Fix: always lo + (hi - lo) / 2. In Kotlin, also promote accumulator sums inside feasible to Long.

Problem: it worked on the sorted example but breaks on the rotated one. Root cause: you compared the rotated-array pivot to a[lo] instead of a[hi], so a non-rotated (or minimally rotated) array takes the wrong "which half is sorted" branch. Fix: for find-min / rotation detection compare a[mid] to a[hi] (unambiguous). For rotated search, first decide the sorted half with a[lo] <= a[mid], then test whether the target is inside that half's concrete [a[lo], a[mid]) (or (a[mid], a[hi]]) range.

Problem: monotonic-stack answer is right for values but you can't compute the width/distance. Root cause: you pushed values onto the stack, so you lost positions and can't do i - j. Fix: push indices; read values as a[stack.top]. Daily temperatures, histogram, trapping water all need i - left - 1 style widths that only indices give you.

Problem: histogram / next-greater misses the elements still on the stack at the end. Root cause: no flush - elements with no smaller/greater element to their right are never popped, so never measured. Fix: iterate to i == n with a virtual sentinel (0 for largest-rectangle, or initialize the answer to the "none" value for next-greater) that forces every remaining element off the stack.

Problem: interval solution gives subtly wrong merges or room counts. Root cause: wrong sort key (sorted by end when merging, or by start when doing the greedy keep), or an inconsistent overlap boundary (< vs <=) at touching endpoints. Fix: merge/insert/sweep → sort by start; greedy "keep the most non-overlapping" → sort by end. Decide once whether touching intervals ([1,2],[2,3]) overlap and thread that same < / <= everywhere.

Problem: meeting-rooms sweep reports one too many rooms. Root cause: double-counting at a shared timestamp - a meeting ending at t and another starting at t were treated as concurrent. Fix: process end before start on ties. In the two-pointer sweep use strict starts[si] < ends[ei]; in an event list, sort end-events ahead of start-events at equal time. (Reverse it only if the problem says touching conflicts.)

Problem: Quickselect is fast in tests but times out on one case. Root cause: a fixed pivot (first/last element) hits O(n²) on already-sorted or reverse-sorted input - a common adversarial test. Fix: pick a random pivot (or median-of-three) each partition. State the O(n) average / O(n²) worst honestly, and that randomization makes the worst case astronomically unlikely.

Interview framing / how to sound senior#

Power phrases (say these):

"The answer is monotonic in X - if x works then every larger x works - so I'll binary-search the boundary with a feasible(x) predicate." ← the single highest-value sentence in this guide.
"There's no sorted array, but there's a monotone predicate, so it's still O(log n) over the value range - O(n·log(sum)) overall."
"I'll keep a monotonic stack of indices; each element is pushed once and popped once, so it's amortized O(n) despite the inner while-loop."
"For the window max I'll use a monotonic deque, not a heap - it drops dominated elements, so it's O(n) instead of O(n log k)."
"Intervals: I'll sort by start and sweep. If it were 'keep the most non-overlapping,' I'd sort by end instead - earliest finish is the greedy choice."
"Touching endpoints - [1,2] and [2,3] - do they overlap? That changes a < to a <=." ← a senior clarifying question.
"Quickselect is O(n) average for one kth query; if it's a stream or I can't mutate the input, I switch to a bounded k-heap at O(n log k)."

Anti-phrases (never say these):

"Let me just try mid = (lo + hi) / 2…" → name the overflow-safe form immediately.
"Binary search only works on sorted arrays." → wrong and it costs you §2 entirely; it works on any monotone predicate.
[silent re-derivation of the loop bounds every time] → state your one convention up front and stick to it.
"I'll use a heap for the sliding-window max." → correct but O(n log k); the deque is the expected answer.
"I'll sort the intervals" (without saying by what) → the key is the whole decision.

The meta-move across all three: announce the ordering you're exploiting and the invariant it buys you before you write code. "Monotone predicate → halve," "monotone stack → amortized linear," "sort by boundary → linear sweep." That sentence is what separates a senior narration from a junior who happens to know the template.

Cheat-sheet#

Technique	Cue	Template heart	Time	Space	Top trap
Binary search (lower_bound)	sorted; "first index where cond flips"	`[lo,hi)`, `mid=lo+(hi-lo)/2`, `a[mid]<t→lo=mid+1 else hi=mid`	O(log n)	O(1)	mixing half-open/closed
First/last/count	duplicates in sorted array	last=`upper−1`; count=`upper−lower`	O(log n)	O(1)	reading `a[lower]` when `lower==n`
Search on the answer	"min the max / max the min / smallest feasible X"; huge value range	binary-search `feasible(x)` boundary	O(n·log range)	O(1)	non-monotone `feasible`; overflow in sum
Rotated search	rotated sorted array	closed `[lo,hi]`; "which half is sorted?"	O(log n)	O(1)	compare min to `a[hi]` not `a[lo]`
Find min / peak	rotation point; local max	`a[mid]` vs `a[hi]` / `a[mid+1]`	O(log n)	O(1)	wrong pivot comparison
Sorted 2D matrix	rows & cols sorted	start top-right, drop row/col	O(m+n)	O(1)	starting at ambiguous corner
Monotonic stack	next/prev greater/smaller; histogram; span	pop while incoming violates; store indices	O(n)	O(n)	pushing values; missing flush
Monotonic deque	sliding-window max/min	evict expired front, dominated back; front=extreme	O(n)	O(k)	wrong front-eviction condition
Merge / insert intervals	list of `[s,e]`, combine	sort by start, extend frontier	O(n log n)	O(n)	wrong sort key
Greedy interval keep	"min removals / max non-overlap"	sort by end, keep earliest finish	O(n log n)	O(1)	sorting by start
Meeting rooms II	max concurrency	min-heap of ends, or +1/−1 sweep	O(n log n)	O(n)	end-before-start tie-break
Quickselect	one-shot kth in memory	random-pivot partition, recurse one side	O(n) avg	O(1)	fixed pivot → O(n²)
Bounded k-heap	streaming top-k; don't mutate	size-k min-heap, evict smallest	O(n log k)	O(k)	using a max-heap

Binary-search convention card: half-open [lo,hi) → while(lo<hi), hi=mid, lo=mid+1, answer=lo. Closed [lo,hi] → while(lo<=hi), hi=mid-1, lo=mid+1. Maximize-min → round up: mid=lo+(hi-lo+1)/2, lo=mid. Always mid=lo+(hi-lo)/2.

Interval key card: merge / insert / sweep / "can attend all" → sort by start. "Keep the most non-overlapping" / "min removals" → sort by end. Concurrency peak → events, end before start on ties.

Self-test#

Write lower_bound on a half-open interval from memory. What does it return when the target exceeds every element, and why is that not a bug?
Give the overflow-safe mid and explain the exact input size at which (lo + hi) / 2 breaks.
Arrays.binarySearch returns -5 for an absent key. What's the insertion point, and why shouldn't you trust the return index when the array has duplicates?
From cue alone: "minimum ship capacity to deliver all packages within D days." Why binary-search-on-answer and not greedy-alone? Write feasible(cap).
Prove feasible is monotone for Koko's eating speed. What are the correct lo and hi?
In a rotated sorted array, why compare a[mid] to a[hi] and not a[lo] when finding the minimum? Give the array that breaks the a[lo] version.
Why does a monotonic stack run in amortized O(n) despite the nested while? State the accounting argument in one sentence.
Largest rectangle in a histogram: what does the sentinel at i == n do, and what's the width formula when you pop bar j?
Sliding-window maximum: why is a monotonic deque O(n) while a heap is O(n log k)? What makes an element safe to discard forever?
Merge intervals vs "erase overlapping intervals" - which sorts by start, which by end, and why does the greedy one want earliest-end?
Meeting Rooms II: give both the heap solution and the sweep solution. Where exactly does the end-before-start tie-break live in each?
Kth largest: Quickselect vs bounded heap - state the time, space, and the two conditions (streaming, input-mutation) that force the heap.
Why must the Quickselect pivot be randomized, and what input is the adversarial worst case?
"Shortest subarray with sum ≥ k" allows negatives - why does the plain sliding window fail, and what replaces it?
You're maximizing the minimum distance. Show the mid and the boundary update that avoid an infinite loop, and say why the "round down" version spins.

Lineage / sources#

Binary-search discipline (one half-open template, overflow-safe mid, lower_bound/upper_bound as the general form) follows Jon Bentley's Programming Pearls and the classic 2006 "nearly all binary searches are broken" analysis; the (-(insertion point) - 1) contract is the documented java.util.Arrays.binarySearch / Collections.binarySearch behaviour, mirrored by Kotlin's List.binarySearch. Binary-search-on-the-answer, monotonic stack/deque, merge-intervals, and top-k are the standard pattern taxonomy from Grokking the Coding Interview / DesignGurus and NeetCode 150/250; canonical problems (Koko, ship-within-D-days, split-array, rotated search, daily temperatures, largest-rectangle, sliding-window-max, merge/insert-intervals, meeting-rooms, kth-largest) are their LeetCode representatives. Quickselect is Hoare's selection algorithm; the randomized-pivot guarantee is textbook CLRS. Heap and deque internals (why PriorityQueue/ArrayDeque, boxing, cache behaviour) live in the companion data-structures-java-kotlin-study-guide.md; this guide owns only the algorithms.

All code in this file was compiled and unit-tested (Java 21) before inclusion; the Kotlin mirrors the same verified logic against Kotlin 2 / stdlib APIs (kotlin.collections.ArrayDeque uses addLast/removeLast/last(); java.util.ArrayDeque in the Java column uses push/pop/peek). Overlap-boundary conventions (< vs <= at touching endpoints) are problem-dependent - confirm with the interviewer; the defaults here treat touching intervals as mergeable and meeting end-times as reusable.

Binary Search, Monotonic Stack/Deque and Intervals (Java + Kotlin)

The mental model#

1. Binary search - the one template you never get wrong#

The template: lower_bound (first index with a[i] >= target)#

Everything derives from those two#

The library methods - know the exact return contract, then usually don't use them#

2. Binary search ON THE ANSWER - the highest-leverage senior move#

The template#

Koko eating bananas (min eating speed in h hours)#

Capacity to ship packages within D days#

Split array largest sum (min the max subarray sum over k parts)#

3. Binary search on rotated / structured-but-not-fully-sorted input#

Search in a rotated sorted array#

Find the minimum in a rotated sorted array#

Find a peak element (any local max)#

Search a row- and column-sorted matrix (staircase)#

Single element in a sorted array (every other element appears twice)#

4. Monotonic stack - each element pushed and popped once#

Daily temperatures (next strictly-greater, as a distance)#

Next greater element II (circular array)#

Largest rectangle in a histogram#

Trapping rain water (stack version)#

Remove k digits (build the smallest number)#

5. Monotonic deque - a sliding-window max/min in O(n)#

Sliding window maximum#

Shortest subarray with sum at least k (handles negatives)#

6. Intervals and the sweep line#

Merge intervals (sort by START)#

Insert interval into a sorted, non-overlapping list (O(n), no re-sort)#

Non-overlapping intervals (min removals) - sort by END, greedy#

Meeting rooms II (minimum rooms) - two equivalent lenses#

7. Quickselect vs the bounded heap - two ways to do top-k#

Quickselect (Hoare's selection, Lomuto partition + random pivot)#

Bounded k-heap - when the stream, or the input contract, wins#

Problems & how to solve them#

Interview framing / how to sound senior#

Cheat-sheet#

Self-test#

Lineage / sources#

The template: `lower_bound` (first index with `a[i] >= target`)#

Koko eating bananas (min eating speed in `h` hours)#