How to Solve: Find Minimum in Rotated Sorted Array

How to Solve: Find Minimum in Rotated Sorted Array

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle binary search on non-standard inputs, a skill that separates L4 from L5 engineers."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Search – How to implement it, its time complexity (O(log n)), and edge cases (empty array, single element). 2. Rotated Sorted Arrays – How a sorted array looks after rotation (e.g., [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated at index 3). 3. Invariants in Binary Search – How to maintain the "search space" and adjust pointers based on conditions.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every problem of this type.)

1. Understand the Problem
2. Confirm the array is rotated sorted (e.g., [4,5,6,7,0,1,2]).
3. Clarify if duplicates are allowed (e.g., [3,1,3]).

4. Goal: Find the minimum element (or pivot index).

5. Initialize Pointers

6. left = 0, right = len(nums) - 1.

7. Binary Search Loop

8. While left < right:

   • mid = left + (right - left) // 2 (avoids overflow).
   • Case 1: If nums[mid] > nums[right], the pivot is in the right half (left = mid + 1).
   • Case 2: If nums[mid] < nums[right], the pivot is in the left half (right = mid).
   • Case 3 (Duplicates): If nums[mid] == nums[right], decrement right (right -= 1).

9. Termination

10. When left == right, return nums[left] (the minimum).

11. Edge Cases

12. Empty array → Return None or raise error.
13. Single element → Return that element.

14. Already sorted array → Return nums[0].

15. Time/Space Complexity

16. Time: O(log n) (best case), O(n) (worst case with duplicates).
17. Space: O(1) (iterative approach).

? WORKED EXAMPLES

Example 1 – Basic (No Duplicates)

Problem: Find the minimum in [4,5,6,7,0,1,2].

Step-by-Step: 1. left = 0, right = 6. 2. Iteration 1:
- mid = 3 (nums[3] = 7).
- 7 > nums[6] (2) → Pivot is in the right half (left = 4). 3. Iteration 2:
- mid = 5 (nums[5] = 1).
- 1 < nums[6] (2) → Pivot is in the left half (right = 5). 4. Iteration 3:
- mid = 4 (nums[4] = 0).
- 0 < nums[5] (1) → Pivot is in the left half (right = 4). 5. Termination: left == right → Return nums[4] = 0.

Code (Python):

def findMin(nums):

    left, right = 0, len(nums) - 1

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:

            left = mid + 1

        else:

            right = mid

    return nums[left]

Complexity: O(log n) time, O(1) space.

Why this works: - The key insight is that in a rotated sorted array, one half is always sorted. By comparing nums[mid] with nums[right], we determine which half contains the pivot.

Example 2 – Medium (With Duplicates)

Problem: Find the minimum in [3,1,3].

Step-by-Step: 1. left = 0, right = 2. 2. Iteration 1:
- mid = 1 (nums[1] = 1).
- 1 < nums[2] (3) → Pivot is in the left half (right = 1). 3. Termination: left == right → Return nums[1] = 1.

Code (Python):

def findMin(nums):

    left, right = 0, len(nums) - 1

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:

            left = mid + 1

        elif nums[mid] < nums[right]:

            right = mid

        else:  # nums[mid] == nums[right]

            right -= 1

    return nums[left]

Complexity: O(log n) average, O(n) worst case (e.g., [1,1,1,1]).

Why this works: - When nums[mid] == nums[right], we can’t determine which half is sorted, so we decrement right to skip duplicates.

Example 3 – Hard (Follow-Up: Find Pivot Index)

Problem: Return the index of the minimum element in [4,5,6,7,0,1,2].

Step-by-Step: 1. Same as Example 1, but return left instead of nums[left].

Code (Python):

def findMinIndex(nums):

    left, right = 0, len(nums) - 1

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:

            left = mid + 1

        else:

            right = mid

    return left

Complexity: O(log n) time, O(1) space.

Why this works: - The pivot index is where the rotation occurs, and binary search efficiently narrows it down.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Here’s the 30-second version for your whiteboard: 1. Binary search is your tool—initialize left and right. 2. Compare nums[mid] with nums[right]:
- If nums[mid] > nums[right], the pivot is in the right half (left = mid + 1).
- If nums[mid] < nums[right], the pivot is in the left half (right = mid).
- If they’re equal, skip duplicates (right -= 1). 3. Terminate when left == right—that’s your minimum. 4. Edge cases: Empty array, single element, already sorted. 5. Time complexity: O(log n) best case, O(n) with duplicates.

Now go crush that interview. You’ve got this!

Final Notes

• Practice: Solve variations like [2,2,2,0,1] and [1,3,5] (already sorted).
• Follow-ups: Be ready for "Find the pivot index" or "Search in a rotated array."
• Confidence: This problem tests binary search adaptability—master it, and you’re ready for harder variants.