Domain 2MediumCORE

Find Minimum in Rotated Sorted Array

We are given an integer array nums that was originally sorted in ascending order but has been rotated (cyclically shifted) some number of times between 1 and n. For example, [1,2,3] becomes [3,1,2] after one rotation. We need to find the minimum element in this array.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Binary Search

153. Find Minimum in Rotated Sorted Array

Model: qwen3.5:9b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 46.4%


Problem Breakdown

We are given an integer array nums that was originally sorted in ascending order but has been rotated (cyclically shifted) some number of times between 1 and n. For example, [1,2,3] becomes [3,1,2] after one rotation. We need to find the minimum element in this array.

Inputs: A list of integers nums. Outputs: The single integer representing the minimum value. Implicit Constraints & Edge Cases:

  • Unique Elements: All elements are distinct (no duplicates). This simplifies binary search logic significantly compared to versions with duplicates.
  • Length: 1≤n1 \le n. We don’t need to handle empty arrays, but we must ensure the code works for a single-element array (n=1n=1) where left equals right.
  • Range: Values are between -5000 and 5000. Standard integer types suffice; no overflow issues in Python or standard languages here.

Intuition

A naive approach would be to iterate through the entire array using a linear scan (O(n)O(n)) to find the minimum value. While this works, it ignores the fact that the input is derived from a sorted sequence. We should leverage the “sorted” property for efficiency.

Since the original array was sorted and then rotated, there exists exactly one point where the order breaks (the pivot). For example: [4, 5, 6] followed by [0, 1, 2]. The minimum element is always at this drop-off or immediately after it. Because we have a monotonic property on either side of the rotation break, we can use Binary Search to find the pivot in O(log⁡n)O(\log n) time instead of scanning every element.

The key insight for binary search here: We compare nums[mid] with nums[right]. Why not left? Because if the array is rotated, the left side might be part of a higher-value segment (e.g., [4...7]). However, we know that within any valid sorted subarray, values increase. If nums[mid] < nums[right], it implies that the range from mid to right is strictly increasing and contains no rotation break inside this specific window; therefore, the minimum must be on the left side (or at mid). Conversely, if nums[mid] > nums[right], we are in a rotated segment where values decrease as indices increase towards the end of that subarray, meaning the pivot/minimum is to the right.

Approach

  1. Initialize two pointers: left pointing to index 0 and right pointing to index n−1n-1.
  2. Enter a loop while left < right. This ensures we narrow down until both point to the same element (the minimum).
  3. Calculate mid = left + (right - left) // 2 to avoid potential overflow in other languages, though Python handles large integers automatically.
  4. Compare nums[mid] with nums[right]:
    • Case A (nums[mid] < nums[right]): The right half [mid...right] is sorted ascendingly. Since the array was originally sorted and rotated, if we are in a sorted segment on the right side of mid, the minimum cannot be to the right of mid. We can discard the right half by setting right = mid.
    • Case B (nums[mid] > nums[right]): The subarray [left...right] is not fully sorted. Since elements are unique and originally ascending, this implies we have crossed the rotation point (the drop). The minimum value must be somewhere between mid + 1 and right. We discard the left half by setting left = mid + 1.
  5. When left == right, that element is guaranteed to be the pivot/minimum because all other elements have been eliminated from consideration as candidates for being smaller than it in a sorted context relative to this search space.

Complexity Analysis

  • Time Complexity: O(log⁡n)O(\log n). We halve the search space with every iteration, characteristic of binary search. Even though we are searching within a rotated array, the logic remains logarithmic because at each step we eliminate half of the remaining candidates based on value comparison.
  • Space Complexity: O(1)O(1). We only use two pointers (left, right) and do not allocate additional data structures proportional to input size.

Solution

def findMin(nums):
    left, right = 0, len(nums) - 1
    
    # Loop until the search space is reduced to a single element
    while left < right:
        mid = (left + right) // 2
        
        # Compare mid with right. 
        # We compare with 'right' because if nums[mid] < nums[right],
        # it implies the segment [mid...right] is sorted ascendingly,
        # meaning the minimum must be to the left of or at mid.
        if nums[mid] < nums[right]:
            right = mid  # Minimum could be here (at mid) or on the left side
        else:
            left = mid + 1  # We are in a rotated segment; min is strictly to the right
        
    return nums[left]

# Example usage for verification
print(findMin([3,4,5,1,2]))      # Output: 1
print(findMin([4,5,6,7,0,1,2])) # Output: 0
print(findMin([11,13,15,17]))   # Output: 11 (Already sorted)

Edge Cases Handled

  • Single Element Array (n=1n=1): The loop condition left < right is false immediately. Returns nums[0], which is correct as it’s the only element and thus minimum.
  • Fully Sorted Array: If rotated nn times (effectively [1,2,3]), logic treats it like a standard sorted array where mid < right always holds until convergence on index 0. Wait, actually if fully sorted ascendingly: e.g., [1,2,3].
    • Iteration 1: mid=1 (val 2). nums[1]=2 < nums[2]=3 -> right = 1.
    • Iteration 2: left=0, right=1. mid=0 (val 1). nums[0]=1 < nums[1]=2 -> right = 0.
    • Loop ends. Returns nums[0]. Correct.
  • Minimum at Start: e.g., [4,5,6,7,0,1,2] (min is 0). Logic correctly identifies that mid > right eventually pushes left pointer past the drop point until it lands on min.
  • Negative Numbers: The logic relies only on relative ordering (<, >), not absolute values, so negative numbers are handled naturally without modification.