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] <= 104nums 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?
Problem Overview: You are given a rotated sorted array that may contain duplicates. The task is to determine whether a target value exists in the array. Unlike the classic rotated array problem, duplicates make it harder to determine which side of the array is sorted, so the search logic needs extra handling.
Approach 1: Modified Binary Search (Average O(log n), Worst O(n) time, O(1) space)
This approach adapts binary search to handle rotation and duplicates. Start with two pointers left and right, compute mid, and check if nums[mid] equals the target. Normally, one half of the rotated array is sorted, which allows you to discard half the search space. The complication appears when nums[left] == nums[mid] == nums[right]; duplicates prevent you from identifying the sorted side. In that case, shrink the window by incrementing left and decrementing right.
If the left half is sorted (nums[left] <= nums[mid]), check whether the target lies between nums[left] and nums[mid]. If it does, move right = mid - 1; otherwise search the other half. If the right half is sorted, apply the same logic symmetrically. This method still behaves like classic rotated-array search in most cases, giving O(log n) performance. However, arrays filled with duplicates can force repeated shrinking of the window, degrading to O(n).
The algorithm uses only index comparisons and constant extra memory, making it efficient and suitable for large arrays. Since the problem revolves around rotated ordering and conditional partitioning, it heavily relies on array traversal combined with decision logic typical in binary search problems.
Approach 2: Linear Search (Fallback) (O(n) time, O(1) space)
The simplest solution iterates through the entire array and checks whether any element equals the target. Use a single loop from index 0 to n-1 and return true when a match is found. If the loop completes without finding the target, return false. This approach ignores the rotated sorted structure completely.
Linear search works reliably regardless of duplicates, rotations, or array ordering. It also becomes the theoretical worst-case behavior of the modified binary search when duplicates prevent meaningful partitioning. While not optimal for large inputs, it is trivial to implement and useful as a correctness baseline or fallback during debugging.
Recommended for interviews: Interviewers expect the modified binary search solution. It shows you understand how rotation affects ordering and how duplicates complicate the decision about which half is sorted. Mentioning the linear scan demonstrates awareness of the brute-force baseline, but implementing the binary search variation shows stronger algorithmic reasoning.
This approach uses a modified binary search to handle the rotated sorted array with duplicates. Normally, in a binary search, you would compare the middle element with the target and adjust your search range accordingly. However, because this array is rotated, the sorted order is disrupted, and duplicates can complicate matters.
The key steps are:
The time complexity is generally O(log N), but in the worst case with duplicates, it can degrade to O(N).
This Python implementation of the modified binary search accounts for duplicates by checking for duplicate middle elements. If they exist, the algorithm adjusts the search boundaries while maintaining the sorted distinction in either half of the array.
The time complexity is O(log N) in the average case, but O(N) in the worst case due to duplicates. The space complexity is O(1) since no extra storage is needed.
In cases of heavy element duplication, when the above methods become inefficient, a linear search ensures completion of the task. Though not ideal for large-sized arrays, this method provides a simple, guaranteed solution without involving complicated logic.
The complexity for linear search is both time and space O(N).
In this simplistic Python solution, we loop through the entire array, checking each element for equality with the target, making it a reliable brute-force method.
Both time and space complexities are O(N), since we traverse the entire array.
We define the left boundary of the binary search as l = 0 and the right boundary as r = n - 1, where n is the length of the array.
Each time during the binary search, we get the current midpoint mid = (l + r) / 2.
nums[mid] > nums[r], it means [l, mid] is ordered. If nums[l] \le target \le nums[mid], it means target is in [l, mid]. Otherwise, target is in [mid + 1, r].nums[mid] < nums[r], it means [mid + 1, r] is ordered. If nums[mid] < target \le nums[r], it means target is in [mid + 1, r]. Otherwise, target is in [l, mid].nums[mid] = nums[r], it means the elements nums[mid] and nums[r] are equal. In this case, we cannot determine which interval target is in, so we can only decrease r by 1.After the binary search, if nums[l] = target, it means the target value target exists in the array. Otherwise, it does not exist.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Modified Binary Search | The time complexity is O(log N) in the average case, but O(N) in the worst case due to duplicates. The space complexity is O(1) since no extra storage is needed. |
| Approach 2: Linear Search (Fallback) | Both time and space complexities are O(N), since we traverse the entire array. |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modified Binary Search | O(log n) average, O(n) worst | O(1) | Best general solution for rotated sorted arrays with duplicates |
| Linear Search (Fallback) | O(n) | O(1) | Small arrays, quick baseline implementation, or debugging |
Search in Rotated Sorted Array II - Leetcode 81 - Python • NeetCodeIO • 32,735 views views
Watch 9 more video solutions →Practice Search in Rotated Sorted Array II with our built-in code editor and test cases.
Practice on FleetCode