First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34

[@NeetCode]

💡 BINARY SEARCH PLAYLIST: kzbin.info/www/bejne/i2m7doGtnZ2Cr5o

[@MP-ny3ep]

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

[@Chirayu19]

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!

[@mr.victory.]

same

[@nataliagrigoryeva6615]

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.

[@aryanyadav3926]

Using leftBias boolean variable was very clever.

[@aviralarpan7350]

Lol

[@nishanttanwar99]

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.

[@healing1000]

Thank you. This is better than all leetcode discuss solutions. I don't even think I will forget this one

[@appcolab]

Wow!! Man, I love this. I was just coming across some complicated solutions but this 🔥, thank you so much!

[@MsSkip60]

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

[@yalebass]

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!

[@vikassharma-ky1dv]

We can optimise it further by finding first index , if not found we need not find second Index

[@ShivangiSingh-wc3gk]

The binary search updates were very intutive thank you

[@yunaliu5946]

Best solution that I have ever seen

[@samCoder]

Had I watched your video before my interview, I would have cleared the interview :(

[@vaibhavdesai16]

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

[@basic-2-advance]

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]

[@danielbzhang3280]

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]

[@pragateesh5545]

smart

[@haruhipoulain8953]

It's O(n), when we have the test case like (8, 8, 8, 8, 8), target 8.

[@eshabaweja]

solved it myself; here to compare and improve :)

[@chenlee7934]

This is the best explanation i watched, thank u.

[@HR-pz7ts]

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.

[@anandhu5082]

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)

[@ChanChan-pg4wu]

Great Explanation! Thanks for your smart and hard work.

[@anshumansharma6758]

You explain very well. Thanks for working hard on these explanations

[@CasualyinAir]

Thanks! Very clean approach. I like your explanation too, very concise.

[@atg878]

great of the greatest 🙌🙌

[@glen6638]

Nice , it’s easy to understand.👍

[@edwardteach2]

U a binary search God

[@jnayehsirine6222]

ur channel is a safe place to me haha

[@sanjeeeeev]

Best Explaination EVER 🔥

[@danishshaikh6151]

If we just add This will reduce 1 extra logN is the target is not present if left == -1: return [-1, -1]

[@arindammandal1513]

Always love ur explanation bro!!!

[@ltxlouis3918]

Thank you! Great explanation

[@yfh7024]

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.

[@scurgames]

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)?

[@Lambyyy]

Yes, O(n)

[@jennielieu3312]

Do we need to define the leftBias function?

[@sivaganesh4489]

awesome explanation

[@AdityaBhongade]

Respect, sir!

[@今天比昨天厲害]

You are amazing!

[@LazyCoder20]

Its easy to do it using lower bound and upper bound - 1.

[@Vivekkumar-zc7mz]

we use upper bound and lower bound for this

[@yuanfeng4843]

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)]

[@eamonmahon6622]

Why can't the helper function be nested and just have leftBias as the input argument?

[@satyakidas4835]

Hi I am getting an error SyntaxError: 'return' outside function can you please suggest what to do?

[@nagendrabommireddi8437]

thanks boss

[@jhonrobaon1669]

Code is good but for worst case, the complexity would be O(n) which is not acceptable

[@denniskang6768]

can you pls explain why it's O(n) in worst case?

[@ShashwataSaha-wb8qd]

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.

[@haruhipoulain8953]

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

[@5_tejabvs818]

isn't the time complexity O(log(n^2))

[@abhinav_mittal]

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 .....

[@RichItUp]

Because the time complexity will be O(n) in the worst case. If all the elements are target.

[@xinniu3145]

Thanks this is so clear!

[@sensei1781]

Since its sorted cant you just iterate once you find either the left or right target index?

[@myroncarvalho4872]

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.

[@akshayskumar2427]

what is the use of leftbias?

[@SaulLee66]

Could we do it in one while loop?

[@yashsolanki3665]

Nice

[@krishgusain3959]

got it

[@henrydi800]

why need to update the left and right pointers when finding the target variable

[@haruhipoulain8953]

Because we need to search most left and most right el

[@nodirbekhbudi1208]

How to run this in jupyter notebook

[@igorf243]

how is it medium?

[@eugene6070]

hello my fellow sharpenarians

[@__Y1a2s3h4__]

This code doesn't works for me

[@gxyxy1012]

m= l + (r-l)/2

[@shubham2440]

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

[@nathamuni9435]

hay

[@lostmeme9862]

I cheated and used floats.

[@sniff4643]

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

[@NeetCode]

Yeah, I like that problem, I'm gonna try to do it soon, thank you for the request!

[@ARkhan-xw8ud]

why i = -1

[@raymonddelacruz9790]

if the target can't be found in the array the expected result would be -1 that's why i = -1

[@piyushbansal9716]

lol i came for the edge cases and they are not there whats the point on teaching the simple binary search 😂😂

[@arunr2265]

can you provide one edge case

[@aleksproger_il]

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