Find Minimum in Rotated Sorted Array

Medium

Goldman Sachs

8 views

Topics:

ArraysBinary Search

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.

Find Minimum in Rotated Sorted Array

Medium

Goldman Sachs

8 views

Topics:

ArraysBinary Search

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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the array?
What should I return if the input array is empty?
Is the array guaranteed to be rotated (i.e., will it always be different from a fully sorted array)?
Is the array sorted in strictly ascending order before rotation?
Can you provide some example inputs and expected outputs?

Brute Force Solution

Approach

We want to find the smallest number in a list that was originally sorted but then rotated. A brute force method involves checking each number individually until we find the smallest.

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the list.
Compare it to every other number in the list.
If you find a number that is smaller than the one you're currently checking, remember that smaller number.
Continue doing this for every number in the list, always keeping track of the smallest one you've found so far.
Once you've checked every number, the one you're remembering is the smallest number in the entire list.

Code Implementation

def find_minimum_brute_force(numbers):
    # Assume the first element is the minimum initially.
    smallest_number_so_far = numbers[0]

    for current_number in numbers:
        # Compare the current number with the smallest found so far.
        if current_number < smallest_number_so_far:

            smallest_number_so_far = current_number

    return smallest_number_so_far

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each of the n elements in the array. For each element, it compares it with every other element in the array to find the smallest element. This involves nested comparisons. Therefore, for each of the n elements, approximately n comparisons are performed, resulting in approximately n*n operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach. This approach only uses a single variable to store the smallest number found so far. The amount of space needed for this variable does not grow with the input size N, where N is the number of elements in the list. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The core idea is to use a divide-and-conquer strategy similar to how you'd look up a word in a dictionary. We repeatedly narrow down the search area until we isolate the smallest element by cleverly comparing sections of the array.

Here's how the algorithm would work step-by-step:

Start by looking at the middle element of the sorted (but rotated) collection.
Compare the middle element to the element at the very beginning.
If the middle element is bigger than the first element, that means the smallest element is somewhere in the right half, so focus only on that part.
If the middle element is smaller than the first element, the smallest element is in the left half (including the middle element), so focus your attention there.
Keep repeating this process of halving the search area until you are left with a very small section.
Eventually, you'll find the point where the order changes - that's where the smallest element lives.

Code Implementation

def find_minimum_in_rotated_sorted_array(numbers):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # If middle element is greater, min is in right half
        if numbers[middle_index] > numbers[right_index]:
            left_index = middle_index + 1

        # If middle element is smaller, min is in left half (or is middle)
        elif numbers[middle_index] < numbers[right_index]:
            right_index = middle_index

        # Duplicates case, reduce search space
        else:
            right_index -= 1

    # left_index is the index of the minimum element
    return numbers[left_index]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm repeatedly halves the search interval. In each iteration, we compare the middle element with the first element and decide whether to search in the left or right half. The number of iterations is proportional to the number of times we can divide the input size n by 2 until we reach a constant size. Therefore, the time complexity is logarithmic, specifically O(log n).

Space Complexity

O(log N) – The described algorithm employs a divide-and-conquer strategy that resembles binary search. This approach recursively narrows down the search space by repeatedly halving it. The space complexity is determined by the depth of the recursion, which, in the worst case, is proportional to the logarithm base 2 of the input size N, where N is the number of elements in the array. Therefore, the maximum space used by the recursion call stack is logarithmic with respect to the input size N, which we approximate as O(log N).

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 or throw an IllegalArgumentException to indicate invalid input; choose an approach that aligns with requirements or assumptions.
Array with only one element	Return the single element as it is trivially the minimum.
Array with two elements, determining the minimum is a simple comparison	Compare the two elements and return the smaller one.
Array is already sorted (no rotation)	Return the first element as it will be the minimum.
Large array (performance concerns for linear search)	Use binary search to achieve logarithmic time complexity for efficient performance with large input sizes.
Array containing negative numbers and zero	Binary search will function correctly as it is based on the relative ordering of elements, regardless of their sign.
Integer overflow during midpoint calculation in binary search (for extremely large arrays)	Use (low + (high - low) / 2) to avoid potential integer overflow when calculating the midpoint in the binary search.
The minimum element is the last element in the array after rotation	The binary search logic correctly handles scenarios where the minimum element is located at the array's tail by properly narrowing the search range.