BS-6. Minimum in Rotated Sorted Array

[@takeUforward]

Please comment understood and give us a like if you got everything :)

[@vishnusiddarth7953]

mass

[@sudhanshushekhar4222]

Understood

[@ersoumyajitpan7205]

************ more optimized ************ int findMin(vector& nums){ int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; }

[@adil_k]

East or west. Striver is the best

[@CheragAli69]

I came only for Minimum in Rotated Sorted Array so why I would seen previews video #striver ?

[@shivajirao999]

the feeling of writing the exact same code by your own without even looking at the lecture is insane, ALL thanks to your level of explanation

[@ravikr3463]

Abe easy hai ye upper ke 3 phele se kiye hue the esiliyee btw good

[@Rahul_Mongia]

@@ravikr3463

[@akshatgupta8787]

@@ravikr3463 bhai merse wo karne ke baad bhi nahi hua yrr

[@hithardhksvln5302]

same here bro, solved one more problem in the same way.

[@abhishekverma7604]

guys, this is one of the most important question if u r preparing for amazon and adobe.. hell they asked it a lot in previous 6 months according to Leetcode stats..

[@animeshshaw388]

Thanks brother 🙏🏾

[@akshitbhasin7322]

The fact that you acknowledged the problem of having different formats in binary search deserve a like. keep up the good work!

[@HananTariq-ws9wd]

Understood!! Hi I'm a Pakistani and I study at US. I really like your DSA playlist and recommend it to everyone. Thank you so much for your effort.

[@AmanSingh-wr6mj]

Pucha kisine?

[@travelbest5623]

Ab ji*@d recruitment mai bhi dsa poochne lage kya? 😂😂

[@vishious14]

6 minutes into the video, I was able to deduce the whole logic as soon as I understood the approach !!!!!! Amazing content !!!!!!

[@ayushpatidar5778]

The way you cover each and every edge case is amazing. Understood everything 👍

[@ArdentMusicLover]

Thank you, Striver. Using your approach , I was able to solve the minimum in Rotated Sorted Array-II as well , which is a LC-Hard. Hats off to you!

[@shrirambalaji2915]

just watched like 7 min and understood the solution and what i am missing out thanks man you are awesome

[@iWontFakeIt]

man what an explanation ! I saw several solutions on leetcode discuss but couldn't understand all of it, some if else conditions were going above my head, but you made it so clear I did code it myself both leetcode 153 and 154 with AC solutions

[@surendhar.v4952]

If hurts the most , when you realize this easy question took you more than 2 hour and failed several time while in the test cases below 5 when you submit in leetcode. I did a course on java in youtube from a famous youtuber an year ago. I took a short break of two months for my semster exam and other activities. I can remind that I solved a similar type of question in an year ago. But now , I am struggling to do a easy problem like this.... Taking a break, even it is small gets your mind out of the programming mode.

[@vaibhavvm4147]

bro where did u do dsa in java from?

[@deepakjain4481]

i guess its medium

[@mehulthuletiya497]

00:38 Problem statement 01:21 Brute-force approach 01:38 Optimal approach 06:30 Dry-run 10:35 Pseudocode 12:57 Code 13:20 Optimised version : If you want try to do then 15:04 Code 15:27 Complexity

[@abhaymaurya9]

the same exact code i was able to write down without even watching your lecture first , kudos to u🙌❣

[@bhushanambhore8378]

I felt proud of myself of solving this question in o(logn) time without even looking this video cz obviously I've seen your previous 2 videos and of course able to solve this one 😎.. Thank you Striver.

[@puzzle-headed-cat]

Understood! These are the kinda explanations I was looking for. Thank you so much for all the hard work and sharing with us!

[@RagaviSathiyamoorthy]

I'm really blessed to watch and learn the concept form you striver and i'm solving the problems now without referring the solutions. Thanks a lot.

[@photon7404]

Understood bro. I almost got the intuition just left unsolved due to this min() method. great explaination. Thank you

[@rathiManikandan2000]

I must tell you, you are an excellent teacher.. Keep up the good work.

[@Charmask_creation]

class Solution { public: int findMin(vector& nums) { sort(nums.begin(),nums.end()); return nums[0]; } };

[@gouravp.3851]

it's order of "NLogN" even worse than linear search

[@TasneemMohammad-oj3ie]

the first prob that was done by myself in the medium list(ive been wanting to write a cmmnt like this forever) Thankyou!

[@harshitgarg2820]

Striver sir plz start a series for strings to simplify strings for us just like you did with the other topics🙏

[@parth2439]

Understood, the last optimisation was great !!

[@SahitiDantuluri]

I have gone through some solutions to this problem and able to understand but if I try to recollect and code it later I would be a little confused. But your explanation and approach is so detailed and very easy to understand that I am able to solve it on my own without any confusion (even after many days). Thanks a lot!!

[@Halid-pl1to]

Understood!!!!! you are the state of the art brother

[@RajeshS-n2j]

You are the only one who considered the case that minimum can lie in sorted half as well, that is cool. 😄Many others who provided a solution simply eliminated the sorted half without really giving any explanation.

[@Adityakumar-dl4vc]

Thanks , from past 2 day i stuck in this , but now it all clear ❤❤❤ thanks

[@snowpieee]

I was solving this for the first time , was struggling because everytime was giving me runtime error and guess what i lerally watched the first 10 mins only infinite times , because my dumb brain was just not convincing myself that how is this done, at 3pm night i passed this that too in 0ms time without seeing your written code 😭😭😭😭😭. It was giving me stress because i haven't been able to pass a single solution that day so i really needed anything to get accepted just to boost my morale . Thanks striver.

[@Cubeone11]

I used to think that neetcode gives the best explanation, but after watching this playlist i changed my thoughts.

[@AyushEditz-hs6pf]

This works as well: first check if the right side of mid is sorted then check of left side. int findMin(vector& nums) { int ans=INT_MAX; int low=0; int high=nums.size()-1; while(low

[@anishaa3298]

I was able to solve this without looking at the pseudocode 😭. thank you Striver. but i still watch till the end.

[@rishabhgupta9976]

Thank you so much for the explanation Striver! :D I think the variable ans that contains the minimum is not that necessary and we can work without it as well. def findMin(self, nums: List[int]) -> int: l = 0 r = len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] > nums[r]: # If the unsorted portion is to the right, the minimum must be there, # as the rotation point lies beyond the middle of the array. l = m + 1 else: # If the unsorted portion is to the left, we need to consider that # the middle element could also be the minimum. # This happens when the array is rotated by exactly half its size. r = m return nums[l]

[@visase2036]

Thanks Striver. Adding my thoughts for (duplicates) . If we apply the previous logic of high-- or low++ as the mid and low/high values are equal , we will end up getting the minimum element but that does not gaurentee the no of times array has been rotated . Examples: array=[1,1,2,1,1] , orignal array = [1,1,1,1,2]. The correct answer is 3 (as the element at 0th index has been moved to 3rd index [1,1,2,1,1]). But if we apply the previous logic, the answer would come as 0 as 0th index is the minimum element. To upsolve this, we can do the following : Keep reducing high, untill [high-1] > [high] (2>1). Once you attain this point, high(3rd index) will be the answer.

[@floatingpoint7629]

this does not cover all the cases

[@ayushmittal9666]

I think if we remove the condition of checking if(a[low]

[@deepakff7498]

you are binary search playlist is goated bro

[@himanshusingh1899]

Best DSA course on you tube.

[@sukhjattana5887]

u unfolded the mysterious binary search....thank you!!!

[@dhruvdonsahu9972]

this one works and its less complex: int low=0; int high=nums.size()-1; int min=INT_MAX; while(low

[@prajeetdubey8213]

Key takeaway from this problem: 1) Basically if the array is rotated either the left or right of the mid will definitely be sorted. So make use of it. 2) Once you find the sorted subarray you definitely know that its 1st element is the smallest so put it in ans. Now no need of that subarray. (if arr[low]

[@cinime]

Understood! Awesome explanation as always, thank you soooo much for your effort!!

[@MansiBansalc]

YOU ARE AN AMAZING TEACHER! THANKYOU FOR EXISTING!

[@namangarg8976]

Another approach I thought of - -> If left array is sorted, right is unsorted. Then go to right as pivot point can be current element or in right array -> If right is sorted, left is unsorted. Then go to left as pivot point can be current element or in left array -> If both are sorted then break and just compare the ans with arr[low] as complete search space is sorted. int findMin(vector& arr) { int low = 0; int high = arr.size() - 1; int ans = INT_MAX; while(low

[@ompandey2911]

Was wondering, What if I search for target = INT_MIN and keep the code same as the previous video wont the arr[low] be my answer?

[@andycharlie3255]

woow bro, this is crazy, legendary explanation, hats off man

[@paragroy5359]

Thanks a lot for making such videos. Your content is amazing. Keep on doing the great work

[@Manasidas99]

Understood sir thank you very much, sir. Your teaching style is really amazing. I hope I will crack my interview.

[@Rohitkumar-bx8ne]

solved without any help with BS, but before solving i have watched the previous two videos of the playlist which helped in developing the thinking skill for solving this problem

[@samlinus836]

I guess this algorithm fails for the below input: arr = [3,1,2] Your explanation is so clear bro❤ This condition should be added: min = Math.min(min,nums[mid]);

[@theanimerecaphub]

ya you have to save mid as a probable answer and compare it while moving on left

[@NitinKumar-wm2dg]

change it to nums[low] , you might get your answer, striver's code passes all the testcases

[@sunnykumarpal5087]

Bhaiya your explanation is relay fabulous. It makes hard concepts easily understandable to us. Thank you bhaiya for helping us in dsa.

[@Anshydv3]

understood ! the best explanation bhaiya , you are hero and a real gem❤

[@jagdishkhetre4515]

Understood...Awesome Binary search Playlist.. 👏

[@milishagupta9465]

great explaination!

[@nirajaya5]

Great explanation! Thank you so much.

[@UserUser-tn8tv]

Understood. Very Good Explanation

[@per.seus._]

UNDERSTOOD❤

[@RolexGTA]

i am learn from you , one day i will cross you 🙇

[@Manishgupta200]

Other way to solve this problem is by pivot search.. Here is the approach, if(nums[nums.size()-1] > nums[0]) return nums[0]; // find pivot int s = 0, e = nums.size()-1, mid = s + (e - s) / 2; while(s < e){ if(nums[mid] >= nums[0]){ s = mid + 1; } else{ e = mid; } mid = s + (e - s) / 2; } return nums[mid];

[@hariomtiwari9283]

Super Explanation 🎉🎉

[@harim7945]

STRIVER YOU THE BEST!!!!!

[@luvdhamija5157]

We know that if it is sorted in nature then arr[low] would always be the minimum number of all. by considering this we can simplify this as following. low=0 high=len(nums)-1 while lownums[high]: low=mid+1 elif nums[low]>nums[mid]: high=mid else: break return nums[low]

[@akkipinky9194]

Thanks for the incredible knowledge u give us...understood!!

[@dayashankarlakhotia4943]

Good explanation. Explanation in depth

[@baibhavghimire3827]

You beat neetcode on this🎉. Superb dude.

[@kurma.4932]

Heres a alternate and easier code Got the intuition myself thankyou Striver :3 class Solution { public: int findMin(vector& nums) { int n = nums.size(); int low = 0; int high = n - 1; while ( low

[@Aks-47]

slightly lengthier, but core logic is , we need to handle 2 cases where we are uncertain where to move, that was the crux for me, a) mid is less than lo and hi, b) mid greater than lo and hi, if we exclude that , then searching is regular BS, attaching java code for the same int ans = Integer.MAX_VALUE; while(lo

[@rahulsidhu5945]

Understood.. Awesome Binary search Playlist..😍

[@aps2129]

Amazing explanation!!!!!

[@tanishkthakur9965]

got it , understood everything

[@atharva_g_vlogs]

UNDERSTOOD

[@shreyanshdasgupta5807]

00:04 Find the minimum in a rotated sorted array using binary search. 02:08 Identify the sorted half in a rotated sorted array 04:19 The left portion of the rotated sorted array contains the minimum. 06:37 Identifying and eliminating the minimum element in a rotated sorted array. 08:40 Finding the smallest element in rotated sorted arrays using binary search. 11:06 Binary search on a rotated sorted array 13:13 Optimization in identifying sorted search space 15:16 Binary search stops in a sorted search space, improving time complexity

[@anuragparasharsarmah1045]

How I thought about this solution is, the minimum is always in the left part of the array in a normal sorted array. However in a rotated sorted array the minimum is always in the unsorted half. So we move to the unsorted right half if it exists. Otherwise we always move to the left. while(low

[@AdityaKumar-h4u]

but i the same code can be done by using built in function for min in whole vector (return *std::min_element(nums.begin(), nums.end());) so you can simply solve the code but finding min which is built in inittself a searching so take it as fun

[@AnmolGupta-oj4lm]

Understood Very Well!

[@RishabhKumar0094]

understood, for duplicate elements worst case time complexity will be O(n/2).

[@harishms5330]

how

[@RishabhKumar0094]

@@harishms5330 So consider an example arr=11111111111111 size=14 it will take about O(7), if arr[low]==arr[mid]==arr[high] low++; high--; till low crosses high, it will follow the condition , at one time, low increases to 1 and high decreases to 1, so arr size reduced by 2 similarly it will go till O(n/2).

[@harishms5330]

@@RishabhKumar0094 thank u🫡

[@piyushroy3278]

understood sir. Huge kudos to you :)

[@keerthireddy8074]

I think this below code is simpler and easier to understand: int findPivot(vector &nums){ int low = 0; int high = nums.size()-1; int pivot =0; // if not rotated, it should return 0 while (low

[@dipingrover1970]

amazing explanation . thanks a lot

[@yossihadad8558]

amazing!

[@kingbadshah452]

thanks striver understood everything

[@kiranmoura2974]

Bahut ache se smgh aaya sir ❤

[@make4u982]

understood good job bro

[@neerajkumar-ts6om]

You don't know how relived I am to know that you won't change format, I was afraid that it is some advance technique. I always hated binary search, hope I wouldn't after this your Binary Search Playlist

[@aliakbaransaria3-925]

Very good explanation Thank you

[@mdrianurrahamancse2568]

You are the best

[@RagaviSathiyamoorthy]

Sir completed the problem which you gave as homework 😇😇

[@rushidesai2836]

Great question!

[@ddevarapaga5134]

Understood perfect bro

[@sriramchaitanya6263]

So what I did is instead of storing the mid value I moved the right pointer to mid instead of mid-1 is it efficient

[@YourCodeVerse]

Understood✅🔥🔥

[@Shunya_Advait]

Understood Sir. Thank You Sir 👌👌

[@thefourhourtalk]

a random tip : if you dont understand this (because at first I didn't get it ) take your pen and paper and dry run the example of 45123

[@md_seraj786_]

understood all clear ❤

[@subhamraul]

I actually thought the same idea by myself 😁

[@samuelfrank1369]

Understood, Thanks a lot

[@presidenttalks8]

Understood👍 thank you sir

[@adarshkumarrao3478]

UNDERSTOOD

[@infernogamer52]

Understood Bhaiya!

[@NazeerBashaShaik]

Understood, thank you.

[@aishezsingh7004]

I think This is more intutive moving towards unsorted and if sorted move left while(low arr[mid] ) high = mid - 1; else if( arr[mid] > arr[high] ) low = mid + 1; else { ans = min(ans , arr[low] ); break; } } return ans;

[@mahadishakkhor123]

Hey god bless you bro❤

[@myproject6768]

Absolutely understand ❤

[@JothiprakashThangaraj]

understood, thanks a lot!

[@riteshsrivastava3447]

Solution based on applying binary search on sorted side and storing start index element as possible solution : tops 100% in leetcode int findMin(vector& nums) { int ans=INT_MAX; int start=0; int end=nums.size()-1; // logic is to find sorted side and store start index value into min each time while(start