LeetCode Find First and Last Position of Element in Sorted Array Solution Explained - Java
Вставка
- Опубліковано 6 вер 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
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/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
Got it in an interview today! Thanks a ton!
Which company? What other questions were asked?
@@abarag8 Are You doing Job ?
He made it seems so easy * meanwhile me stuck on this one since last hr * Thanks!
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!
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 🙏🏼
All your videos are exceptionally good better then other fancy programmers.
Not sure why but there are lots of Indian coding tutorials and always have a hard time understanding what they are trying to teach.
@@RaymondLo84 🙂
Simple and straightforward. No BS. Just hit it right on point. just a clean code and well-structural linear flow. thank you.
Thanks man! You saved me!
and that Keyboard sound is so satisfying!
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.
Great video. One comment, If the firstIndex==-1 then we don't need to call the secondIndex binarySearch, right?
correct, and also if it is NOT -1, I'd start findEndIndex with firstIndex+1 (add parameter to finction...)
@@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 !!
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.
thanks thanks alot nick brother.
Please keep on making such videos.
your leetcode solution videos help students all over the world.
Easily readable code Nick great work.. Thank you...
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!
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;
}
```
very neat code, nice way of using methods rather than optimizing code lines and making it very hard to understand it. Very well explained
I've watched 3 videos for this problem. But this one is the best. Thanks Nick.
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 !!!:))
What a nice explanation! This really helped me. Thanks
The logic is so clear and the explanation is very easy to understand! Thx!
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..
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
@@NickWhite Got it! Thanks
Best Solution for this problem.
Nice solution. Easy to understand. Good job. Thanks.
You are a genius ❤️
Excellent Description ! The best solution explanation I have found for this problem. Thank you!!
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;
Great explanation, very readable and clean coding... Thanks for sharing!!
Why cant we use the indexOf() and lastIndex() methods and store them in result?
We can but in an interview, the interviewer won't be happy with it or ask for the logic anyway
This is really a good solution. Kudos @Nick
Well explained
Thank u
U explained it in simple way
very helpful thanks
Nice work bro
Clean... Great job, thanks mate.
nick white >>>>
Awesome solution
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.
outstanding explanation
Great Video Nick!! Thanks
Great Explanation!
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?
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.
Thanks man!
Thank you for sharing
Good explanation. Subscribed!
It's good!Thanks for sharing!
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
you are superb bro !
awesome Nick
Simple and elegant explanation! Amazing man
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
So fancy ;))) thanks a lot
Awesome video
really good! keep it up
Thanks nick
Is it bad practice to rely on int casting to take the floor?
This is implicit casting so I don't see why it would be.
you are Amazing
I have done using recrusive solution but got me error . Thanks for iterative version of the problem.
you rock bro!
Did you consider binary search for this problem?
🤔
Somehow, I tried the same method in Javascript but it didn't work. It works well on Java.
Because mid in javascript will give decimal values on dividing by 2! Just tried myself and found out :)
awesome
big fan bro
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.
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.
That would be linear time complexity. Imagine having an array of same number repeating n times.
Question: Why not just find the left most index and then traverse through the array till we keep finding duplicates?
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.
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?
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.
Of course you could check is first and last element are the same before running the algorithm.
Dude you are like my hero and shit.
so smart
Smooothhhh!!!!
Instead of combing through the discussion boards I check your channel first, leetcode solution , and discussion board last.
Can, please, someone explain why
start + (end - start) / 2
is preferrable to
(start + end) / 2
Thanks in advance.
Use the first way to avoid integer overflow
@@neloangelo172 thanks a lot, got it
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.
Why does this code return -1, -1 for me ? Any guesses , what i might me missing ?
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
@@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.
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
there’s a better way, get index of first, then with that index look at how long it goes
Binary Search. Binary Search. Binary Search.
Everything is good but sound is not balance
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...
You don't need 2 binary searches.
You mean you don't need 2 functions, two searches are obviously needed.
@@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.
Hi
Amazing solution