Search in Rotated Sorted Array II solution and explanation
Google
TCS
Cisco
9 more videos on this problem
Search in Rotated Sorted Array II - Leetcode 81 - PythonNeetCodeIO · 17:36 · 35K views
Search in Rotated Sorted Array II-(Adobe, Amazon, Microsoft....🤩):Live Coding 🧑🏻💻👩🏻💻codestorywithMIK · 20:38 · 16K views
Search in Rotated Sorted Array II | Live Coding with Explanation | Leetcode #81Algorithms Made Easy · 3:35 · 7K views
LeetCode 81. Search in Rotated Sorted Array IIHappy Coding · 15:08 · 2K views
Leetcode - Search in Rotated Sorted Array II (Python)Timothy H Chang · 12:50 · 1K views
Binary Search in Rotated Arrays | LeetCode 81. Search in Rotated Sorted Array II in PythonvanAmsen · 9:03 · 1K views
Search in Rotated Sorted Array II | Leetcode 81 | Array | Binary SearchNitesh Nanda · 15:07 · 506 views
Daily Leetcode #1227: Aug 10, 2023 - 81. Search in Rotated Sorted Array IIProgramming Live with Larry · 25:54 · 278 views
81. Search in Rotated Sorted Array II - Binary Search - LeetCode Daily Challenge - JavaScriptLeetCodeWithMonu · 11:21 · 231 views
BS-5. Search Element in Rotated Sorted Array IItake U forward · 12:44 · 443K views
The problem
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] <= 104numsis 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?
Approach overview
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.
Approach 1: Approach 1: Modified Binary Search
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:
- Ignore duplicate elements by adjusting the left and right pointers when nums[left] == nums[mid] == nums[right].
- Determine the sorted half of the array and decide the search direction.
The time complexity is generally O(log N), but in the worst case with duplicates, it can degrade to O(N).
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
while left < mid and nums[left] == nums[mid]:
left += 1
while mid < right and nums[right] == nums[mid]:
right -= 1
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return Falseclass Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
while (left < mid && nums[left] == nums[mid]) left++;
while (mid < right && nums[right] == nums[mid]) right--;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
}#include <vector>
using namespace std;
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
while (left < mid && nums[left] == nums[mid]) left++;
while (mid < right && nums[right] == nums[mid]) right--;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return true;
while (left < mid && nums[left] === nums[mid]) left++;
while (mid < right && nums[right] === nums[mid]) right--;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}#include <stdbool.h>
bool search(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
while (left < mid && nums[left] == nums[mid]) left++;
while (mid < right && nums[right] == nums[mid]) right--;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}public class Solution {
public bool Search(int[] nums, int target) {
int left = 0, right = nums.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
while (left < mid && nums[left] == nums[mid]) left++;
while (mid < right && nums[right] == nums[mid]) right--;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
}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.
Approach 2: Approach 2: Linear Search (Fallback)
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).
def search(nums, target):
for num in nums:
if num == target:
return True
return Falseclass Solution {
public boolean search(int[] nums, int target) {
for (int num : nums) {
if (num == target) return true;
}
return false;
}
}#include <vector>
using namespace std;
bool search(vector<int>& nums, int target) {
for (int num : nums) {
if (num == target) return true;
}
return false;
}function search(nums, target) {
for (let num of nums) {
if (num === target) return true;
}
return false;
}#include <stdbool.h>
bool search(int* nums, int numsSize, int target) {
for (int i = 0; i < numsSize; i++) {
if (nums[i] == target) return true;
}
return false;
}public class Solution {
public bool Search(int[] nums, int target) {
foreach (int num in nums) {
if (num == target) return true;
}
return false;
}
}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.
Approach 3: Binary Search
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.
- If
nums[mid] > nums[r], it means[l, mid]is ordered. Ifnums[l] \le target \le nums[mid], it meanstargetis in[l, mid]. Otherwise,targetis in[mid + 1, r]. - If
nums[mid] < nums[r], it means[mid + 1, r]is ordered. Ifnums[mid] < target \le nums[r], it meanstargetis in[mid + 1, r]. Otherwise,targetis in[l, mid]. - If
nums[mid] = nums[r], it means the elementsnums[mid]andnums[r]are equal. In this case, we cannot determine which intervaltargetis in, so we can only decreaserby1.
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).
function search(nums: number[], target: number): boolean {
let [l, r] = [0, nums.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] > nums[r]) {
if (nums[l] <= target && target <= nums[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (nums[mid] < nums[r]) {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return nums[l] === target;
}func search(nums []int, target int) bool {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r) >> 1
if nums[mid] > nums[r] {
if nums[l] <= target && target <= nums[mid] {
r = mid
} else {
l = mid + 1
}
} else if nums[mid] < nums[r] {
if nums[mid] < target && target <= nums[r] {
l = mid + 1
} else {
r = mid
}
} else {
r--
}
}
return nums[l] == target
}impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> bool {
let (mut l, mut r) = (0, nums.len() - 1);
while l < r {
let mid = (l + r) >> 1;
if nums[mid] > nums[r] {
if nums[l] <= target && target <= nums[mid] {
r = mid;
} else {
l = mid + 1;
}
} else if nums[mid] < nums[r] {
if nums[mid] < target && target <= nums[r] {
l = mid + 1;
} else {
r = mid;
}
} else {
r -= 1;
}
}
nums[l] == target
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Search in Rotated Sorted Array II easy or hard?
The problem is generally classified as medium difficulty. The base idea of binary search is straightforward, but handling duplicates while still determining the sorted half of a rotated array adds subtle edge cases.
Search in Rotated Sorted Array II Python/Java solution
Most implementations follow the same modified binary search logic across languages. Maintain left and right pointers, compute mid, compare with the target, and adjust boundaries depending on which side is sorted. Python, Java, C++, C#, and JavaScript solutions differ mainly in syntax but use identical algorithmic steps.
How to solve Search in Rotated Sorted Array II in O(n)?
An O(n) solution simply performs a linear scan through the array. Iterate from index 0 to n-1 and check whether any element equals the target value. This approach ignores rotation and duplicates but guarantees correctness with constant space.
What is the best approach for Search in Rotated Sorted Array II?
The best approach uses modified binary search. By checking which half of the rotated array is sorted and narrowing the search space accordingly, you can usually achieve O(log n) time. Duplicates may obscure the sorted side, so the algorithm sometimes shrinks both boundaries, leading to a worst-case O(n).
Is Search in Rotated Sorted Array II asked at Google/Amazon/Meta?
Rotated array search problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants without duplicates are more common, but this version tests how you handle ambiguous ordering caused by duplicate elements during binary search.
What data structure is used in Search in Rotated Sorted Array II?
The problem uses a simple array as the underlying data structure. The main technique applied on top of it is binary search logic with pointer manipulation to determine which half of the rotated array remains sorted.
What is the time complexity of Search in Rotated Sorted Array II?
Modified binary search runs in O(log n) on average because it discards half of the search space each step. However, when many duplicate values appear (for example nums[left] == nums[mid] == nums[right]), the algorithm may only shrink the range by one element at a time, resulting in O(n) worst-case complexity.