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

[@rostam_1ted331]

Me too!

[@aryanyadav3926]

Using leftBias boolean variable was very clever.

[@aviralarpan7350]

Lol

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

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

[@appcolab]

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

[@healing1000]

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

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

[@yunaliu5946]

Best solution that I have ever seen

[@ShivangiSingh-wc3gk]

The binary search updates were very intutive thank you

[@atg878]

great of the greatest 🙌🙌

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

[@meetpatel4750]

Minor best case time improvement: we can start from "left" instead of 0 when doing the binary search for right boundary.

[@chenlee7934]

This is the best explanation i watched, thank u.

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

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

[@glen6638]

Nice , it’s easy to understand.👍

[@arindammandal1513]

Always love ur explanation bro!!!

[@ltxlouis3918]

Thank you! Great explanation

[@eshabaweja]

solved it myself; here to compare and improve :)

[@sanjeeeeev]

Best Explaination EVER 🔥

[@vikassharma-ky1dv]

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

[@jennielieu3312]

Do we need to define the leftBias function?

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

[@sivaganesh4489]

awesome explanation

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

[@edwardteach2]

U a binary search God

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

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

[@今天比昨天厲害]

You are amazing!

[@AdityaBhongade]

Respect, sir!

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

[@samCoder]

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

[@Charmask_creation]

class Solution { public: vector searchRange(vector& nums, int target) { sort(nums.begin(),nums.end()); bool start=false; int first=-1; int last=-1; if (nums.empty()) { return {-1,-1}; // Return {-1, -1} for an empty array } for(int i=0 ; i

[@jnayehsirine6222]

ur channel is a safe place to me haha

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

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

[@eamonmahon6622]

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

[@Charmask_creation]

class Solution { public: int findMin(vector& nums) { int size = nums.size(); if (size == 0) { return -1; } if (size == 1) { return nums[0]; } int left = 0; int right = size - 1; int res = nums[0]; while (left

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

[@xinniu3145]

Thanks this is so clear!

[@SaulLee66]

Could we do it in one while loop?

[@satyakidas4835]

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

[@danishshaikh6151]

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

[@akshayskumar2427]

what is the use of leftbias?

[@nagendrabommireddi8437]

thanks boss

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

[@LazyCoder20]

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

[@Vivekkumar-zc7mz]

we use upper bound and lower bound for this

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

[@igorf243]

how is it medium?

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

[@__Y1a2s3h4__]

This code doesn't works for me

[@krishgusain3959]

got it

[@gxyxy1012]

m= l + (r-l)/2

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

[@eugene6070]

hello my fellow sharpenarians

[@nathamuni9435]

hay

[@lostmeme9862]

I cheated and used floats.

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