Find Minimum in Rotated Sorted Array

• Difficulty: Medium
• Topics: Array, Binary Search
• Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Problem Description

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.

Solution

1. Problem Deconstruction

• Technical Restatement
  Given a rotated sorted array of unique integers, find the minimum element in O(log n) time. The array was originally sorted in ascending order and rotated between 1 and n times.

• Beginner Explanation
  Imagine you have a list of numbers that were sorted from small to large. Then, someone took the last k numbers and moved them to the front. Your job is to find the smallest number in this modified list without checking every single number.

• Mathematical Formulation
  Let nums be an array where ∃ pivot index p such that:

  • nums[p] < nums[p-1] (if p > 0)
  • All elements nums[0...p-1] > nums[p...n-1]
    Find min(nums) = nums[p].

• Constraint Analysis

  • n ≤ 5000: Allows O(n) but requires O(log n) per problem statement.
  • Unique elements: Guarantees a single minimum, simplifying binary search.
  • Rotated 1 to n times: Edge cases include fully rotated (original array) and minimally rotated (pivot at index 1).

2. Intuition Scaffolding

• Real-World Analogy
  Like finding the earliest edition year in a cyclically ordered bookshelf where someone rotated the books.

• Gaming Analogy
  Similar to locating the weakest monster in a dungeon where strength increases but the list wraps around.

• Math Analogy
  Identifying the inflection point in a piecewise monotonic function.

• Common Pitfalls

  1. Global Min Search: O(n) time violates constraints.
  2. Assuming Pivot at Mid: Directly comparing mid to neighbors fails in edge cases.
  3. Overlooking Full Rotation: Missing when the array is unrotated.
  4. Index Errors: Incorrect mid calculation causing infinite loops.
  5. Equality Checks: Unnecessary since elements are unique.

3. Approach Encyclopedia

Binary Search Approach

• Pseudocode

  def findMin(nums):  
      left, right = 0, len(nums) - 1  
      while left < right:  
          mid = (left + right) // 2  
          if nums[mid] > nums[right]:  
              left = mid + 1  
          else:  
              right = mid  
      return nums[left]  
  

• Complexity Proof
  Each iteration halves the search space:

  $$T(n) = T(n/2) + O(1) \implies O(\log n)$$

  Space: O(1).

• Visualization

  Example: [4,5,6,7,0,1,2]  
  Initial: [4,5,6,7,0,1,2]  
               ^mid=3 (7 > 2 → search right)  
  Next: [0,1,2]  
           ^mid=5 (1 < 2 → search left)  
  Next: [0] → return 0  
  

4. Code Deep Dive

• Line-by-Line

  def findMin(nums):  
      left, right = 0, len(nums) - 1  # Initialize search boundaries  
      while left < right:  # Loop until search space is a single element  
          mid = (left + right) // 2  # Find middle index  
          if nums[mid] > nums[right]:  # Pivot is in the right half  
              left = mid + 1  
          else:  # Pivot is in the left half (including mid)  
              right = mid  
      return nums[left]  # Minimum found  
  

• Edge Case Handling
  • Single Element: Loop exits immediately, returns nums[0].
  • Unrotated Array: Binary search converges to left=0.

5. Complexity War Room

• Hardware Impact
  At n=5000, log₂(5000) ≈ 13 iterations → negligible memory/cache usage.
• Approach Comparison

  Approach	Time	Space	Readability	Interview Viability
  Linear Scan	O(n)	O(1)	10/10	❌ Fails O(log n)
  Binary Search	O(log n)	O(1)	9/10	✅ Optimal

6. Pro Mode Extras

• Variant: Multiple Rotations
  If the array had duplicates, binary search would degrade to O(n) in worst case.
• Interview Tips
  • Always clarify element uniqueness and rotation count constraints.
  • Practice dry-runs for edge cases like fully rotated arrays.