LeetCode 81: Search in Rotated Sorted Array II Solution in Python Explained

Problem Statement

LeetCode 81, Search in Rotated Sorted Array II, is a medium-level problem where you’re given an integer array nums that was originally sorted in ascending order, rotated at an unknown pivot index, and may contain duplicates. Your task is to determine if a given integer target exists in the array, returning true if it does and false otherwise. The solution should ideally run in O(log n) time, but duplicates complicate this.

Constraints

  • 1 <= nums.length <= 5000: Array length is between 1 and 5000.
  • -10^4 <= nums[i], target <= 10^4: Values are within this range.
  • nums is sorted and rotated, with possible duplicates.

Example

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Explanation: 0 exists at indices 3 and 4 in the rotated array.

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Explanation: 3 is not in the array.

Input: nums = [1,1,1,1], target = 1
Output: true
Explanation: 1 exists, despite all duplicates.

Understanding the Problem

How do you solve LeetCode 81: Search in Rotated Sorted Array II in Python? For nums = [2,5,6,0,0,1,2] and target = 0, determine if 0 exists—here, it’s true at indices 3 and 4. The array is rotated and sorted but has duplicates, making standard binary search tricky since we can’t always determine which half is sorted. We’ll explore two approaches: a Modified Binary Search Solution (optimal and primary) and an Alternative with Linear Scan (simpler but O(n)). The modified binary search runs in O(n) worst-case time due to duplicates, with O(1) space.

Solution 1: Modified Binary Search Approach (Primary)

Explanation

Adapt binary search to handle rotation and duplicates. Use two pointers, left and right, and a mid-point mid. Compare nums[mid] with target, but since duplicates may obscure which half is sorted, check if nums[mid] == nums[left] to skip duplicates, then determine the sorted half and adjust the search range accordingly.

Here’s a flow for [2,5,6,0,0,1,2], target = 0:

left=0, right=6, mid=3, nums[mid]=0 = target, found

For [1,0,1,1,1], target = 0:

left=0, right=4, mid=2, nums[mid]=1 == nums[left], left=1
left=1, right=4, mid=2, nums[mid]=1 < nums[right], left=2
left=2, right=4, mid=3, nums[mid]=1 > target, right=2
left=2, right=2, mid=2, nums[mid]=1 > target, right=1
left=2, right=1, stop
left=1, right=1, mid=1, nums[mid]=0 = target, found
  1. Initialize Pointers.
  • left = 0, right = n-1.
  1. Binary Search with Duplicate Handling.
  • Skip duplicates, identify sorted half, adjust range.
  1. Check Target.
  • Return true if found, false if range exhausted.
  1. Return Result.

Step-by-Step Example

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

We need true.

  • Goal: Search for 0 in rotated array with duplicates.
  • Result for Reference: true.
  • Start: nums = [2,5,6,0,0,1,2], left = 0, right = 6.
  • Step 1: mid = 3, nums[mid] = 0.
    • 0 = target, return true.
  • Finish: Return true.

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

We need true.

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

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

We need false.

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

Here’s the Python code with line-by-line explanation:

def search(nums: list[int], target: int) -> bool:
    # Line 1: Handle edge case
    if not nums:
        return False

    # Line 2: Initialize pointers
    left, right = 0, len(nums) - 1

    # Line 3: Modified binary search
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return True

        # Line 4: Handle duplicates
        if nums[mid] == nums[left]:
            left += 1
            continue

        # Line 5: Determine sorted half
        if nums[left] <= nums[mid]:  # Left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    # Line 6: Target not found
    return False

Alternative: Linear Scan Approach

Explanation

Use a simple linear scan to check each element for target. This is O(n) time but straightforward, useful when duplicates make binary search degrade to linear complexity anyway.

  1. Iterate Array.
  • Check each element against target.
  1. Return Result.
  • True if found, false otherwise.

Step-by-Step Example (Alternative)

For [2,5,6,0,0,1,2], target = 0:

  • Start: i = 0.
  • Step 1: i = 0, 2 ≠ 0.
  • Step 2: i = 1, 5 ≠ 0.
  • Step 3: i = 2, 6 ≠ 0.
  • Step 4: i = 3, 0 = 0, return true.
  • Finish: Return true.

How the Code Works (Linear Scan)

def searchLinear(nums: list[int], target: int) -> bool:
    # Line 1: Linear scan
    for num in nums:
        if num == target:
            return True

    # Line 2: Target not found
    return False

Complexity

  • Modified Binary Search:
    • Time: O(log n) average, O(n) worst case with many duplicates.
    • Space: O(1) – Only pointers.
  • Linear Scan:
    • Time: O(n) – Single pass through array.
    • Space: O(1) – No extra space.

Efficiency Notes

Modified Binary Search aims for O(log n) time but degrades to O(n) in worst-case duplicate scenarios, using O(1) space, making it preferred for LeetCode 81. Linear Scan is O(n) time and O(1) space, simpler but less efficient, serving as a baseline or fallback.

Key Insights

Tips to master LeetCode 81:

  • Duplicate Handling: Skip when mid equals left.
  • Sorted Half: Identify using mid and endpoints.
  • Rotation: Adapt binary search for pivot.

Additional Example

For nums = [1,3,1,1], target = 3:

  • Goal: true.
  • Binary: mid=1, nums[mid]=3, return true.
  • Result: true.

Edge Cases

  • Single Element: [1], target=1 – Return true.
  • All Duplicates: [1,1,1], target=1 – Return true.
  • No Rotation: [1,2,3], target=2 – Return true.

Final Thoughts

The Modified Binary Search solution is a smart pick for LeetCode 81 in Python—optimized for rotation, handling duplicates, with Linear Scan as a simple fallback. For a related challenge, try LeetCode 80: Remove Duplicates II to switch to array manipulation! Ready to search? Solve LeetCode 81 on LeetCode now and test it with [2,5,6,0,0,1,2] and targets 0 or 3 to master rotated searches. Dive in and find that target!