Skip to main content

🟨 Find Minimum in Rotated Sorted Array (#153)

🔗 Problem Link​

📋 Problem Statement​

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.

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.

💡 Examples​

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.

🔑 Key Insights & Approach​

Core Observation: In a rotated sorted array, the minimum element is where the rotation happened. Binary search by comparing mid with right boundary.

Why Binary Search?

  • O(log n) time complexity required
  • Can determine which half contains minimum based on comparison
  • If nums[mid] > nums[right], minimum is in right half
  • Otherwise, minimum is in left half (including mid)

Approaches:

  1. Linear scan: O(n)
  2. Binary search: O(log n) - optimal

Pattern: "Modified Binary Search" pattern for rotated arrays.

🐍 Solution: Python​

Time Complexity: O(log n) | Space Complexity: O(1)

from typing import List

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

        while left < right:
            mid = left + (right - left) // 2

            # If mid element is greater than right element,
            # minimum must be in the right half
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                # Minimum is in left half (including mid)
                right = mid

        return nums[left]

Approach 2: With Comments​

Time Complexity: O(log n) | Space Complexity: O(1)

from typing import List

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

        # If array not rotated
        if nums[left] < nums[right]:
            return nums[left]

        while left < right:
            mid = left + (right - left) // 2

            # Compare mid with right to determine which side has minimum
            if nums[mid] > nums[right]:
                # Rotation point is to the right
                left = mid + 1
            else:
                # Rotation point is to the left or at mid
                right = mid

        return nums[left]

🔵 Solution: Golang​

Approach: Binary Search​

Time Complexity: O(log n) | Space Complexity: O(1)

func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right-left)/2

        // If mid > right, minimum is in right half
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            // Minimum is in left half (including mid)
            right = mid
        }
    }

    return nums[left]
}

📚 References​