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 <= 104Follow 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?
The problem asks whether a target value exists in a rotated sorted array that may contain duplicate elements. A direct linear scan would work but would not leverage the sorted structure. The key idea is to adapt binary search while accounting for rotation and duplicates.
Normally, in a rotated array, at least one half of the array remains sorted. By comparing nums[left], nums[mid], and nums[right], we can determine which half is sorted and whether the target lies within that range. However, duplicates can make it difficult to identify the sorted half when values at the boundaries are equal. In such cases, we shrink the search window by moving the pointers inward.
This approach keeps the search efficient in most cases. The typical time complexity is O(log n), but in worst cases with many duplicates, it may degrade to O(n). The algorithm uses O(1) extra space since it only maintains pointers.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Modified Binary Search | O(log n) average, O(n) worst case (due to duplicates) | O(1) |
NeetCode
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).
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.
1def search(nums, target):
2 left, right = 0, len(nums) - 1
3 while left <= rightThis 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.
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).
Both time and space complexities are O(N), since we traverse the entire array.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are commonly asked in technical interviews, including at large tech companies. Interviewers use it to test understanding of binary search, edge cases with duplicates, and reasoning about rotated arrays.
Duplicates can make it difficult to determine which half of the array is sorted during binary search. If the left, middle, and right values are the same, the algorithm cannot decide the sorted side and must reduce the search range linearly.
The problem primarily uses an array and a binary search technique. No additional data structures are required, making the space complexity constant while still leveraging the partially sorted property of the rotated array.
The optimal approach uses a modified binary search. By checking which half of the array is sorted and adjusting the search boundaries accordingly, we can narrow down where the target might exist. When duplicates cause ambiguity, the boundaries are slightly shrunk to continue the search.
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.