Find Minimum In Rotated Sorted Array LeetCode Solution [Python]

In this blog post, we’ll tackle the problem of finding the minimum element in a rotated sorted array.

We are given an array of unique elements that were originally sorted in ascending order but have been rotated between 1 and n times.

Our task is to find the minimum element in this rotated array, and we need to do it in O(log n) time.

LeetCode Problem: Find Minimum in Rotated Sorted Array

Problem Overview

Let’s start by understanding the problem in more detail.

Suppose we have an array sorted in ascending order, and it’s rotated one or more times.

For example, the array [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] after being rotated 4 times.

The task is to find the minimum element in this rotated array.

We are guaranteed that the elements in the array are unique.

This means we can’t use a simple linear search to find the minimum element.

Instead, we need to come up with a more efficient algorithm that runs in O(log n) time.

Example 1:

Input: `[3, 4, 5, 1, 2]`
Output: 1
Explanation: The original sorted array was `[1, 2, 3, 4, 5]` and was rotated 3 times.

Example 2:

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

Example 3:

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

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints of the problem:

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

These constraints give us valuable information about the nature of the problem and the potential complexity of our solution.

Find Minimum in Rotated Sorted Array LeetCode Problem Solution

1. Bruteforce Approach

The most straightforward approach to solving this problem is a linear search.

We could scan through the entire array, compare each element to the minimum found so far, and return the minimum value.

However, this approach would have a time complexity of O(n), which doesn’t meet the requirement of O(log n).

2. Efficient Binary Search Approach

To achieve the desired time complexity of O(log n), we will employ a modified binary search algorithm.

This approach takes advantage of the fact that the rotated array can be divided into two sorted subarrays, one on the left and one on the right.

We will use two pointers, left and right, to maintain the range of our search.

We will also keep track of the result, initialized with an arbitrary value from the array (in this case, nums[0]).

While left is less than or equal to right, we continue our search. If we ever reach a point where the entire subarray is sorted, we update the result by taking the minimum of the current result and the leftmost element in the subarray.
If the subarray is not sorted (indicating rotation), we calculate the mid pointer and potentially update the result. We then check whether the mid element is part of the left or right sorted portion using a simple condition: nums[mid] >= nums[left]. If it’s part of the left sorted portion, we move left to mid + 1, indicating that we should search in the right portion. If it’s part of the right sorted portion, we move right to mid - 1, indicating that we should search in the left portion.
We repeat this process until we find the minimum element, and our binary search loop ends.

This approach ensures we search in the correct portion of the array, reducing the search space with each iteration until we find the minimum value.

Python Code Solution

Here’s the Python code for the efficient binary search approach:

View on GitHub ➹

def findMin(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    result = nums[0]

    while left <= right:
        # If the subarray is already sorted, update the result and exit.
        if nums[left] <= nums[right]:
            result = min(result, nums[left])
            break

        mid = (left + right) // 2
        result = min(result, nums[mid])

        # Check if mid is in the left or right sorted portion.
        if nums[mid] >= nums[left]:
            left = mid + 1
        else:
            right = mid - 1

    return result

Time and Space Complexity

Time Complexity: O(log n) – We use a binary search algorithm to find the minimum element, ensuring a logarithmic time complexity.
Space Complexity: O(1) – We use a constant amount of extra space to store variables.

Reasoning Behind Our Approach

The reasoning behind this approach is based on the observation that the rotated array consists of two sorted subarrays.

By comparing the middle element with the left element, we can determine which portion is sorted and adjust our search accordingly.

This binary search strategy reduces the search space in each iteration, leading to an efficient O(log n) solution.

Conclusion

In this blog post, we tackled the LeetCode problem “Find Minimum in Rotated Sorted Array.” We explained the problem, discussed the constraints, and provided an efficient solution using a modified binary search algorithm.

This approach allows us to find the minimum element in a rotated sorted array in O(log n) time.

We hope this explanation helps you understand the problem and its solution better.

If you have any questions, suggestions, or comments, please feel free to ask in the comments section.

We encourage you to share this content with others who might find it helpful.

LeetCode Problem Link

Happy coding!