How should I practice Search in a Rotated Sorted Array with Duplicates?

Start by reading the full statement, solve the visible examples, then compare the pattern against related ByteDance phone screen problems in FastPrep.

Is Search in a Rotated Sorted Array with Duplicates associated with ByteDance?

FastPrep tags this as a ByteDance phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Search in a Rotated Sorted Array with Duplicates

Learn this problem

● Medium

ByteDanceINTERNPHONE SCREEN

Problem statement

Given an integer array nums that was sorted in nondecreasing order and then rotated at an unknown pivot, return the lowest array index whose value equals target.

The array may contain duplicate values. If target does not occur, return -1.

Your algorithm should use the sorted, rotated structure to discard unambiguous regions. Because duplicate boundary values can hide the sorted side, the worst case may require examining every element.

Function

search(nums: int[], target: int) → int

Examples

Example 1

nums = [2,5,6,0,0,1,2]target = 0return = 3

The target occurs at indices 3 and 4, so the lowest matching index is 3.

Example 2

nums = [1,1,3,1]target = 3return = 2

The array is a rotation of a nondecreasing array and the only 3 is at index 2.

Example 3

nums = [4,4,5,1,2,4]target = 3return = -1

The target does not occur, so the result is -1.

Constraints

1 <= nums.length <= 100000.
-2147483648 <= nums[i], target <= 2147483647.
Before rotation, nums was sorted in nondecreasing order.
nums may contain duplicate values.
The array was rotated at an arbitrary pivot, including a rotation by zero positions.