Find Minimum in Rotated Sorted Array: Multiple Solutions and Complexity Analysis

Introduction to the Rotated Sorted Array Minimum Problem

Given an array of integers that was originally sorted in ascending order and then rotated at an unknown pivot point, the task is to find the minimum element. The array may contain unique elements or duplicates. This problem is a classic test of algorithmic thinking—especially binary search adaptation—and appears frequently in coding interviews and real-world systems (e.g., circular buffers, rotated logs, time-series databases). This tutorial covers multiple solutions, from brute-force linear scan to optimal binary search, handling both unique and duplicate scenarios, with full complexity analysis and best practices.

Problem Statement

Suppose you have an array nums sorted in ascending order. It is then rotated between 1 and n-1 times. For example, the sorted array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if rotated at index 4. Your goal is to return the minimum element. The array may contain unique values (LeetCode 153) or duplicates (LeetCode 154). In both cases, the minimum is the "pivot" element that marks the rotation point.

Why This Problem Matters

It’s not just an interview puzzle. Rotated sorted arrays model real-world scenarios: circular logs where entries wrap around, ring buffers in embedded systems, or time-series data partitioned into shifted windows. Efficiently finding the minimum (or an insertion point) without linear scanning is crucial for performance in large datasets. Mastering the binary search variations here sharpens your ability to adapt divide-and-conquer techniques to non-standard orderings.

Solution 1: Linear Scan (Brute Force)

Approach

The simplest method: iterate through the entire array, keeping track of the smallest value seen. This works regardless of rotation, duplicates, or even if the array is not sorted. However, it ignores the structure and runs in linear time.

Code

def find_min_linear(nums):
    # Handles empty array by returning None (or raise exception as needed)
    if not nums:
        return None
    min_val = nums[0]
    for num in nums[1:]:
        if num < min_val:
            min_val = num
    return min_val

Complexity

• Time: O(n) — one pass over all elements.
• Space: O(1) — only a single variable.

This approach is acceptable for small arrays or when performance is not critical, but it does not leverage the sorted rotated property.

Solution 2: Binary Search (Unique Elements)

Key Insight

Because the array is sorted and then rotated, it consists of two contiguous sorted segments. The minimum element is the only point where the order "breaks" (the pivot). By comparing the middle element with the rightmost element, we can determine which half contains the minimum.

• If nums[mid] > nums[right], the minimum lies in the right half (mid+1 to right) because the rotation point is between mid and right.
• Otherwise (nums[mid] <= nums[right]), the minimum is in the left half including mid (left to mid), because the right half is already sorted and all values there are greater than or equal to the left half's minimum.

This classic binary search template runs in O(log n) time and works flawlessly for arrays with no duplicates.

Code

def find_min_binary_unique(nums):
    if not nums:
        return None
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            # Minimum is in the right half
            left = mid + 1
        else:
            # Minimum is in the left half (including mid)
            right = mid
    return nums[left]

Dry Run Example

Take nums = [4,5,6,7,0,1,2]. Initially left=0, right=6.

• mid=3, nums[3]=7 > nums[6]=2 → left = mid+1 = 4.
• Now left=4, right=6. mid=5, nums[5]=1 <= nums[6]=2 → right = mid = 5.
• left=4, right=5. mid=4, nums[4]=0 <= nums[5]=1 → right = 4.
• Loop ends (left == right). Return nums[4]=0.

Complexity

• Time: O(log n) — search space halved each iteration.
• Space: O(1) — no recursion or extra data structures.

Solution 3: Binary Search with Duplicates

The Challenge

When duplicates exist, the condition nums[mid] == nums[right] becomes ambiguous: we cannot definitively decide which half contains the minimum. For example, [2,2,2,0,2,2] — at mid=3, nums[3]=0 < nums[5]=2 works, but consider [1,1,1,1] or [10,10,10,10,10,1,10]. If nums[mid] == nums[right], the minimum could be on either side.

Approach

We adapt the binary search: when nums[mid] == nums[right], we cannot eliminate half confidently, so we simply decrement the right pointer. This safely shrinks the search range without discarding a possible minimum, but it degrades performance to O(n) in worst-case scenarios (e.g., all elements equal).

Code

def find_min_binary_duplicates(nums):
    if not nums:
        return None
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            # Minimum must be in right half
            left = mid + 1
        elif nums[mid] < nums[right]:
            # Minimum is in left half including mid
            right = mid
        else:
            # nums[mid] == nums[right] – ambiguous
            # Safely reduce right bound by one
            right -= 1
    return nums[left]

Worst-Case Example

For an array of all identical elements like [2,2,2,2,2], the right -= 1 branch triggers every iteration, leading to O(n) time. In typical cases with few duplicates, it remains near O(log n).

Complexity

• Time: O(log n) average, O(n) worst-case (many duplicates).
• Space: O(1).

Alternative: Early Exit Linear + Binary Hybrid

Some developers combine approaches: if the array is small (say n < 10), linear scan is simpler and constant overhead is tiny. For larger arrays, binary search is invoked. This is an engineering trade-off, not an algorithmic improvement. The code is straightforward:

def find_min_hybrid(nums):
    if len(nums) < 10:
        return min(nums)  # O(n) but negligible overhead
    # Use binary search with duplicate handling as fallback
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right -= 1
    return nums[left]

This is rarely necessary in pure algorithmic challenges but demonstrates pragmatic thinking.

Complexity Analysis Summary

• Brute Force: Time O(n), Space O(1). Simple but ignores sorted structure.
• Binary Search (Unique): Time O(log n), Space O(1). Optimal for distinct elements.
• Binary Search (Duplicates): Time O(log n) average, O(n) worst-case. Space O(1). Handles real-world messy data.
• Hybrid: Time O(n) for tiny arrays, O(log n) otherwise. Engineering choice.

Best Practices

• Validate Input: Always handle empty arrays and single-element arrays. The binary search loops assume at least one element.
• Know Your Data: If duplicates are guaranteed absent (or irrelevant), use the simpler unique binary search. If duplicates may exist, implement the duplicate-safe version.
• Loop Condition: Use while left < right — it ensures termination and avoids off-by-one errors. The final answer is at index left.
• Mid Calculation: Prefer mid = (left + right) // 2 (or left + (right - left) // 2 to avoid overflow in languages with fixed-size integers).
• Pointer Updates: When nums[mid] > nums[right], set left = mid + 1 (exclude mid). Otherwise, set right = mid (include mid). This asymmetry ensures progress.
• Duplicates Handling: The right -= 1 trick is safe and widely accepted; avoid complex three-way compares that may introduce bugs.
• Testing: Cover edge cases: array of one element, array already sorted (rotation 0), fully reversed rotation (max at left, min at right), all duplicates, and alternating duplicates around the minimum.

Real-World Applications

• Circular Buffer Search: In systems with ring buffers, the buffer content is a rotated sorted sequence. Finding the oldest/newest entry is exactly this problem.
• Rotated Log Files: Distributed systems may rotate logs by timestamp; locating the earliest log entry after rotation requires minimum-finding.
• Database Shards: Partition keys that wrap around can be modeled as rotated sorted arrays; quick min/max queries help optimize range scans.
• Cyclic Schedules: In cron-like job scheduling with shifted start times, identifying the earliest future trigger is analogous.

Conclusion

Finding the minimum in a rotated sorted array is a powerful exercise that demonstrates how to adapt binary search to non-standard orderings. Starting from a naive O(n) scan, we progressed to a clean O(log n) binary search for unique elements, then extended it to handle duplicates with a slight degradation. The techniques—comparing against the rightmost element, deciding pointer moves, and safely handling equality—form a reusable template for many rotated-array problems (searching, finding target, counting rotations). Always analyze whether duplicates are present, choose the right variant, and test thoroughly. With these solutions in your toolkit, you can tackle both interview settings and real-world rotated-sequence scenarios with confidence.