LeetCode 153: Find Minimum in Rotated Sorted Array Solution in Python Explained

Problem Statement

In LeetCode 153, you’re given an integer array nums that was sorted in ascending order and rotated (shifted) between 1 and n times. Your task is to find the minimum element in the array, achieving O(log n) time complexity. The array has no duplicates, ensuring a unique minimum. This differs from subarray products like LeetCode 152: Maximum Product Subarray, focusing on searching rather than product optimization.

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• All integers are unique
• Originally sorted in ascending order

Example

Let’s see some cases:

Copy codeInput: nums = [3,4,5,1,2]
Output: 1
Explanation: Rotated at 1: [1,2,3,4,5] → [3,4,5,1,2], min is 1.

Copy codeInput: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: Rotated at 0: [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2], min is 0.

Copy codeInput: nums = [1]
Output: 1
Explanation: Single element, min is 1.

These examples show we’re finding the rotation point’s minimum.

Understanding the Problem

How do you solve LeetCode 153: Find Minimum in Rotated Sorted Array in Python? Take nums = [3,4,5,1,2]. Originally [1,2,3,4,5], it’s rotated to put 1 at index 3, making 1 the minimum. For [4,5,6,7,0,1,2], rotation puts 0 at index 4, the minimum. We need O(log n) time, suggesting binary search over linear scanning. This isn’t a string task like LeetCode 151: Reverse Words in a String; it’s about array searching. We’ll use: 1. Binary Search: O(log n) time, O(1) space—our best solution. 2. Linear Search: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Binary Search Approach

Explanation

Binary Search exploits the rotated sorted property: one half of the array is always sorted, and the minimum lies at the rotation point. Using two pointers (left, right):

• Compute the middle element.
• Compare mid with right: if mid > right, the minimum is in the right half (unsorted); if mid < right, it’s in the left half (sorted).
• Adjust pointers to narrow the search, converging on the minimum.

This is the best solution due to its O(log n) time complexity, O(1) space usage, and efficient use of the array’s structure, meeting the problem’s performance requirement perfectly.

For [3,4,5,1,2]:

• Mid=5 > 2, search right: [1,2].
• Mid=1 < 2, minimum found at 1.

Step-by-Step Example

Example 1: nums = [3,4,5,1,2]

Goal: Return 1.

• Start: left = 0, right = 4.
• Step 1: mid = 2, nums[mid] = 5, nums[right] = 2.
• 5 > 2, unsorted right, left = 3.
• Step 2: left = 3, right = 4, mid = 3, nums[mid] = 1, nums[right] = 2.
• 1 < 2, sorted right, minimum at left = 3, nums[3] = 1.
• Finish: Return 1.

Example 2: nums = [4,5,6,7,0,1,2]

Goal: Return 0.

• Start: left = 0, right = 6.
• Step 1: mid = 3, nums[mid] = 7, nums[right] = 2.
• 7 > 2, left = 4.
• Step 2: left = 4, right = 6, mid = 5, nums[mid] = 1, nums[right] = 2.
• 1 < 2, minimum at left = 4, nums[4] = 0.
• Finish: Return 0.

Example 3: nums = [1]

Goal: Return 1.

• Start: left = 0, right = 0, left == right.
• Finish: Return nums[0] = 1.

How the Code Works (Binary Search) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef findMin(nums: list[int]) -> int:
    # Line 1: Initialize pointers
    left = 0
    # Left boundary (e.g., 0)
    right = len(nums) - 1
    # Right boundary (e.g., 4 for [3,4,5,1,2])

    # Line 2: Binary search loop
    while left < right:
        # Continue while range exists (e.g., 0 < 4)

        # Line 3: Calculate mid point
        mid = left + (right - left) // 2
        # Avoid overflow (e.g., 0+(4-0)//2=2)

        # Line 4: Compare mid with right
        if nums[mid] > nums[right]:
            # If mid > right (e.g., 5 > 2), min in right half
            left = mid + 1
            # Move left past mid (e.g., 3)
        else:
            # If mid < right (e.g., 1 < 2), min in left half or at mid
            right = mid
            # Move right to mid (e.g., 3)

    # Line 5: Return minimum
    return nums[left]
    # Left points to min (e.g., nums[3]=1)

This detailed breakdown clarifies how binary search efficiently finds the minimum in a rotated sorted array.

Alternative: Linear Search Approach

Explanation

Linear Search scans the array sequentially, returning the first element smaller than its predecessor, which is the minimum in a rotated sorted array (or the first element if no rotation). It’s a practical alternative, simple with O(n) time, but doesn’t meet the O(log n) requirement, using O(1) space.

For [3,4,5,1,2]:

• 3 < 4, 4 < 5, 5 > 1, min = 1.

Step-by-Step Example (Alternative)

For [4,5,6,7,0,1,2]:

• Step 1: i=1, 4 < 5, continue.
• Step 2: i=2, 5 < 6, continue.
• Step 3: i=3, 6 < 7, continue.
• Step 4: i=4, 7 > 0, min = 0, break.
• Finish: Return 0.

How the Code Works (Linear Search)

Copy codedef findMinLinear(nums: list[int]) -> int:
    for i in range(1, len(nums)):
        if nums[i] < nums[i-1]:
            return nums[i]
    return nums[0]

Complexity

• Binary Search:
• Time: O(log n) – halves search space.
• Space: O(1) – constant space.
• Linear Search:
• Time: O(n) – single pass.
• Space: O(1) – constant space.

Efficiency Notes

Binary Search is the best solution with O(log n) time and O(1) space, meeting the problem’s efficiency goal—Linear Search uses O(n) time, making it simpler but slower, though space-efficient.

Key Insights

• Rotated Sorted: Min at pivot.
• Binary Search: Leverages sorted halves.
• Linear: Checks all elements.

Additional Example

For nums = [2,1]:

• Goal: 1.
• Binary: Mid=1 < 2, min at 1.

Edge Cases

• Single Element: [1] → 1.
• No Rotation: [1,2,3] → 1.
• Full Rotation: [1,2,3] → 1.

Both solutions handle these well.

Final Thoughts

LeetCode 153: Find Minimum in Rotated Sorted Array in Python is a clever search challenge. The Binary Search solution excels with its efficiency and elegance, while Linear Search offers a straightforward approach. Want more? Try LeetCode 154: Find Minimum in Rotated Sorted Array II with duplicates or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 153 on LeetCode with [3,4,5,1,2], aiming for 1—test your skills now!