LeetCode - Search in Rotated Sorted Array II
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.
Problem statement taken from: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/.
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 <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
Explanation
The solution for this problem is similar to the previous Search in Rotated Sorted Array. The only difference is that due to the presence of duplicates, nums[low] == nums[mid] is a possibility and we have to deal with this case separately.
Let's jump directly to the algorithm.
// search function
- if low > high
- return -1
- set mid = low + (high - low) / 2
- if nums[mid] == key
- return true
- if nums[low] == nums[mid + 1] && nums[high] == nums[mid]
- low++
- high--
- search(nums, low, high, key)
if nums[low] <= nums[mid]
- if key >= nums[low] && key <= nums[mid]
- return search(nums, low, mid - 1, key)
- return search(nums, mid + 1, high, key)
if key >= nums[mid] && key <= nums[high]
- return search(nums, mid + 1, high, key)
- return search(nums, low, mid - 1, key)
Let's check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
bool searchUtil(vector<int>& nums, int low, int high, int target) {
if(low > high) {
return false;
}
int mid = low + (high - low)/2;
if(nums[mid] == target){
return true;
}
if(nums[low] == nums[mid] && nums[high] == nums[mid]){
low++;
high--;
return searchUtil(nums, low, high, target);
}
if(nums[low] <= nums[mid]){
if(target >= nums[low] && target <= nums[mid]){
return searchUtil(nums, low, mid - 1, target);
}
return searchUtil(nums, mid + 1, high, target);
}
if(target >= nums[mid] && target <= nums[high]){
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
}
bool search(vector<int>& nums, int target) {
bool result = searchUtil(nums, 0, nums.size() - 1, target);
return result;
}
};Golang solution
func searchUtil(nums []int, low, high, target int) bool {
if low > high {
return false
}
mid := low + (high - low) / 2
if nums[mid] == target {
return true
}
if nums[low] == nums[mid] && nums[high] == nums[mid] {
low++
high--
return searchUtil(nums, low, high, target)
}
if nums[low] <= nums[mid] {
if target >= nums[low] && target <= nums[mid] {
return searchUtil(nums, low, mid - 1, target)
}
return searchUtil(nums, mid + 1, high, target)
}
if target >= nums[mid] && target <= nums[high] {
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
}
func search(nums []int, target int) bool {
return searchUtil(nums, 0, len(nums) - 1, target)
}Javascript solution
var searchUtil = function(nums, low, high, target) {
if(low > high) {
return false;
}
let mid = low + (high - low)/2;
if(nums[mid] == target){
return true;
}
if(nums[low] == nums[mid] && nums[high] == nums[mid]){
low++;
high--;
return searchUtil(nums, low, high, target);
}
if(nums[low] <= nums[mid]){
if(target >= nums[low] && target <= nums[mid]){
return searchUtil(nums, low, mid - 1, target);
}
return searchUtil(nums, mid + 1, high, target);
}
if(target >= nums[mid] && target <= nums[high]){
return searchUtil(nums, mid + 1, high, target);
}
return searchUtil(nums, low, mid - 1, target);
};
var search = function(nums, target) {
return searchUtil(nums, 0, nums.length - 1, target);
};Let's dry run the problem.
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
// search function
Step 1: searchUtil(nums, 0, nums.size() - 1, target)
searchUtil(nums, 0, 6, 0)
// searchUtil function
Step 2: low > high
0 > 6
false
Step 3: mid = low + (high - low)/2
= 0 + (6 - 0)/2
= 0 + 6/2
= 3
Step 4: if nums[mid] == target
nums[3] == 3
0 == 3
false
Step 5: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[3] && nums[6] == nums[3]
2 == 0 && 2 == 0
false
Step 6: if nums[low] <= nums[mid]
nums[0] <= nums[3]
2 <= 0
false
Step 7: if target >= nums[mid] && target <= nums[high]
3 >= nums[3] && 3 <= nums[6]
3 >= 0 && 3 <= 2
false
Step 8: searchUtil(nums, low, mid - 1, target)
searchUtil(nums, 0, 2, 3)
// searchUtil function
Step 9: low > high
0 > 2
false
Step 10: mid = low + (high - low)/2
= 0 + (2 - 0)/2
= 0 + 2/2
= 1
Step 11: if nums[mid] == target
nums[1] == 3
5 == 3
false
Step 12: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[1] && nums[2] == nums[1]
2 == 5 && 6 == 5
false
Step 13: if nums[low] <= nums[mid]
nums[0] <= nums[1]
2 <= 5
true
if target >= nums[low] && target <= nums[mid]
3 >= nums[0] && 3 <= nums[1]
3 >= 2 && 3 <= 5
true
return searchUtil(nums, low, mid - 1, target)
searchUtil(nums, 0, 1 - 1, 3)
searchUtil(nums, 0, 0, 3)
// searchUtil function
Step 14: if low > high
0 > 0
false
Step 15: mid = low + (high - low)/2
= 0 + (0 - 0)/2
= 0 + 0/2
= 0
Step 16: if nums[mid] == target
nums[0] == 3
2 == 3
false
Step 17: if nums[low] == nums[mid] && nums[high] == nums[mid]
nums[0] == nums[0] && nums[0] == nums[0]
2 == 2 && 2 == 2
true
low++
low = 1
high--
high = -1
return searchUtil(nums, low, high, target)
searchUtil(nums, 1, -1, 3)
// searchUtil function
Step 14: if low > high
1 > -1
true
return false
// We go back from Step 14 to Step 9 to Step 2 to Step 1 because of recursion
We return the answer as false.