Blind 75.07 - Find Minimum in Rotated Sorted Array

Find minimum in rotated sorted array.

Problem description

Taken directly from LeetCode.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution type

Binary search (no big fancy idea, just the one specific category of algorithm).

Solution

\(O(n)\) solution is to scan the entire array, and if the array is not rotated at all (just sorted), then it’s \(O(1)\) to just get the start of the array. The part we need to think about is where to find the rotated start of the array.

The start of the array can be defined as the element that decreases in value compared to the previous value. For example, in [4,5,6,7,0,1,2] we know 0 is the minimum because the previous element is greater (7).

\(O(\log(n))\) implies binary search. I can never remember the exact bits of binary search (is right exclusive? Which comparison operator do you use in the while header?), but I figured out this solution that works. This is a little different from standard binary search, and you can and should clean up the logic a bit if this were production code; but this code will set left to the index of the maximum element and right to the index of the minimum element. Which feels dumb because right is the exclusive index…

def findMin(self, nums: List[int]) -> int:
    left, right = 0, len(nums)
    while left + 1 < right:
        middle = (left + right) // 2
        if nums[middle] > nums[left]:
            left = middle
        else:
            right = middle
    return nums[right % len(nums)]

Edge cases to think about: single element, \(n-1\) rotations, \(n\) rotations. Easiest cases to think about when devising the solution are 1, 2, and 3-length arrays.

This is likeliest to show up in a pre-interview screening, where speed matters, so I would submit this and leave it as is. It is definitely irritating because the variables feel wrong!! I want to make it nicer than it is right now. Gah. Just leave it be Kevin, don’t be so perfectionist about everything.

Nice and simple though, only took 10-15 minutes teasing out the right bits in the conditionals.