Skip to content
Hello Python

Search a Rotated Array With Duplicates

Interview ProblemInterviewMediumArrayBinary Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.search(nums, target). nums was rotated and may contain duplicates. Return whether target exists while reducing the search space whenever ordering permits.

Starter code

class Solution:
    def search(self, nums, target):
        pass
Test cases

duplicate-found

{
  "args": [
    [
      2,
      5,
      6,
      0,
      0,
      1,
      2
    ],
    0
  ]
}

Expected: true

Wizard outline
  1. Step 1: Initialize Solution.search

    Replace the empty starter with the first real state owned by Solution.search. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Pass the Duplicate Found case

    Complete the readable core algorithm for one representative Interview case. Handle the ambiguous equal-endpoint case before applying rotated binary-search range logic.

  3. Step 3: Harden the Ambiguous Endpoints boundary

    Repair the reviewed boundary and pass the complete submission contract. Equal endpoints provide no ordering information, and removing them cannot discard a unique target value without another equal copy remaining. Otherwise one half is sorted and range checks safely preserve the target side.

Footguns and prerequisites
  • When left, middle, and right values are equal, neither half can be identified as sorted; shrink both ends.
  • arrays strings two pointers sliding window
Reviewed references
Practice prerequisites
  • Find the First True Boundary(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing search rotated array two as a complete Interview Problem.

Recommended approach and implementation

Use rotated binary search, but shrink both endpoints when left, middle, and right values are equal.

Why it works: Equal endpoints provide no ordering information, and removing them cannot discard a unique target value without another equal copy remaining. Otherwise one half is sorted and range checks safely preserve the target side.

class Solution:
    def search(self, nums, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = (left + right) // 2
            if nums[middle] == target:
                return True
            if nums[left] == nums[middle] == nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[middle]:
                if nums[left] <= target < nums[middle]: right = middle - 1
                else: left = middle + 1
            else:
                if nums[middle] < target <= nums[right]: left = middle + 1
                else: right = middle - 1
        return False
Similar exercises