81. Search in Rotated Sorted Array II LeetCode Solution
In this guide, you will get 81. Search in Rotated Sorted Array II LeetCode Solution with the best time and space complexity. The solution to Search in Rotated Sorted Array II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Search in Rotated Sorted Array II
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.
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?
Complexity Analysis
Time Complexity: O(\log n) \to O(n)
Space Complexity: O(1)
81. Search in Rotated Sorted Array II LeetCode Solution in C++
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
const int m = (l + r) / 2;
if (nums[m] == target)
return true;
if (nums[l] == nums[m] && nums[m] == nums[r]) {
++l;
--r;
} else if (nums[l] <= nums[m]) { // nums[l..m] are sorted
if (nums[l] <= target && target < nums[m])
r = m - 1;
else
l = m + 1;
} else { // nums[m..n - 1] are sorted
if (nums[m] < target && target <= nums[r])
l = m + 1;
else
r = m - 1;
}
}
return false;
}
}; /* code provided by PROGIEZ */
81. Search in Rotated Sorted Array II LeetCode Solution in Java
class Solution {
public boolean search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
final int m = (l + r) / 2;
if (nums[m] == target)
return true;
if (nums[l] == nums[m] && nums[m] == nums[r]) {
++l;
--r;
} else if (nums[l] <= nums[m]) { // nums[l..m] are sorted
if (nums[l] <= target && target < nums[m])
r = m - 1;
else
l = m + 1;
} else { // nums[m..n - 1] are sorted
if (nums[m] < target && target <= nums[r])
l = m + 1;
else
r = m - 1;
}
}
return false;
}
} // code provided by PROGIEZ
81. Search in Rotated Sorted Array II LeetCode Solution in Python
class Solution:
def search(self, nums: list[int], target: int) -> bool:
l = 0
r = len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return True
if nums[l] == nums[m] == nums[r]:
l += 1
r -= 1
elif nums[l] <= nums[m]: # nums[l..m] are sorted
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else: # nums[m..n - 1] are sorted
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return False # code by PROGIEZ
