LeetCode Find First and Last Position of Element in Sorted Array Solution Explained - Java
Vložit
- čas přidán 11. 09. 2019
- 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 - Věda a technologie
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.
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.
Thanks man! You saved me!
and that Keyboard sound is so satisfying!
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.
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!
I've watched 3 videos for this problem. But this one is the best. Thanks Nick.
Excellent Description ! The best solution explanation I have found for this problem. Thank you!!
The logic is so clear and the explanation is very easy to understand! Thx!
What a nice explanation! This really helped me. Thanks
Great explanation, very readable and clean coding... Thanks for sharing!!
very neat code, nice way of using methods rather than optimizing code lines and making it very hard to understand it. Very well explained
Good explanation. Subscribed!
Nice solution. Easy to understand. Good job. Thanks.
Great Explanation!
Great Video Nick!! Thanks
This is really a good solution. Kudos @Nick
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;
}
```
Nice work bro
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 !!!:))
Thank you for sharing
You are a genius ❤️
outstanding explanation
Amazing solution
It's good!Thanks for sharing!
Clean... Great job, thanks mate.
Thank u
U explained it in simple way
you are superb bro !
really good! keep it up
Awesome solution
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 !!
Simple and elegant explanation! Amazing man
thanks thanks alot nick brother.
Please keep on making such videos.
your leetcode solution videos help students all over the world.
So fancy ;))) thanks a lot
Well explained
awesome Nick
Best Solution for this problem.
very helpful thanks
nick white >>>>
Thanks nick
Awesome video
you rock bro!
Thanks man!
Instead of combing through the discussion boards I check your channel first, leetcode solution , and discussion board last.
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.
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
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
I have done using recrusive solution but got me error . Thanks for iterative version of the problem.
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
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.
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;
Smooothhhh!!!!
you are Amazing
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?
big fan bro
awesome
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.
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 :)
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
Did you consider binary search for this problem?
🤔
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.
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.
Dude you are like my hero and shit.
so smart
there’s a better way, get index of first, then with that index look at how long it goes
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.
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
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
Binary Search. Binary Search. Binary Search.
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...
Everything is good but sound is not balance
Hi
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.