Find Minimum in Rotated Sorted Array

Search a 2D Matrix

Find All Anagrams in a String

Find the smallest value in an ascending array that has been rotated an unknown number of times.

You are given an array `nums` of unique integers that was originally sorted in ascending order, then rotated between `1` and `n` times.

Rotating `[0, 1, 2, 4, 5, 6, 7]` four times gives `[4, 5, 6, 7, 0, 1, 2]`. Return the minimum element of the array.

**Input / output**
- Input: `nums: int[]` (all values distinct)
- Output: the smallest value in `nums`

**Examples**
1. `nums = [3, 4, 5, 1, 2]` returns `1`.
2. `nums = [4, 5, 6, 7, 0, 1, 2]` returns `0`.
3. `nums = [11, 13, 15, 17]` returns `11` (no effective rotation).

**Constraints**
- `1 <= nums.length <= 5000`
- `-5000 <= nums[i] <= 5000`
- All values in `nums` are distinct.
- `nums` is a rotation of a strictly ascending array.

**Edge cases**
- The array may not be rotated at all, so the answer is `nums[0]`.
- A single-element array returns that element.

**Target complexity**
- Aim for `O(log n)` time and `O(1)` extra space.

**Hints**
1. The array is split into two ascending runs; the minimum is the start of the second run.
2. Compare `nums[mid]` with `nums[right]` to decide which half still contains the pivot.

**Follow-up**
How would your approach change if the array could contain duplicate values?

- A rotated ascending array is two sorted runs, e.g. `[4,5,6,7]` then `[0,1,2]`.
- The minimum value is exactly the first element of the second run (the pivot).
- If the array is not rotated, the pivot is index `0`.

Read the rotated structure

- The simplest answer is to scan every element and track the smallest.
- This is `O(n)` and ignores the sorted structure, but it is a good correctness baseline.

Brute-force scan

- Compare `nums[mid]` with `nums[right]`.
- If `nums[mid] > nums[right]`, the pivot is to the right, so move `left = mid + 1`.
- Otherwise the pivot is at `mid` or to its left, so move `right = mid`.
- The loop ends when `left == right`, pointing at the minimum.

Binary search on the halves

- Keep halving the search window based on the comparison above.
- No `mid + 1` on the right side, because `mid` itself may be the minimum.

Logarithmic solution

Trace `nums = [4, 5, 6, 7, 0, 1, 2]`.

| left | right | mid | nums[mid] vs nums[right] | action |
|---:|---:|---:|---|---|
| 0 | 6 | 3 | `7 > 2` | `left = 4` |
| 4 | 6 | 5 | `1 <= 2` | `right = 5` |
| 4 | 5 | 4 | `0 <= 1` | `right = 4` |
| 4 | 4 | — | loop ends | answer `nums[4] = 0` |

Dry run

Binary search finds the pivot in `O(log n)` time and `O(1)` extra space.