153. Find Minimum in Rotated Sorted Array

MediumArrayBinary Search
Leetcode Link

Problem Description

The problem presents an array containing a sequence of numbers in ascending order that has been rotated between 1 and n times. A rotation means that the elements are shifted to the right by one position, and the last element is moved to the first position. The task is to find the minimum element in this rotated array. The challenge is to achieve this with an algorithm that runs in O(log n) time, which suggests that a binary search approach should be used because binary search has a logarithmic time complexity and is typically applied to sorted arrays to find a specific element quickly.

Intuition

The key to solving this problem lies in understanding how a rotation affects a sorted array. Despite the rotation, a portion of the array remains sorted. If the array is not rotated or has been rotated a full cycle (n times), then the smallest element would be at the beginning. If it is rotated, the array is composed of two increasing sequences, and the minimum element is the first element of the second sequence.

Therefore, we can use binary search to quickly identify the point where the transition from the higher value to the lower value occurs, which indicates the smallest element. The binary search is modified here to compare the middle element with the first element and decide where to move next:

  1. If the middle element is greater than the first element, the smallest value must be to the right of the middle element. Hence, we search the right half of the array.
  2. If the middle element is less than the first element, then the smallest value is somewhere to the left of the middle element, or it could be the middle element itself. Here, we search the left half.

By applying this logic recursively to the halves, the point at which the smallest element exists can be found efficiently, satisfying the required time complexity.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The implementation of the solution leverages a binary search algorithm to find the minimum element in the rotated array. Here are the detailed steps of the algorithm:

  1. First, the solution checks if the first element of the array is less than or equal to the last element. If true, this indicates that the array is not rotated, or it is rotated a full cycle. Hence, the first element is already the minimum, and we can return it immediately.

    1if nums[0] <= nums[-1]:
2    return nums[0]

  2. If the previous check fails, the solution sets two pointers, left and right, at the start and the end of the array, respectively. These pointers are used to dynamically narrow down the search region while performing the binary search.

    1left, right = 0, len(nums) - 1

  3. The algorithm enters a loop that continues as long as the left pointer is less than the right pointer. The purpose of this loop is to repeatedly narrow the search space until the minimum element is identified.

    1while left < right:

  4. Inside the loop, the solution calculates the mid point between left and right pointers. This mid point is used to compare the elements and decide which half of the array to search next.

    1mid = (left + right) >> 1

  5. The next step is to compare the element at the mid index with the first element in the array. If nums[mid] is greater than nums[0], we know that the smallest element must be to the right of mid, so we move the left pointer to mid + 1.

    1if nums[0] <= nums[mid]:
2    left = mid + 1

  6. Otherwise, if nums[mid] is less than nums[0], the minimum element is to the left of mid, or it could be mid itself, so we move the right pointer to mid.

    1else:
2    right = mid

  7. The loop continues until the left and right pointers converge to the index of the minimum element. At this point, we can return nums[left] as the minimum element of the array.

    1return nums[left]

This approach guarantees that the running time will be O(log n) because it repeatedly eliminates half of the search space in each iteration, which is characteristic of a binary search.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following rotated array:

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

Initially, we check if the array is not rotated or has been rotated a full cycle:

1if nums[0] <= nums[-1]:
2    return nums[0]

However, nums[0] is 4 and nums[-1] is 2, so we do not return nums[0] because the array has been rotated.

Next, we set our left and right pointers:

1left, right = 0, len(nums) - 1

Hence, left = 0 and right = 6.

Entering the loop, we calculate our mid index:

1mid = (left + right) >> 1

This gets us mid = 3, with nums[mid] = 7.

We now compare nums[mid] with nums[0]. Since 7 (middle element) is greater than 4 (the first element), we update the left to mid + 1:

1left = mid + 1

Now, left = 4 and right = 6.

On the next iteration, mid = (4 + 6) >> 1 = 5. The value nums[mid] is 1, which is less than nums[0].

Since nums[mid] is less than nums[0], we update the right pointer to mid:

1right = mid

Now, left = 4 and right = 5.

Continuing with the loop, we calculate the next mid:

1mid = (left + right) >> 1 = (4 + 5) >> 1 = 4

The value at mid index is 0, which is less than nums[0]. So, we update the right pointer to mid again:

1right = mid

Since now both left and right are 4, the loop terminates, and we return the value nums[left] which is 0, the smallest element in the rotated array:

1return nums[left]

Thus, following the provided approach, we efficiently find the minimum element in a rotated sorted array in O(log n) time.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMin(self, nums: List[int]) -> int:
5        # If the array is not rotated (or sorted in ascending order), 
6        # then the smallest element is the first element.
7        if nums[0] <= nums[-1]:
8            return nums[0]
9      
10        # Initialize the left and right pointers.
11        left, right = 0, len(nums) - 1
12      
13        # Perform a binary search for the minimum element.
14        while left < right:
15            # Calculate the midpoint index
16            mid = (left + right) // 2  # Using // for floor division in Python 3
17          
18            # If the element at the midpoint is greater than or equal 
19            # to the first element, then the minimum is to the right.
20            if nums[0] <= nums[mid]:
21                left = mid + 1
22            else:
23                # Otherwise, the minimum is to the left, so we reduce the right bound.
24                right = mid
25      
26        # After the loop, left will point to the smallest element.
27        return nums[left]
28
1class Solution {
2    public int findMin(int[] nums) {
3        int length = nums.length; // Store the length of the array for quick access
4      
5        // If the first element is less than or equal to the last element,
6        // the minimum element must be at the starting index since the array is not rotated.
7        if (nums[0] <= nums[length - 1]) {
8            return nums[0];
9        }
10      
11        // Initialize pointers for binary search
12        int left = 0;
13        int right = length - 1;
14      
15        // Conduct binary search to find the minimum element index
16        while (left < right) {
17          
18            // Midpoint calculation
19            int mid = left + (right - left) / 2;
20          
21            // Compare middle element with the first element to decide where to continue the search.
22            // If nums[0] is less than or equal to nums[mid], the rotation index must be to the right 
23            // of mid, hence we adjust left to mid + 1.
24            if (nums[0] <= nums[mid]) {
25                left = mid + 1;
26            } else {
27                // If nums[0] is greater than nums[mid], the rotation index must be at mid or
28                // to the left of mid, hence we adjust right to mid.
29                right = mid;
30            }
31        }
32      
33        // After the search, left would be pointing at the minimum element in the rotated array.
34        return nums[left];
35    }
36}
37
1#include <vector> // Include the vector header for using the vector data structure
2
3class Solution {
4public:
5    // Function to find the minimum element in a rotated sorted array
6    int findMin(std::vector<int>& nums) {
7        int size = nums.size(); // Get the size of the vector
8      
9        // If the first element is less than or equal to the last element, 
10        // then the array is not rotated, so return the first element
11        if (nums[0] <= nums[size - 1]) {
12            return nums[0];
13        }
14      
15        int left = 0; // Initialize left pointer to the start of the array
16        int right = size - 1; // Initialize right pointer to the end of the array
17      
18        // Binary search to find the pivot, the smallest element
19        while (left < right) {
20            int mid = left + (right - left) / 2; // Find the mid index to prevent overflow
21          
22            // If the first element is less than or equal to the mid element,
23            // then the smallest value must be to the right of mid
24            if (nums[0] <= nums[mid]) {
25                left = mid + 1;
26            } else { // Otherwise, it is to the left of mid
27                right = mid;
28            }
29        }
30      
31        // At this point, left is the index of the smallest element
32        return nums[left];
33    }
34};
35
1/**
2 * Finds the minimum value in a rotated sorted array.
3 * @param {number[]} nums - An array of numbers which has been rotated.
4 * @returns {number} - The minimum value in the array.
5 */
6function findMin(nums: number[]): number {
7    // Initialize two pointers for the start and end of the array segment.
8    let start = 0;
9    let end = nums.length - 1;
10
11    // Use binary search to find the minimum element.
12    while (start < end) {
13        // Find the middle index by averaging start and end.
14        const middle = (start + end) >>> 1;
15
16        // Determine which part of the array to continue searching in.
17        if (nums[middle] > nums[end]) {
18            // If middle element is greater than end element,
19            // the smallest value must be to the right of middle.
20            start = middle + 1;
21        } else {
22            // Otherwise, the smallest value is to the left of middle, or at middle.
23            end = middle;
24        }
25    }
26
27    // When the while loop ends, start points to the smallest element.
28    return nums[start];
29}
30
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

The provided Python code implements a binary search algorithm to find the minimum element in a rotated sorted array. Here is the analysis of its time and space complexity:

Time Complexity:

The time complexity of the algorithm is O(log n), where n is the length of the input list nums. This is because the algorithm uses a binary search approach, where it repeatedly divides the search interval in half. At each step, the algorithm compares the middle element with the boundary elements to determine which half of the array to search next. The number of steps required to find the minimum will, therefore, be proportional to the logarithm of the array size.

Space Complexity:

The space complexity of the algorithm is O(1), as it uses only a constant amount of extra space. The variables left, right, and mid used for maintaining the bounds of the search space and no additional data structures are allocated that would depend on the size of the input list. Thus, the memory requirement remains constant irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫