BS-7. Find out how many times array has been rotated

Problem Link: bit.ly/3pMzTCh
Notes/C++/Java/Python codes: takeuforward.o...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of Course

[@takeUforward]

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

[@sushamakumari4886]

Sir , please i request you make video in Hindi as well as ..sir there are so many students like me who waiting for you lecture in Hindi 🙏🙏

[@bhargavonfire5978]

​@@sushamakumari4886

[@bhargavonfire5978]

Understood

[@pranavmisra5870]

Learning platforms appear, reach their peak and disappear, but takeuforward is going to be evergreen. The quality, the hardwork and the amazing way he teaches is unmatched.

[@saswatrath4646]

Yes

[@dilipkumarbk7657]

Don't know how to thank you for your contribution to the community. I just did this problem by my self that I was able to use the previous question finding the minimum in a rotated sorted array. When I saw the question. I just remembered the line, "DON'T DIRECTLY JUMP TO THE SOLUTION, FIRST GIVE IT A TRY!" Thanks a lot striver bhaiya. I am feeling confident now, that I can understand the pattern in the problem.

[@Beastboy-h6c]

Hi bro, What are you doing right now?

[@gurpritsingh2339]

a tricky thing to spot here is whether the rotation is clockwise or anti-clockwise, in this problem we considered anti-clockwise rotation. the final rotated position can take a different no of steps depending upon the type of rotation.

[@nownow1025]

The current code works well for right rotations because the pivot index (`index`) represents the number of steps the array has been rotated to the right. For left rotations, you can calculate the equivalent number of rotations as: Left Rotations=(Size of Array)−Pivot Index (Smallest Element Index)

[@inderjeet09]

Bro we need a playlist on Bit manipulation also . Please consider this request.

[@gajsinghrathore8800]

TRY LOVE BABBAR

[@iamnoob7593]

Bit Manipulation is hardly asked in face to face interviews , But can be asked in OA.

[@vaishnavejp9247]

used a different approach. it goes to the side that is unsorted(as that will have the pivot element). it keeps doing that until nums[low] < nums[mid]. the moment we find that, we find our pivot value. int findKRotation(vector &nums) { // Code Here if((nums[0] < nums[nums.size()-1]) || (nums.size() == 1)) return 0; int low = 0, high = nums.size()-1; while(low nums[mid]) high = mid - 1; else low = mid + 1; if(nums[low] < nums[mid]) return low; } return 0; }

[@Manasidas99]

Help me a lot thank you sir It is the biggest KZbin channel I follow every time on the channel. I learn lot .

[@aadityamehta6342]

solved this one on my own. Thanks Striver!!

[@just_a_guy6985]

class Solution { public: int findKRotation(vector &arr) { int start = 0 ; int end = arr.size()-1; while(start< end) { int mid = start+(end-start)/2; if(arr[end]

[@SuvradipDasPhotographyOfficial]

Understood, awesome striver keep going, eagerly waiting for remaining videos

[@cinime]

Understood! Wonderful explanation as always, thank you very much for your effort!!

[@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.

[@kaushiksen2190]

could you please elaborate and show the steps

[@kaushiksen2190]

it is little confusing, please explain if possible

[@dank7044]

well in case of duplicates, we just need to update the index, eveyrtime we encounter an elemwnt==min, whose index

[@visase2036]

@@kaushiksen2190 in the example I mentioned , rotate the original array I highlighted 3 times. , You would get the rotated array as [1,1,2,1,1]. Now if you apply the same code , the minimum element would come as 1(0th index) which is correct but if you ask how many times the array is rotated ( the 1 which is originally at the 0th index have moved to 3rd Index) so 3 should the correct answer. To get 3 as your answer , you have to add one more condition which I mentioned !

[@aisharawat9102]

​@@dank7044can you share the code for the duplicate ones

[@RitikLowanshi-d1s]

I understood this concept after watching this video.

[@mehulthuletiya497]

00:20 Problem statement 02:16 Code 03:54 Try out for duplicates to solve this problem

[@Anshydv3]

bhaiya aap,, sbko knight and gaurdian badge dil ke rahoge , Leetcode pe ❤❤

[@elizabethr5161]

Best series ever..

[@dakudevilyt751]

thank you so much great video

[@manavsingh5919]

Thank you Striver...Understood everything

[@harshithareddygujjula2261]

Understood very well!

[@Gaurav_Tripathi_]

understood, wonderful explaination Bhaiya..!!

[@kingbadshah452]

understood everything thanks sstriver

[@myproject6768]

Absolutely understand ❤

[@augustinradjou3909]

Understood boss🎉

[@KCOYASH]

understood :) , please continue such great videos

[@infernogamer52]

Understood Bhaiya!

[@yashsomani3042]

Understood, Thank You!

[@dgvlogs4183]

Understood😍😍😍😍😍😍

[@PiyushKumar-xe1ng]

int findKRotation(vector &arr) { int n=arr.size(); int low=0, high=n-1, ans=0; while(low

[@riyabankawat4998]

awesome explanation.. bhaiya thank u

[@NazeerBashaShaik]

Understood, thank you.

[@samuelfrank1369]

Understood. Thanks a lot.

[@aakashsharma780]

Understood ❤🙌🥳

[@therandomguy21]

sir i have a confusion how do we know from where we have to count how many times the array has been rotated for ex - arr[] = [1,2,3,4,5] is if rotated from left hand gives the answer 2 and from right end it will give the answer 3 ?? for the rotated array = [3,4,5,1,2]

[@time-barbaad]

right rotated

[@HARSHAMANNE-bt1oo]

It will be 54312 if it is right rotated by 3 places​@@time-barbaad

[@HARSHAMANNE-bt1oo]

It will be (n-index of min element)%n

[@YourCodeVerse]

Understood✅🔥🔥

[@srija0608]

Understood 👍

[@rahulsidhu5945]

Please continue this playlist

[@kiranmoura2974]

Understood ❤

[@utsavseth6573]

Understood.

[@suraj_3240]

Understood 👍 👍

[@bhavya8608]

understood!!

[@DEVANSHVYAS-z1b]

Code for duplicates :- int findKRotation(int arr[], int n) { // code here int low = 0, high = n - 1; int minValue = INT_MAX; int k = -1; while(low low && arr[high-1] == arr[high]) high--; if(arr[high] < minValue) { k = high; minValue = arr[high]; } high = high - 1; continue; } if(arr[low] < arr[high]) { if(arr[low] < minValue) { k = low; minValue = arr[low]; } break; } if(arr[low]

[@mainakdasgupta7130]

thank you man

[@SYCOA12CHAITANYAASOLE]

Understood !! 😎😎

[@HarshSingh-fq3dv]

Understood ❤

[@anonymous-sz8jq]

Understoood!!

[@adarshkumarrao3478]

UNDERSTOOD

[@ErenYeager-dp4er]

Done on 14 Jan 2025 at 10:13 Place : Study Room 2 , Hostel 5 , IIT Bombay

[@ZephyrrCummins]

can anyone explain why min() function is used directly??

[@jitinroy2246]

to write line code in 1 code, by this you also save time in writing.

[@ddevarapaga5134]

Understood Brother

[@UnknownforKnown-t1i]

static int timesRotated(int[] a,int n) { int low=0; int high=n-1; int ans=Integer.MAX_VALUE; int index=-1; while (low

[@aritrasaha3938]

it won't work for [2, 3, 1, 1] right?

[@UnknownforKnown-t1i]

It will work once dry run the code.​

[@DeepakPatel-d5v]

Thanks a lot Bhaiya

[@anonymousofficial7824]

Understood!

[@hallupandet228]

Understood🕺

[@aryanpatelyt7562]

Understood !!

[@anshulrai6058]

understood👍

[@AnishRaj-gk2ll]

Just randomly found another solution to this with O(log(n)) int findKRotation(vector &arr) { int n = arr.size(); int left = 0; int right = n-1; int mid; while(leftarr[mid]) right = mid-1; else left = mid+1; } return left%n; }

[@SriM-g6p]

understood!!!

[@shubhamkumar170]

Understood!

[@subhamghosh229]

Understood :)

[@sibiranganath]

UNDERSTOOD

[@Learnprogramming-q7f]

Thank you bhaiya

[@aumrudhlalkumar5487]

Thanks

[@moonchild-il2xs]

understood!

[@Pw_Unfiltered]

was waiting for that iitb student comment here 😂ok let he come, we shall meet in some next vdo

[@pihus3498]

understood :)

[@dayashankarlakhotia4943]

Understood

[@MAHESHAITBECS]

excelleent

[@TrinmoyDutta]

will not the index of the minimum element be the number of rotations??? initially the minimum should be at 0, but the minimum is at index i due to i number of rotations.

[@rupalikumari8829]

Understood:)

[@Shivi32590]

thanq

[@Manishgupta200]

Same as minimum_in_sorted_array problem.

[@oyeshxrme]

understood bhaiya

[@Anony.musk01]

understood :)

[@rahulab1165]

They said STRIVER i listen SAVIOUR

[@codeman3828]

Awesome

[@sudhanshushekhar4222]

Understood

[@astronautgamer34]

it is better to find min by finding the pivot and adding 1 to it

[@divyadwivedi1527]

understood

[@Abhishekkumarnjw22-vf7cr]

❤❤

[@singhji4149]

If the array contains duplicates and then we have to find out the number of times the array is rotated ?????????????????????????????

[@nownow1025]

If arr[low] == arr[mid] == arr[high], it is unclear whether the pivot lies in the left or right half of the array. In such cases, we cannot rely on the usual binary search rules, so we must increment low or decrement high to bypass duplicates.

[@nownow1025]

int findKRotationLeft(vector &arr) { int low = 0, high = arr.size() - 1; int ans = 1e9 + 7; int index = -1; while (low

[@kiranmoura2974]

I tried solving for duplicate elements also but was unable to do so ...can anyone help me out in this .

[@nikhilthulaseedharan1525]

Below is the solution for duplicates: public static int findKRotation(int nums[], int n) { int low=0; int high=n-1; int ans=Integer.MAX_VALUE; int index=-1; while(lownums[low]){ ans=nums[low]; index=low; } low++; high--; continue; } if(nums[low]nums[low]){ ans=nums[low]; index=low; } low=mid+1; }else{ if(ans>nums[mid]){ ans=nums[mid]; index=mid; } high=mid-1; } } return index; //TC:O(n/2) //SC:O(1) }

[@divyakumardivyanshu4279]

understand

[@md_seraj786_]

understood all

[@godson200]

Whenever someone pronounces the word understood, I feel someone is calling my name (homophones)

[@himanshukaushik9223]

Find minimum ki 2 approach use nahi hori ish question ma meri can anyone explain??

[@tamanna354]

💗

[@AnandKumar-lz2nf]

❤

[@raghavkansal3765]

"understood"

[@girikgarg8]

Done

[@jagadeeshp1163]

US💯

[@CodeMode9313]

Habibi mst hai bideo

[@shalinijha2615]

class Solution { public int findKRotation(List arr) { int n=arr.size(); int lo=0; int hi=n-1; int min=Integer.MAX_VALUE; int minIndex=Integer.MAX_VALUE; while(lo

[@anshsaxena7297]

UnderStood

[@apoorva5961]

😇

[@codingp110]

US!

[@deeksha6514]

int findKRotation(vector &arr){ // Write your code here. int low = 0; int high = arr.size()-1; if(arr[low]

[@tanujaSangwan]

Solved it without watching the video

[@Itsme1n1ly]

US

[@harshitjaiswal9439]

Undetstood!

[@AmiteshRanjan24]

"us"