LeetCode Day 19 - Search in Rotated Sorted Array

[@mariansoltan1318]

When I saw this problem, first thing that i remembered was you binary search lecture where you talked about that.

[@AnkurDeka]

Totally loved your solution. I think the key idea was to understand that within the rotated array, by comparing any element with the first element we can determine which section the element belongs to. We could instead compare with the last element as well.

[@jamjam3448]

Thanks so much. I finally understand it after several hours of studying

[@domdom_hello]

Dude, you're the best! You help me a lot! I just love your style to explain things - so easy for me to understand, so clear. Thanks man!

[@vineethkumar6710]

@Errichto I watched your 'Binary Search Tutorial' and I could easily come up with optimal solution for this question. Thanks for your amazing videos

[@mohamadalibaydoun6418]

This was one of my Google interview questions 5 years ago. Aced it, got in

[@miteshkumar3183]

I still cant get it consistently. The first time I came up with it myself but I always mess up when I re attempt the problem, and have to submit several times. Right now I am passing 150 /200 test cases on leetcode, gg.

[@fauzanwaseem6436]

@@miteshkumar3183 i went for a linear search just to feel better lol

[@PiyushKumar-qj8ue]

I used the first approach to solve it but I'm very pleased to learn another approach. Thanks ❤️

[@SurajKumar-bw9oi]

I ran both codes Amazingly, both approach gives the same running time of 4 ms in Leetcode.

[@Rekefa]

Can you do a data structures/ algorithm crash course? Would be a pleasure to learn from you

[@genuineprofile6400]

He may not be good with just theory.

[@rentib9136]

@@genuineprofile6400 He is ultra good

[@CarrotCakeMake]

Wow, what a thing to see. I was just implementing a BTree data structure using circular buffers for children and data. An IRL version of this problem. Except I guess I know where the start of the circle is.

[@shreyasshastry5795]

Code Jam 1B video???

[@hellowill]

Very cool! I think of it like the rotation partitions the array into two sorted parts. E.g. [3,4,5,0,1,2] = [3,4,5] ++ [0,1,2]. So if you're in the same part as target you're allowed to do standard binary search and if you're not in the same part then simply search that part with target in it.

[@RMGringo2122]

William you still need to find the point where one array splits from another though right? Which would be slower. Unless I misunderstood your solution

[@hellowill]

@@RMGringo2122 You do that with the first element comparison (its the same code as in the video)

[@mohamed4441]

good work! please keep doing these videos.

[@usuyus]

I want to ask a question: because the question said that there wouldn't be any duplicates in the list, we didn't really consider examples like this: [1,1,2,4,0,1,1,1,1,1,1] 4 In this case, we say m = 5 in the first iteration and encounter a 1 in nums[5]. Because we assume no duplicates, we think m is in the first sector while it actually is in the second one. This would cause the algorithm to not work. I have been thinking about the general case where duplicates are allowed and where we have to be able to also answer test cases like this, but couldn't actually find a feasible solution / modification to the existing solution. Any help is welcome as a comment :) (I have been looking for a solution for too long now... I really need help)

[@kabaran2]

Unfortunately there is no solution to do this with O(log(n)). At least not in the worst case. Consider the array [1,1,2,1,1,1]: there is no way to find the "2" with a binary search because none of the other elements give you any clue as to were the "2" is (or if there even is one). So you will end up looking at every item on the list which means O(n). However, if the first item and the last item are not the same, then a binary search can reveal the location of the "shift". So let's say we have something like [3,3,4,4,4,5,1,1,2,2]. In this elements all the elements up to a certain index are >=3, and all the elements beyond that index are

[@usuyus]

@@kabaran2 Thanks for the reply. I did think of the O(m + logn) solution; I was just wondering whether an O(logn) algorithm would exist or not.

[@AshishSingh-dn8wb]

Amazing explanation! Can you upload a video on Code Jam Round 1B maybe?

[@iamtrash288]

very nice explanation, loved it!

[@dr.darkfurygaming9174]

It also accepted O(n)

[@Sebastian-eb2ux]

Maybe, but the problem explicitly states that your solution has to have a complexity of O(log n)

[@dr.darkfurygaming9174]

@@Sebastian-eb2ux Ya i know i just try and it accepted

[@aminel2a]

I can't understand why people react by dislike 😂BigUp anyway

[@venkyvirat92]

bro.....according to ur template u haven'nt used separate if to check if arr[mid]==target but why u are using here???

[@jpfr012]

since I'm lazy, I just used the vector::iterator java users can also use the array.indexOf(target)

[@BarkaDog]

That will be O(n)

[@jpfr012]

@@BarkaDog thanks, I didn't know that. but why didn't give TLE?

[@neer3]

Hey Errichto please tell the fine diff between (low+high)/2 and (low +(high-low)/2).

[@yashsanjeev8480]

low+high may overflow resulting in garbage values of mid

[@mohitranka9840]

In statically typed languages such as C++, which have fixed range for int, (low+high) may result in overflow, if the numbers are big. The other variant of high-low prevents it, atleast when the numbers are non negative.

[@vibhor3049]

> suppose you have a very large (like v v large around consuming 30 bits) values of high and low. Then (low+high) would give a value which simply can't be stored in int data type, hence an overflow error. > (high+low)/2 doesn't work with pointers- type error

[@ivanp4740]

i found this video with solving leetcode problems very useful. I hope errichto will do that even after leetcode challenge I did this problem twice. And twice i wasn't able to this without any mistakes(always fail on edge cases) But that explanation and code organization helps me to really understand how it could be simplified. Because my thoughts(and solution) was overcomplicated with a lot of "if else"

[@codeencode5728]

For the cases like this Eg: [5,4,3,1,2] . can the time complexity can log n instead of 3*logn ? Thanx Errichto

[@NotFound-hy7qb]

Video is right on time

[@almuhimen8023]

Why not linear search?

[@akhilanand3708]

code jam round 1 B solution please

[@arpansingh4284]

Please do a video on code jam 1B

[@sakshamsethi4123]

Codejam video please !

[@thehalfblo0dprince]

why this problem passes in O(n) complexity?

[@flintpiratehunter8723]

I think it is because it is just for interview preparation. You do not win any price; O(log n) is just for making the problem more interesting.

[@ashishdukare1313]

[India] Superb solution. thanks for the video : )

[@rajdave9862]

What is difference between low+high/2. And low +(high-low)/2 ? Please tell

[@flintpiratehunter8723]

Low + high may overflow

[@charchitsharma8902]

Implementing this in python givens TLE.

[@dhananjaysonawane1996]

I saw other problems on leetcode, codeforces which gave TLE on python but AC on cpp :( Maybe time limit is not set properly for python.

[@charchitsharma8902]

@@dhananjaysonawane1996 Yes :(

[@flintpiratehunter8723]

Nah, I got AC in Python with similar code

[@dhananjaysonawane1996]

@@flintpiratehunter8723 They later change time limits. leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/discuss/586547/C++-Top-Down-DP/509109

[@charchitsharma8902]

@@dhananjaysonawane1996 Yes!

[@thepodfunnel]

He is Mini Lex Fridman

[@tetrreter6548]

Way not use function build in like find and count?

[@rentib9136]

for vector they are linear

[@sahilsharma2952]

Google codejam solutions?

[@danilsabirov715]

Errichto, can you describe that the mid = (lo + hi)/2 is different than mid = lo + (hi - lo) /2? I can't understand what is the difference that you mentioned

[@alexandrugabriel9202]

both do the same thing, but the second is better because you avoid overflow problems if lo and hi are big.

[@sameerchouragade2706]

If low and high are very big , high + low becomes even more big , which could lead to overflow of int

[@vaibhavvashist238]

sir who to get motivated and consistency in cp?

[@fiziblank2609]

Sir, which keyboard do you use?

[@leetcodesolver9092]

I also solved it using similar approach.

[@zeyneperol2984]

Thanks!

[@abilashshankarpalli9301]

Hi Errichto, Love From India I am beginner in competative programming, and I am struggling to figure out how to take stdin and stdout for the programs here in "codeforces" so I can practice. I am using Python as language. Would you please help me with by making a video on how to take stdin and stdout in python. Or atleast please reply me with the code in python.

[@philtoa334]

Thx

[@inosuke44]

first viewer?

[@ДмитрийВихляев-к9п]

Please use zoom