Find Minimum in Rotated Sorted Array

The problem

An array of n different numbers was sorted from small to large. Then it was rotated: some numbers were taken off the front and put, in the same order, at the back. For example, [1, 2, 3, 4, 5] rotated twice becomes [3, 4, 5, 1, 2]. It may also have been rotated n times, which gives back the sorted array.

You get the rotated array nums, so n is the length of nums. Return its smallest number. Your code must run in O(log n) time.

Example 1

Input: nums = [6, 8, 9, 11, 2, 4, 5]

Output: 2

The sorted array was [2, 4, 5, 6, 8, 9, 11]. Four numbers moved to the back, so 2 now sits at index 4.

nums

608192113244556

Example 2

Input: nums = [3, 1, 2]

Output: 1

The array [1, 2, 3] was rotated once.

Example 3

Input: nums = [1, 4, 7]

Output: 1

Rotated 3 times, which is a full turn. The array is sorted again, so the first number is the smallest.

Constraints

• 1 ≤ n ≤ 5,000
• −5,000 ≤ nums[i] ≤ 5,000
• All numbers are different.
• nums is a sorted array rotated between 1 and n times.

Clarifying questions

Can numbers repeat?

No. All numbers are different. With repeats, the halving trick can get stuck, which is a harder version of this problem.

Can the array be not rotated at all?

Yes, after n rotations it is sorted again. The answer is then the first number.

Do we return the number or its index?

The number.

Is a simple scan allowed?

It gives the right answer, but the problem asks for O(log n). A scan is O(n).

Spot the pattern

The array is almost sorted: two sorted runs, with one drop between them. The problem asks for O(log n), which means halving the search space at every step. That is binary search. The question is how to tell, from one middle number, which half holds the drop.

Solutions

Linear scanO(n)Binary searchO(log n)

Show all

This problem has two approaches. There is no useful step between a full scan and binary search.

Linear scan O(n)

The idea

Look at every number once and keep the smallest. It ignores the sorted structure, but it is always correct. It is a good first answer, and it shows what binary search must beat.

Walkthrough

nums

608192113244556

i

smallest

6

1. smallest = nums[0]
2. for i in range(1, len(nums)):
3. smallest = min(smallest, nums[i])
4. return smallest

Start with the first number as the smallest seen. Then look at every other number once.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Linear scan: look at every number and keep the smallest.
    // Always correct, but it ignores the order, so O(n) time.
    public int findMin(int[] nums) {
        int smallest = nums[0];
        // The drop can be anywhere, so without using the order we must look at all of them.
        for (int i = 1; i < nums.length; i++) {
            smallest = Math.min(smallest, nums[i]);
        }
        return smallest;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line compares one number with the smallest so far. It sits inside one loop. One comparison does not grow with n, so each run is 1 step.

   1. smallest = nums[0]
   2. for i in range(1, len(nums)):
   3. smallest = min(smallest, nums[i])
   4. return smallest

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers. The loop starts at index 1, because index 0 is the starting value. So it looks at indexes 1 to 6.

   6 runs.

   i	1	2	3	4	5	6
   nums[i]	8	9	11	2	4	5

   total

   6 runs

3. 3 Write the count for any n

   The loop runs once for every number after the first:

   n − 1 times

   Check it with Example 1: 7 − 1 = 6.

4. 4 Keep only the part that grows fastest

   Drop the − 1. One run more or less does not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps smallest and i. That is 2 variables, whatever n is, so the space is O(1).

   smallesti

Binary search O(log n)

The idea

Keep a range low..high that always holds the smallest number. Look at the middle position, middle, and compare nums[middle] with nums[high].

• If nums[middle] > nums[high], the numbers go down somewhere between middle and high. That drop is where the smallest number sits. So the answer is to the right of middle: set low = middle + 1.
• Otherwise, middle..high goes up the whole way. Then nums[middle] is the smallest of that part, and the answer is middle itself or to its left: set high = middle. We keep middle, because it may be the answer.

Each step throws away about half the range. When low meets high, one number is left: the smallest.

Why it never misses the answer: each step only drops numbers that are bigger than one we keep, so the smallest number always stays inside low..high.

Walkthrough

nums

608192113244556

lowhigh

1. low, high = 0, len(nums) - 1
2. while low < high:
3. middle = (low + high) // 2
4. if nums[middle] > nums[high]:
5. low = middle + 1
6. else:
7. high = middle
8. return nums[low]

The smallest number is somewhere in low..high. At the start that is the whole array.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Binary search: compare the middle with the right end to find the half
    // that holds the drop. Each step halves the range, so O(log n) time.
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        // low..high always holds the smallest number. Stop when one number is left.
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (nums[middle] > nums[high]) {
                // The numbers go down somewhere after middle, and the drop is the minimum.
                low = middle + 1;
            } else {
                // middle..high is sorted, so nums[middle] beats everything to its right.
                // Keep middle: it may be the answer.
                high = middle;
            }
        }
        return nums[low];
    }
}

Big O

Time O(log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop finds the middle, does one comparison and moves one end. That is the same small job every time, so each run is 1 step. There is one loop. The question is how many times it runs.

   1. low, high = 0, len(nums) - 1
   2. while low < high:
   3. middle = (low + high) // 2
   4. if nums[middle] > nums[high]:
   5. low = middle + 1
   6. else:
   7. high = middle
   8. return nums[low]

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers. The table shows how many numbers are still in low..high before each run. Each run keeps about half of them: 7, then 3, then 2, then 1, and the loop stops.

   3 runs.

   	run 1	run 2	run 3	stop
   numbers left	7	3	2	1

3. 3 Write the count for any n

   Each run halves the range, at least. So after k runs, about n / 2ᵏ numbers are left. The loop stops when 1 is left, so n / 2ᵏ = 1, which means:

   k ≈ log₂ n runs

   Check it with Example 1: log₂ 7 is about 2.8, so 3 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. log₂ n grows very slowly: doubling n adds only one more run. For the largest input, 5,000 numbers, the loop runs at most 13 times.

   So the time is O(log n).

5. S Space: count the extra memory the same way

   The code keeps low, high and middle. That is 3 variables, whatever n is, so the space is O(1).

   lowhighmiddle

Common mistake

Comparing with the left end

Comparing nums[middle] with nums[low] seems the same, but it fails on an array that is not rotated. In [1, 4, 7], the left half looks sorted, so you move right and lose the 1. The right end has no such trap: if nums[middle] < nums[high], the answer is never to the right of middle.

Tested at the limits

2,000 random rotated arrays of 1 to 8 different numbers, rotated by any amount. Then every one of the 5,000 rotations of the largest array. The linear scan and the binary search gave the same answer every time.

Largest inputs	Result
5,000 numbers (the most allowed), with the minimum in the last place, so the search narrows all the way to the right. Binary search.	Under 0.001 s, and under 0.001 MB of extra memory: just three indexes (low, middle and high).