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

[@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

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

[@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!

[@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!

[@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)

[@ShivangiSingh-wc3gk]

The binary search updates were very intutive thank you

[@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

[@vikassharma-ky1dv]

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

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

[@yunaliu5946]

Best solution that I have ever seen

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

[@qazyip]

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?

[@anshumansharma6758]

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

[@eshabaweja]

solved it myself; here to compare and improve :)

[@CasualyinAir]

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

[@chenlee7934]

This is the best explanation i watched, thank u.

[@ChanChan-pg4wu]

Great Explanation! Thanks for your smart and hard work.

[@atg878]

great of the greatest 🙌🙌

[@ltxlouis3918]

Thank you! Great explanation

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

[@glen6638]

Nice , it’s easy to understand.👍

[@sivaganesh4489]

awesome explanation

[@danishshaikh6151]

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

[@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]

[@eamonmahon6622]

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

[@sanjeeeeev]

Best Explaination EVER 🔥

[@edwardteach2]

U a binary search God

[@satyakidas4835]

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

[@arindammandal1513]

Always love ur explanation bro!!!

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

[@samCoder]

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

[@SaulLee66]

Could we do it in one while loop?

[@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

[@LazyCoder20]

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

[@akshayskumar2427]

what is the use of leftbias?

[@AdityaBhongade]

Respect, sir!

[@Vivekkumar-zc7mz]

we use upper bound and lower bound for this

[@jnayehsirine6222]

ur channel is a safe place to me haha

[@今天比昨天厲害]

You are amazing!

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

[@5_tejabvs818]

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

[@igorf243]

how is it medium?

[@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

[@nagendrabommireddi8437]

thanks boss

[@xinniu3145]

Thanks this is so clear!

[@nodirbekhbudi1208]

How to run this in jupyter notebook

[@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?

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

[@yashsolanki3665]

Nice

[@krishgusain3959]

got it

[@__Y1a2s3h4__]

This code doesn't works for me

[@gxyxy1012]

m= l + (r-l)/2

[@eugene6070]

hello my fellow sharpenarians

[@nathamuni9435]

hay

[@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!

[@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

[@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

[@lostmeme9862]

I cheated and used floats.

[@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