81. Search in Rotated Sorted Array II

Search in Rotated Sorted Array II (LeetCode 81) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find Min/Max in Rotated Sorted Array subpattern.

• NeetCode 250 · #69 of 250 · Binary Search

How to solve Search in Rotated Sorted Array II

Search in Rotated Sorted Array II is a Binary Search in Rotated Sorted Array problem, part of Binary Search Patterns. Master binary search in rotated sorted arrays. Find minimum, search elements, and handle duplicates.

Work towards the solution in these steps:

1. Consider utilizing a modified binary search approach since the array is sorted but rotated, which helps in achieving better than linear time complexity.
2. Observe that even with rotation, one half of the array (left or right) remains sorted; identifying this sorted half can guide your search direction.
3. Duplicates can obscure the sorted half detection; think about how to handle cases where elements at start, mid, and end indices are equal.

The reference solution runs in O(logn) time and O(1) space.

The Search in Rotated Sorted Array II solution and editorial walks through the full approach with reference code.

Problem statement

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false

Constraints:

- 1 <= nums.length <= 5000

- -104 <= nums[i] <= 104

- nums is guaranteed to be rotated at some pivot.

- -104 <= target <= 104

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Amazon.

How to practise Search in Rotated Sorted Array II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Search in Rotated Sorted Array II in the code editor, or read the Search in Rotated Sorted Array II editorial for a worked solution with its approach and complexity analysis.

Where Search in Rotated Sorted Array II sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• Find Min/Max in Rotated Sorted Array subpattern
• The full DSA patterns sheet

Problems related to Search in Rotated Sorted Array II

Other problems that use the same Find Min/Max in Rotated Sorted Array and Binary Search Patterns techniques:

• Find in Mountain Array — Hard, same subpattern
• Find Minimum in Rotated Sorted Array — Medium, same subpattern
• Find Peak Element — Medium, same subpattern
• Peak Index in a Mountain Array — Medium, same subpattern
• Search in Rotated Sorted Array — Medium, same subpattern
• Binary Search — Easy, same pattern

Search in Rotated Sorted Array II FAQ