Search in Rotated Sorted Array II | Made Super Easy | Binary Search | ADOBE | AMAZON | Leetcode-81

Similar Problem:

This is the 7th Video on our Binary Search Playlist.
In this video we will try to solve a very famous Binary Search Problem - Search in Rotated Sorted Array II (Leetcode-81)

Trust me, this will no longer be a Medium Problem.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Search in Rotated Sorted Array II
Company Tags : Adobe, Amazon, Microsoft, Morgan Stanley, Samsung, Snapdeal, Times Internet

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Introduction : 00:00
Detailed and Full Dry Run : 2:56

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #interview

[codestorywithMIK]

CORRECTION (08:57):
arr[mid] = 1
arr[r] = 1

😇

[anythingforspeed]

I usually don't comment on any kind of video but man the way you explain DSA problem, covering all the edge cases and explaining each and every line of code .... Hats off ❤

[codestorywithMIK]

Time complexity : O(N) worst case, O(logN) best case, where N is the length of the input array.

[hypewaali]

This playlist is a gem 💎
Done with POTD . Thanks to you ❤

[wearevacationuncoverers]

Thank you for this fantastic explanation

[souravjoshi]

Thanks a lot for this. It looks so easy now

[akshaychavan]

Hi MIK,

I understood this skipping part to make our algorithm work here. However, wouldn't this skipping logic make it O(n) algorithm in worst case? It is as good(rather I should say bad) as Linear Search.

[taneyasoni]

worst case complexity can be O(n). then why not just apply linear search ???

[amitkumaryadav]

what will be time complexity now? it should be O(n) now?

[kishan.]

use set data structure bro(search, insert, delete)->all operations are O(1) --> which is better than binary Search.

[GeniusOG]

Hello Bhaiya,

I am doing question with Java(BEATS 100% in Time Complexity and BEATS 99.5% in Space Complexity),

Is this solution is correct 🤔

In which firstly,

I have implemented two pointer approach to find pivot index which takes O(log n) and then implemented binary search helper function to find whether target is present or not which also takes O(log n)

So overall complexity is O(log n).

Java Code:-

class Solution {
public boolean bs(int[] nums, int start, int end, int target){
while(start<=end){
int mid=(start+end)/2;

if(nums[mid]==target){
return true;
}else if(nums[mid]>target){
end=mid-1;
}else{
start=mid+1;
}
}

return false;
}


public boolean search(int[] nums, int target) {
int startPointer=0;
int endPointer=nums.length-1;

int pivotIndex=-1;

if(nums.length==1){
return nums[0]==target;
}



pivotIndex=startPointer+1;
break;
}


pivotIndex=endPointer;
break;
}

startPointer++;
endPointer--;
}

if(pivotIndex==-1){
return bs(nums, 0, nums.length-1, target);
}

return bs(nums, 0, pivotIndex-1, target) || bs(nums, pivotIndex, nums.length-1, target);
}
}

[tommyshelby]

this approach won't pass if we were to use it in harder problem

[dayashankarlakhotia]

Class solution {
Public boolean search (int[]nums, int target){
int low=0 high=nums.length;
While (low<=high){
int mid= (low +high)/2;
if(nums[mid]==target ||nums[low]==target ||nums [high]==target) return true;
if(nums[low]==nums [high]){ low ++ high--
Continue
}
if((nums [low]<=nums [mid]&&(nums [low]>target ||nums [mid]<target))||(nums [low]>target &&nums [mid]<target)){
low =mid +1}else { high =mid-1
}
return false
}
}

[ayusharyan]

IDK where I'm going wrong
class Solution {
public boolean search(int[] arr, int target) {
int l=0, h=arr.length-1;
while(l<h){
int mid=l+(h-l)/2;
while(l<h&&arr[h-1]==arr[h])
h--;
while(l<h&&arr[l+1]==arr[l])
l++;

if(arr[mid]<=arr[h])
h=mid;
else
l=mid+1;
}
//System.out.println(h);
return bs(arr, 0, h-1, target)||bs(arr, h, arr.length-1, target);
}
public boolean bs(int arr[], int l, int h, int target){
while(l<=h){
int mid=l+(h-l)/2;
if(arr[mid]==target)
return true;
else if (arr[mid]<target)
l=mid+1;
else
h=mid-1;
}
return false;
}
}

[TechieTech-gxkd]

class Solution {
public boolean search(int[] nums, int target) {
return search(nums, 0, nums.length - 1, target);
}

private boolean search(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;

// Now check which side is sorted
if (nums[low] < nums[mid]) {
// Left side is sorted
if (nums[low] <= target && nums[mid] > target) {
return search(nums, low, mid-1, target);
} else {
return search(nums, mid+1, high, target);
}
} else if (nums[low] > nums[mid]) {
// Right side is sorted
if (nums[mid] < target && target <= nums[high]) {
return search(nums, mid+1, high, target);
} else {
return search(nums, low, mid-1, target);
}
} else { // Found duplicate betweeen low and mid
// we found duplicates
return search(nums, low+1, high, target);
}
}
}