LeetCode 154: Find Minimum in Rotated Sorted Array II Solution in Python Explained

Problem Statement

In LeetCode 154, you’re given an integer array nums that was sorted in ascending order and rotated (shifted) between 1 and n times, potentially containing duplicates. Your task is to find the minimum element in the array, aiming for O(log n) time complexity. This builds on LeetCode 153: Find Minimum in Rotated Sorted Array, adding complexity with duplicates, and differs from subarray products like LeetCode 152: Maximum Product Subarray.

Constraints

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

Example

Let’s see some cases:

Copy codeInput: nums = [1,3,5]
Output: 1
Explanation: No rotation (or full), min is 1.

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

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

These examples show we’re finding the minimum amidst duplicates.

Understanding the Problem

How do you solve LeetCode 154: Find Minimum in Rotated Sorted Array II in Python? Take nums = [2,2,2,0,1]. Originally [0,1,2,2,2], it’s rotated to place 0 at index 3, the minimum. Duplicates (e.g., multiple 2s) complicate binary search compared to LeetCode 153, requiring special handling. For [3,3,1,3], 1 is the minimum. We aim for O(log n) time, suggesting binary search, not a string task like LeetCode 151: Reverse Words in a String. We’ll use: 1. Binary Search with Duplicate Handling: O(log n) time (average), 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 with Duplicate Handling Approach

Explanation

Binary Search with Duplicate Handling adapts the binary search from LeetCode 153 for duplicates:

• Use two pointers (left, right).
• Compute the middle element.
• Compare mid with right:
• If mid > right, minimum is in the right half.
• If mid < right, minimum is in the left half or at mid.
• If mid == right, shrink right by 1 (duplicates prevent decision).
• Continue until left meets right, pointing to the minimum.

This is the best solution due to its O(log n) average time complexity (worst O(n) with all duplicates), O(1) space usage, and effective handling of duplicates, making it efficient and robust.

For [2,2,2,0,1]:

• Mid=2 == 1, shrink right.
• Mid=2 > 0, search right.
• Minimum at 0.

Step-by-Step Example

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

Goal: Return 1.

• Start: left = 0, right = 2.
• Step 1: mid = 1, nums[mid] = 3, nums[right] = 5.
• 3 < 5, right = 1.
• Step 2: left = 0, right = 1, mid = 0, nums[mid] = 1, nums[right] = 3.
• 1 < 3, right = 0.
• Step 3: left = 0, right = 0, return nums[0] = 1.
• Finish: Return 1.

Example 2: nums = [2,2,2,0,1]

Goal: Return 0.

• Start: left = 0, right = 4.
• Step 1: mid = 2, nums[mid] = 2, nums[right] = 1.
• 2 > 1, left = 3.
• Step 2: left = 3, right = 4, mid = 3, nums[mid] = 0, nums[right] = 1.
• 0 < 1, right = 3.
• Step 3: left = 3, right = 3, return nums[3] = 0.
• Finish: Return 0.

Example 3: nums = [3,3,1,3]

Goal: Return 1.

• Start: left = 0, right = 3.
• Step 1: mid = 1, nums[mid] = 3, nums[right] = 3.
• 3 == 3, right = 2.
• Step 2: left = 0, right = 2, mid = 1, nums[mid] = 3, nums[right] = 1.
• 3 > 1, left = 2.
• Step 3: left = 2, right = 2, return nums[2] = 1.
• Finish: Return 1.

How the Code Works (Binary Search with Duplicate Handling) – 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 [2,2,2,0,1])

    # 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., 2 > 1), min in right half
            left = mid + 1
            # Move left past mid (e.g., 3)
        elif nums[mid] < nums[right]:
            # If mid < right (e.g., 0 < 1), min in left half or at mid
            right = mid
            # Move right to mid (e.g., 3)
        else:
            # If mid == right (e.g., 3 == 3), duplicate, shrink right
            right -= 1
            # e.g., right = 2

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

This detailed breakdown clarifies how binary search with duplicate handling efficiently finds the minimum.

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), even with duplicates. It’s a practical alternative, simple with O(n) time, but doesn’t achieve O(log n), using O(1) space.

For [2,2,2,0,1]:

• 2=2, 2=2, 2>0, min = 0.

Step-by-Step Example (Alternative)

For [3,3,1,3]:

• Step 1: i=1, 3=3, continue.
• Step 2: i=2, 3>1, min = 1, break.
• Finish: Return 1.

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 with Duplicate Handling:
• Time: O(log n) average, O(n) worst (all duplicates).
• Space: O(1) – constant space.
• Linear Search:
• Time: O(n) – single pass.
• Space: O(1) – constant space.

Efficiency Notes

Binary Search with Duplicate Handling is the best solution with O(log n) average time and O(1) space, meeting the efficiency goal despite worst-case O(n) with duplicates—Linear Search uses O(n) time consistently, making it simpler but slower.

Key Insights

• Duplicates: Complicate binary search.
• Binary: Adjusts for equality.
• Linear: Always finds min.

Additional Example

For nums = [1,1,1]:

• Goal: 1.
• Binary: Shrinks to first 1.

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 154: Find Minimum in Rotated Sorted Array II in Python is a challenging search problem. The Binary Search with Duplicate Handling solution excels with its efficiency and adaptability, while Linear Search offers a straightforward fallback. Want more? Try LeetCode 153: Find Minimum in Rotated Sorted Array without duplicates or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 154 on LeetCode with [2,2,2,0,1], aiming for 0—test your skills now!