153. Find Minimum in Rotated Sorted Array - Solution

The problem

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.

Approach overview

Problem Overview: You receive a sorted array that has been rotated at some unknown pivot. The order is still increasing, but the smallest element is no longer guaranteed to be at index 0. The task is to find the minimum element efficiently without fully sorting or scanning the array unnecessarily.

Approach 1: Iterative Linear Scan (O(n) time, O(1) space)

The most direct approach is to iterate through the array and track the smallest value seen so far. Start with min = nums[0] and update it while traversing each element. Because the array is only partially rotated, this method still works correctly for every case. The downside is performance: you examine every element even though the array retains sorted structure that could be exploited.

A small optimization is checking where the order breaks. During iteration, if nums[i] < nums[i-1], that element is the minimum because rotation creates exactly one drop point. Even with this improvement, worst‑case time complexity remains O(n) with constant O(1) space.

Approach 2: Binary Search (O(log n) time, O(1) space)

The optimal strategy uses binary search. Even though the array is rotated, it still contains two sorted segments. Compare the middle element with the right boundary to determine which half contains the minimum.

If nums[mid] > nums[right], the minimum must be in the right half because the rotation pivot lies there. Move the left pointer to mid + 1. Otherwise, the minimum is in the left half (including mid), so move the right pointer to mid. Continue shrinking the search window until left == right. That index holds the smallest value.

This works because one side of the array is always strictly sorted. The comparison with the right boundary tells you whether the pivot lies to the left or right of mid. Each iteration halves the search space, giving a time complexity of O(log n) with constant O(1) space.

The problem primarily involves arrays and modified binary search. Recognizing that rotation preserves partial ordering is the key insight that allows logarithmic search.

Recommended for interviews: Interviewers expect the binary search solution. A linear scan shows you understand the problem and guarantees correctness, but it ignores the sorted property. The binary search approach demonstrates stronger algorithmic thinking by leveraging the rotated sorted structure to reach O(log n) time.

Approach 1: Binary Search Approach

This approach utilizes binary search to identify the smallest element in a rotated sorted array. The idea is based on the characteristics of the rotated array where at least one half of the array is always sorted. By comparing middle and right elements, we can decide whether the rotation point lies to the left or right of the middle element, effectively narrowing down the search space.

Python

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        else:
            high = mid
    return nums[low]

nums = [3, 4, 5, 1, 2]
print("Minimum is:", find_min(nums))

Java

public class Main {
    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println("Minimum is: " + findMin(nums));
    }
}

C++

#include <iostream>
#include <vector>

int findMin(const std::vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return nums[low];
}

int main() {
    std::vector<int> nums = {3, 4, 5, 1, 2};
    std::cout << "Minimum is: " << findMin(nums) << std::endl;
    return 0;
}

JavaScript

function findMin(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        let mid = Math.floor(low + (high - low) / 2);
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return nums[low];
}

const nums = [3, 4, 5, 1, 2];
console.log("Minimum is:", findMin(nums));

#include <stdio.h>

int findMin(int* nums, int numsSize) {
    int low = 0, high = numsSize - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return nums[low];
}

int main() {
    int nums[] = {3, 4, 5, 1, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Minimum is: %d\n", findMin(nums, size));
    return 0;
}

using System;

public class Solution {
    public int FindMin(int[] nums) {
        int low = 0, high = nums.Length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }

    public static void Main(string[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        Solution solution = new Solution();
        Console.WriteLine("Minimum is: " + solution.FindMin(nums));
    }
}

The Python function find_min uses pointers low and high to perform binary search and identify the smallest element in the array. It narrows the scope to the half of the array where the smallest element resides based on comparison between the mid and high elements.

Complexity

Time Complexity: O(log n) due to the use of binary search.
Space Complexity: O(1), meaning no additional array or data structures are used beyond the input array.

Try this approach in the editor

Approach 2: Iterative Approach

This approach involves linearly iterating through the array to find the minimum value. While it doesn't meet the time complexity requirement of O(log n), it serves as a straightforward method to understand the array's properties and validate the binary search approach.

Python

def find_min(nums):
    min_value = nums[0]
    for num in nums:
        if num < min_value:
            min_value = num
    return min_value

nums = [3, 4, 5, 1, 2]
print("Minimum is:", find_min(nums))

Java

public class Main {
    public static int findMin(int[] nums) {
        int min = nums[0];
        for (int num : nums) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        System.out.println("Minimum is: " + findMin(nums));
    }
}

C++

#include <iostream>
#include <vector>

int findMin(const std::vector<int>& nums) {
    int min = nums[0];
    for (const auto& num : nums) {
        if (num < min) {
            min = num;
        }
    }
    return min;
}

int main() {
    std::vector<int> nums = {3, 4, 5, 1, 2};
    std::cout << "Minimum is: " << findMin(nums) << std::endl;
    return 0;
}

JavaScript

function findMin(nums) {
    let min = nums[0];
    for (const num of nums) {
        if (num < min) {
            min = num;
        }
    }
    return min;
}

const nums = [3, 4, 5, 1, 2];
console.log("Minimum is:", findMin(nums));

#include <stdio.h>

int findMin(int* nums, int numsSize) {
    int min = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

int main() {
    int nums[] = {3, 4, 5, 1, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Minimum is: %d\n", findMin(nums, size));
    return 0;
}

using System;

public class Solution {
    public int FindMin(int[] nums) {
        int min = nums[0];
        foreach (int num in nums) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }

    public static void Main(string[] args) {
        int[] nums = {3, 4, 5, 1, 2};
        Solution solution = new Solution();
        Console.WriteLine("Minimum is: " + solution.FindMin(nums));
    }
}

This Python function iterates over each array element, updating the minimum whenever a smaller value is encountered. This exhaustive search method provides correctness at the cost of linear time and is a good fallback strategy.

Complexity

Time Complexity: O(n) since it potentially checks each element once.
Space Complexity: O(1) indicating limited allocation apart from inputs.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function findMin(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

func findMin(nums []int) int {
	n := len(nums)
	if nums[0] <= nums[n-1] {
		return nums[0]
	}
	left, right := 0, n-1
	for left < right {
		mid := (left + right) >> 1
		if nums[0] <= nums[mid] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return nums[left]
}

Rust

impl Solution {
    pub fn find_min(nums: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] > nums[right] {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        nums[left]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search Approach	Time Complexity: O(log n) due to the use of binary search. Space Complexity: O(1), meaning no additional array or data structures are used beyond the input array.
Iterative Approach	Time Complexity: O(n) since it potentially checks each element once. Space Complexity: O(1) indicating limited allocation apart from inputs.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Linear Scan	O(n)	O(1)	Simple baseline solution or when binary search conditions are not guaranteed
Binary Search	O(log n)	O(1)	Best choice when the array is rotated but originally sorted

Frequently asked questions

Is Find Minimum in Rotated Sorted Array easy or hard?

The problem is typically classified as Medium difficulty. The implementation is short, but recognizing how rotation affects the sorted order and applying binary search correctly requires careful reasoning.

Find Minimum in Rotated Sorted Array Python/Java solution

Most implementations use a binary search loop with left, right, and mid pointers. The logic is identical across languages like Python, Java, C++, C#, and JavaScript, with O(log n) time and constant extra space.

How to solve Find Minimum in Rotated Sorted Array in O(log n)?

Use binary search with two pointers. Compute mid and compare nums[mid] with nums[right]. If nums[mid] is greater, the minimum lies in the right half; otherwise it lies in the left half including mid. Continue until the pointers converge on the smallest element.

What is the best approach for Find Minimum in Rotated Sorted Array?

The best approach uses binary search. Compare the middle element with the right boundary to determine which half contains the rotation pivot. This reduces the search space by half each step, giving O(log n) time and O(1) space complexity.

Is Find Minimum in Rotated Sorted Array asked at Google/Amazon/Meta?

Rotated sorted array problems are common in technical interviews at companies like Amazon, Google, and Meta. Variants include searching in a rotated array, finding the minimum element, or handling duplicates using modified binary search.

What data structure is used in Find Minimum in Rotated Sorted Array?

The problem uses a standard array as the data structure. The key algorithmic technique is modified binary search that exploits the partially sorted property created by rotation.

What is the time complexity of Find Minimum in Rotated Sorted Array?

The optimal binary search solution runs in O(log n) time because the search range is halved every iteration. A simpler linear scan solution exists with O(n) time complexity and O(1) space.

Find Minimum in Rotated Sorted Array solution and explanation

The problem

Approach overview

Approach 1: Binary Search Approach

Approach 2: Iterative Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Minimum in Rotated Sorted Array solution and explanation

The problem

Approach overview

Approach 1: Binary Search Approach

Approach 2: Iterative Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems