First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/find-fi...
0:00 - Read the problem
1:35 - Drawing Explanation
5:15 - Coding Explanation
leetcode 34
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#binary #search #python - Věda a technologie
💡 BINARY SEARCH PLAYLIST: czcams.com/video/U8XENwh8Oy8/video.html
I watched some 4-5 videos for this problem , but this is hands down the most easiest and intuitive way of solving.
Thanks a ton
Initially what I did is finding the element through binary search and then iterating left and right to find leftmost and rightmost. But now I realized in worst case that would be O(N).
Thanks a ton for this video!
same
Great Explanation, I found the video using the link given in the leetcode post. This solution is so intuitive and is much better than the solution provided with the Leetcode problem. Keep up the good work.
Wow!! Man, I love this. I was just coming across some complicated solutions but this 🔥, thank you so much!
Thank you. This is better than all leetcode discuss solutions. I don't even think I will forget this one
Great thanks! Tried tuning a little bit further and start searching after we found initial match but lots of edge cases in that case tbh
Using leftBias boolean variable was very clever.
Lol
Thanks! Very clean approach. I like your explanation too, very concise.
You explain very well. Thanks for working hard on these explanations
The binary search updates were very intutive thank you
Great Explanation! Thanks for your smart and hard work.
As always, such a great explanation! I have a small suggestion for a slight efficiency boost: if the target is not in the array, we could run the binary search once and set right to -1 if left is -1, without running the binary search a second time.
This is the best explanation i watched, thank u.
Nice , it’s easy to understand.👍
Thank you! Great explanation
Best solution that I have ever seen
Always love ur explanation bro!!!
Best Explaination EVER 🔥
I was used similar approach but I used binary search exit condition as (nums[mid] == target && nums[mid -1] != target) similarly for right bias it will nums[mid+1] != target. This one is much cleaner
it makes total sense to use binary search to find the left and rightmost instances if the target, I don’t know why I suddenly let my code return to O(n). Thanks for the vid!
We can optimise it further by finding first index , if not found we need not find second Index
awesome explanation
after r=m-1 and l=m+1, won't it be better if we return if the values in this new position != target? (To stop the search to left(or right) if we already reached left(or right) end)
solved it myself; here to compare and improve :)
great of the greatest 🙌🙌
You are amazing!
Hi, I have a question: my code looks almost the same to you expect my mid is m = l + (r - l) //2, when it executed test case: [2,2] 3, I got exceed time limit. but when I changed it to m = (l + r)//2, my code was accepted.
Respect, sir!
ur channel is a safe place to me haha
Had I watched your video before my interview, I would have cleared the interview :(
U a binary search God
Thanks this is so clear!
Do we need to define the leftBias function?
My first approach was binary search and it unfortunately didn't worked and had to switch to linear search and it worked just fine after a few tries with using few conditions and Boolean. And for some reason it was better than 100% java submissions for time complexity.
thanks boss
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binSearch(leftBias):
l, r, i = 0, len(nums)-1, -1
while l nums[mid]: l = mid + 1
elif target < nums[mid]: r = mid - 1
else:
i = mid
if leftBias: r = mid - 1
else: l = mid + 1
return i
return [binSearch(True), binSearch(False)]
If I use a two pointer method, left at index 0 and right at end of length, traverse each until both meets the target and return left, right.
Would this be o(n)?
Yes, O(n)
If we just add This will reduce 1 extra logN is the target is not present
if left == -1:
return [-1, -1]
Hi I am getting an error SyntaxError: 'return' outside function can you please suggest what to do?
Could we do it in one while loop?
Its easy to do it using lower bound and upper bound - 1.
Why can't the helper function be nested and just have leftBias as the input argument?
we use upper bound and lower bound for this
Nice
Since its sorted cant you just iterate once you find either the left or right target index?
time complexity would be O(n) in that case the moment you start iterating. coz in worst case you can have an array with all elements as target.
Bringing the Algorithms 101
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search_leftmost(A,T):
L = 0
R = len(A)
while L < R:
m = floor((L + R) / 2)
if A[m] < T:
L = m + 1
else:
R = m
return L
def binary_search_rightmost(A,T):
L = 0
R = len(A)
while L < R:
m = floor((L + R) / 2)
if A[m] > T:
R = m
else:
L = m + 1
return R - 1
l = binary_search_leftmost(nums,target)
r = binary_search_rightmost(nums,target)
return [l,r] if target in nums else [-1,-1]
what is the use of leftbias?
got it
isn't the time complexity O(log(n^2))
why need to update the left and right pointers when finding the target variable
Because we need to search most left and most right el
How's it Log(N) everywhere it's showing as Log(N) TC. But no, it's O(Log(N)) before it enters in the last else block, as it enters the last else block it will iteratively reset the binary search for about log(N) times. So the time complexity should be O(log(N)*log(N)). Open to suggestions.
In the last loop we have some l and r index, so we have some range like r - l + 1 to check. And after that it not get bigger, after one operation we always get to check (r - l + 1) / 2 range. So it's log(n) because we always divide range by 2
How to run this in jupyter notebook
Code is good but for worst case, the complexity would be O(n) which is not acceptable
can you pls explain why it's O(n) in worst case?
Here's my solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
leftpos, rightpos = -1, -1
l, r = 0, len(nums)-1
while l = 0 and nums[mid-1] == target:
mid -= 1
leftpos = mid
while mid+1 target:
r = mid - 1
else:
l = mid + 1
return [leftpos, rightpos]
smart
It's O(n), when we have the test case like (8, 8, 8, 8, 8), target 8.
how is it medium?
can some one tell me why can't i use this:-
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
for i in nums:
if target not in nums or len(nums)==0:
return [-1, -1]
elif target in nums:
return [nums.index(target), len(nums) - 1 - nums[::-1].index(target)]
And also this doesn't satisfy the Case 3:-
Input: nums = [], target = 0
Output: [-1,-1]
Please tell me why .....
Because the time complexity will be O(n) in the worst case. If all the elements are target.
video request!: leetcode.com/problems/jump-game/
the DP solution is quadratic time. but the greedy one is linear?! could you help explain how the greedy works lol
Yeah, I like that problem, I'm gonna try to do it soon, thank you for the request!
hello my fellow sharpenarians
This code doesn't works for me
hay
why i = -1
I cheated and used floats.
93% Faster - 64 ms and 61% better memory usage
class Solution(object):
def searchRange(self, nums, target):
l=0
h=len(nums)-1
loc = ['p']*2
if len(nums)==0:
return [-1,-1]
if len(nums)==1 and target==nums[0]:
return [0,0]
if len(nums)==1 and target!=nums[0]:
return [-1,-1]
while l
lol i came for the edge cases and they are not there whats the point on teaching the simple binary search 😂😂
can you provide one edge case
My solution:
public class Solution {
public int[] SearchRange(int[] nums, int target) {
int[] res = {-1, -1};
if(nums.Length == 0) return res;
int l = 0;
int r = nums.Length - 1;
while(l