LeetCode Find First and Last Position of Element in Sorted Array Solution Explained - Java

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@eshagupta9407]

Got it in an interview today! Thanks a ton!

[@abarag8]

Which company? What other questions were asked?

[@KcClips]

@@abarag8 Are You doing Job ?

[@debasismandal1924]

He made it seems so easy * meanwhile me stuck on this one since last hr * Thanks!

[@Ola-xx4zh]

Man, I was struggling with this for a long while and couldn't find a good explanation anywhere, until I found you and I think, I finally got it. You are doing a really good job, thanks!

[@tannerbarcelos6880]

I knew binary search was needed when hearing “sorted” then hearing “log N” supported that idea. However, the disconnect I was having was how to slightly tweak the search to accommodate for multiple targets in a row and get the left and right most. This video helped solve that disconnect. Thanks bro 🙏🏼

[@borishuang887]

Simple and straightforward. No BS. Just hit it right on point. just a clean code and well-structural linear flow. thank you.

[@akshaydwivedi935]

All your videos are exceptionally good better then other fancy programmers.

[@RaymondLo84]

Not sure why but there are lots of Indian coding tutorials and always have a hard time understanding what they are trying to teach.

[@andrewsavin9596]

@@RaymondLo84 🙂

[@sarvottampriyadarshee5425]

Thanks man! You saved me! and that Keyboard sound is so satisfying!

[@davaa847]

Learned a lot from you, not only problem solution but also coding style. I watch your solution even I got my own solution to optimize my coding style and readability, This one was mindblowing my run time was also 0ms 100% BUT my code readability was not up to your standard. Keep doing the good work man.

[@wendywang8535]

Great Explanation!! Much better than those few lines code, and also I think this is really good for interview, you can explain your idea very clear. Thank you!

[@saravanansarangan7035]

Easily readable code Nick great work.. Thank you...

[@gourabbanerjee4152]

Excellent Description ! The best solution explanation I have found for this problem. Thank you!!

[@fengxie4762]

The logic is so clear and the explanation is very easy to understand! Thx!

[@rovingravi4603]

Great explanation, very readable and clean coding... Thanks for sharing!!

[@nawaz_haider]

I've watched 3 videos for this problem. But this one is the best. Thanks Nick.

[@bmy4415]

What a nice explanation! This really helped me. Thanks

[@kahizer]

very neat code, nice way of using methods rather than optimizing code lines and making it very hard to understand it. Very well explained

[@Leo-zh2or]

Nice solution. Easy to understand. Good job. Thanks.

[@kumarc4853]

Nick White for President of Programming. I got a variation of this in a interview recently, which is find the last index of an element in sorted array, whose index is equal to the value. The technique to find first or last was very helpful.

[@ankurranjan3218]

This is really a good solution. Kudos @Nick

[@rchukkapalli1]

Good explanation. Subscribed!

[@gaurbasu5274]

Great Explanation!

[@PramodRj]

Great Video Nick!! Thanks

[@shivalikagupta3433]

U had done same, just that i was writing the list.get(mid)==target condition first followed by other conditions(start = mid+1 or end = mid-1 as and when) Following this same as you did, I finally arrived at my answer. Thanks !!!:))

[@ManishKumar-xt6kf]

Thank u U explained it in simple way

[@user-hq6zx2ds2r]

It's good!Thanks for sharing!

[@huihuang2294]

Thank you for sharing

[@satyamgupta6030]

thanks thanks alot nick brother. Please keep on making such videos. your leetcode solution videos help students all over the world.

[@Taheershaik]

Clean... Great job, thanks mate.

[@surajpenugonda4756]

Nice work bro

[@044_karan9]

outstanding explanation

[@surajgrandhi6742]

Amazing solution

[@alibaba998]

Great video. One comment, If the firstIndex==-1 then we don't need to call the secondIndex binarySearch, right?

[@miashani]

correct, and also if it is NOT -1, I'd start findEndIndex with firstIndex+1 (add parameter to finction...)

[@Abhishek_Poddar]

@@miashani but it won't create some significance change in time complexity of the problem or it will be ? ....cuz binary search will be like the way it is !!

[@notgaurav]

really good! keep it up

[@tusharpadihar7030]

You are a genius ❤️

[@sharuk3545]

Awesome solution

[@yashwantkumar4998]

you are superb bro !

[@ZhouHaibo]

Pretty easy and clear, add 1 earlier break when first index is -1. ``` result[0] = findStartIndex(nums, target); if (result[0] == -1) { result[1] = -1; return result; } ```

[@dinamohamed13600]

very helpful thanks

[@suprathikm3639]

awesome Nick

[@AshishKumar-dn6jc]

Thanks man!

[@aravinds6406]

Well explained

[@harikrishnak721]

Thanks nick

[@tuannguyentranle7151]

So fancy ;))) thanks a lot

[@yashspr]

Simple and elegant explanation! Amazing man

[@lifeofme3172]

Awesome video

[@prathamchitransh5338]

Best Solution for this problem.

[@farzanehahmadi9410]

you rock bro!

[@free-palestine000]

nick white >>>>

[@anmolverma075]

At 8:13 , what is the difference between the condition of this function and for the start index function? I don't understand because they are basically the same. Can anyone explain?

[@vaibhavjain4710]

I have done using recrusive solution but got me error . Thanks for iterative version of the problem.

[@abhishekkumarsinghA]

awesome

[@somyasrivastava6315]

you are Amazing

[@akshaybhosale2724]

Why did we not do linear search again? Did I miss something? start a loop with start and end as -1 when you see the target first time set start = i and then till i is greater than target set end = i-1 and return.

[@shubhamuniyal2417]

Smooothhhh!!!!

[@rupaldesai7098]

If the target value occurs only once in the input array then the result[0] = indexvalue and result[1] = -1? Please correct if I am wrong..

[@NickWhite]

result[0] = indexvalue and result[1] = indexvalue. They would equal the same index value because there is only one occurrence of target in the array. That's why the conditions are = because they will find the target but then keep going to make sure it's not the only occurrence. At the end of each loop if they have seen the target we will set the index variable to the index we saw the target at

[@rupaldesai7098]

@@NickWhite Got it! Thanks

[@somyasinha6293]

U did not check for the corner cases i.e when the mid = target so in that case we need to check that mid==0 || nums[mid-1]!=nums[mid] then return mid;

[@StayPuft787]

7:52 So ye, for the last index I just used the same code but removed the equals sign. if (nums[midpoint] > target) { end = midpoint - 1;} and it also worked

[@yahwehagape]

Is it bad practice to rely on int casting to take the floor?

[@hritwiksom3032]

This is implicit casting so I don't see why it would be.

[@visheshsahu-yn8wz]

big fan bro

[@benjaminmalley5719]

Did you consider binary search for this problem?

[@siobhanahbois]

🤔

[@akshatshah3013]

Why cant we use the indexOf() and lastIndex() methods and store them in result?

[@hritwiksom3032]

We can but in an interview, the interviewer won't be happy with it or ask for the logic anyway

[@rubyjiang8836]

so smart

[@ahmetozdemir2207]

If I remember this correctly, there was a better solution which does not solve this problem with 2 binary search. One is enough actually. While you are searching for a target value, you just have to remember last "smaller" and "bigger" number of target and maybe their indices. Then you simply add 1 to smaller value's index and subtract 1 to other index.

[@nhht77]

Somehow, I tried the same method in Javascript but it didn't work. It works well on Java.

[@aman4434]

Because mid in javascript will give decimal values on dividing by 2! Just tried myself and found out :)

[@svalyavasvalyava9867]

Can, please, someone explain why start + (end - start) / 2 is preferrable to (start + end) / 2 Thanks in advance.

[@neloangelo172]

Use the first way to avoid integer overflow

[@svalyavasvalyava9867]

@@neloangelo172 thanks a lot, got it

[@fulinaround]

Instead of combing through the discussion boards I check your channel first, leetcode solution , and discussion board last.

[@ethanhuang2127]

Since the time complexity only considers the worst case, if all integers in the list are the same, the time complexity would be O(n)... I have a not-so-smart proposal --"how about searching for targart-(smallest number) and target+(smallest number) and return the closest index?

[@maddinmanek8679]

The time complexity would still be a fast binary search - and meet the log n. That only one of each occurs would make no difference in that.

[@maddinmanek8679]

Of course you could check is first and last element are the same before running the algorithm.

[@jashbhatia3948]

Question: Why not just find the left most index and then traverse through the array till we keep finding duplicates?

[@fhantom784]

That'd be O(n) in the worst case (e.g. an array of all 8s). What you could do though is use the left index as "start" when searching for the right index.

[@adjmonkey]

Why not just find any index of it with a normal binary search and then just move two pointers left and right until it changes? Then just an initialize an array with those pointers+-1? That would be faster unless the array has 10,000 of 1 value (or something obtuse like that) and a lot less code.

[@RhymesWithCarbon]

adjmonkey this is along the same lines as what i was thinking, have two pointers, one far left and one far right, and start moving towards the middle. If one pointer finds a match, keep it moving until it finds another match. Then: if the unmatching Pointer and matching pointer overlap, stop, you know there’s only one match at all. Or if the unmatching pointer gets a hit, stop.

[@bestsaurabh]

That would be linear time complexity. Imagine having an array of same number repeating n times.

[@thesuburbanerrorist9727]

Dude you are like my hero and shit.

[@a4ankit27]

Why does this code return -1, -1 for me ? Any guesses , what i might me missing ?

[@a4ankit27]

var searchRange = function(nums, target) { let array = []; array[0] = firstIndex(nums, target); array[1] = lastIndex(nums, target); return array; } var firstIndex = function(nums, target) { let index = -1; let start = 0; let end = nums.length -1; while (start = target) { end = middle -1 } else { start = middle +1; } if(nums[middle] == target) { index = middle; } } return index; } var lastIndex = function(nums, target) { let index = -1 let start = 0; let end = nums.length -1; while (start

[@paveldubinin515]

@@a4ankit27 your "middle" is float (use Math.floor() to convert to integer). He uses java and his variables are typed int so this happens automatically there.

[@NickKravitz]

Nice explanation, but you have broken the "don't repeat yourself" rule. Methods are similar enough to combine into a single method with a boolean startingOrEnding input variable.

[@RawBert]

there’s a better way, get index of first, then with that index look at how long it goes

[@chillu420]

the video is at 1.4K likes right now, Can we make it to be more liked than the actual leetcode question likes in this particular video i.e 1.9k

[@kingthunder9787]

Hi

[@amansayer4943]

class Solution { public int[] searchRange(int[] nums, int target) { int[] ans = {-1, -1}; // First Occurrence int start = 0, end = nums.length - 1; int mid = (start + end) / 2; while (start nums[mid]) { start = mid + 1; } } // Last Occurrence start = 0; end = nums.length - 1; while (start nums[mid]) { start = mid + 1; } } return ans; } } clean code

[@existenence3305]

Binary Search. Binary Search. Binary Search.

[@dushyantjakhar1716]

Everything is good but sound is not balance

[@RaymondLo84]

I still really hate people writing code like those compressed javascripts with 1 line does all... I really don't think that's how the real world works...

[@TheBestNameEverMade]

You don't need 2 binary searches.

[@hritwiksom3032]

You mean you don't need 2 functions, two searches are obviously needed.

[@TheBestNameEverMade]

@@hritwiksom3032 no he throws away information the way he does the search. You could split it into two and use the bounds found in the first as a starting point for the second. However you might as well just search for both at once and adjust both upper and lower ranges. At the very minimum he could have used the returned lower bound as the min range for the second algorithm, saving having to search the start of the array. Still that throws away information learned about the upper bound.