Find Minimum In Rotated Sorted Array

MEDIUM✓ CHIP-TIMEDLC #153 — FULL STATEMENT ↗

The drill: An originally ascending array of distinct values has been rotated at an unknown pivot — find the smallest value without knowing where the rotation happened.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array that started out fully ascending, with every value distinct, has been rotated some unknown number of positions — picture cutting it at one point and swapping the two pieces.

Somewhere in that rotated arrangement sits the value that used to be first, and it's still the smallest value in the array; the job is to name it without walking the whole array or knowing where the rotation happened.

The rotation leaves behind two runs that are each individually sorted, and the boundary between them is exactly where the minimum lives.

EX 01

nums = [9, 12, 15, 18, 2, 5, 7]

→ 2

ROTATION PIVOT MID-ARRAY

EX 02

nums = [6]

→ 6

SINGLE ELEMENT

EX 03

nums = [8, 3]

→ 3

TWO ELEMENTS, ROTATED ONCE

array holds up to a few thousand elements, all distinct
array is always non-empty and rotated by some amount, possibly zero
only the minimum value itself is expected back, not its index
no duplicate values ever appear in this version of the drill

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A linear scan finds the minimum trivially, but it never uses the fact that both halves of a rotated sorted array are themselves sorted — what property tells you which half the pivot is hiding in?

HINT 2 THE STRUCTURE

Compare the middle element to the last element: if mid > last, the pivot (and the true minimum) is somewhere to the right; otherwise it's at mid or to its left.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search with that rule — move lo past mid when nums[mid] > nums[hi], otherwise pull hi down to mid; lo and hi converge exactly on the minimum.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PIVOT HUNTPATTERN · BINARY SEARCH THE PIVOTnums = [9, 12, 15, 18, 2, 5, 7]

STEP 1

Rotated sorted array, no duplicates. Compare the midpoint against the right edge to find which half hides the pivot and the minimum.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/find-minimum-in-rotated-sorted-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 10 LN

class Solution:
    def findMin(self, nums: List[int]) -> int:
        m = nums[0]
        for v in nums[1:]:
            if v < m:
                m = v
        return m

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 7 LN

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

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 14 LN

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

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED