BS-3. First and Last Occurrences in Array | Count occurrences in Array

[@takeUforward]

Please comment understood and give us a like if you got everything :)

[@sudhanshushekhar4222]

Understood

[@venup2813]

Understood

[@alishashaikh3859]

Understood Sir.Thank you so much for your efforts

[@pardhi8959]

understood

[@mohammedahtesham7972]

understood

[@kumpatisupriya3947]

"Don't need any paid resources when there's aStriver's free DSA playlist and DSA sheet. I'm sooooo grateful to you, bro! 🙇‍♂🙇‍♀🙇 Thank you!"

[@pranavmandke8829]

At first I had trouble with lower, upper bound. But when I saw like the first 5 mins of the video, I could code the entire thing in one go!! Thanks a lot for such a clear explaination!

[@MrProgrammerJay]

You make us Feel DSA. Thanks for Amazing Lectures.

[@Nikhil-xx5bh]

I have gone through many KZbin playlist and paid courses, but this playlist is one of the best I have ever seen.

[@shubhamagarwal1434]

#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.....

[@siddharthkhandelwal933]

The edge cases in finding upperbound are 1. The element>k may not exist in that case low==n , now if arr[low-1]==k then UB=low-1 else UB=-1 2. The element>k exist at index =index ,now if arr[index-1]==k UB=index-1 else then UB=-1

[@AyushMishra-b8w]

If lower bound does not exist there is no need to find upperbound

[@_._escanor_._]

man this guys teaching energy levels are in whole another level dude !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1

[@jayant-baid]

I have seen your book allocation, aggression cows problems, and I understood everything. Excited to see and learn more such question from U in BS series

[@abhay9994]

Thank you so much, Striver! Your DSA course has been incredibly helpful to me. I've learned a lot and it has greatly improved my understanding of data structures and algorithms. Thank you for your dedication and expertise in creating such a valuable resource. I'm truly grateful for all the knowledge and skills I've gained through your course!❣❣

[@saksham_1612]

How do you watch like you try a problem first then see solutions or you directly see solutions and then try other problems of the same concept

[@utkarshprakash7837]

Every topic of DSA learnt from you with such beautiful explanation. Thanks striver❤

[@JalalMujawar]

Thank you for great video, we can avoid repeating the same code in both methods for finding the firstIndex and last using a simple boolean. flag: public int[] searchRange(int[] nums, int target) { int[] ans = {-1,-1}; if(nums.length == 0){ return ans; } int startIndex = search(nums, target, true); int endIndex = search(nums, target, false); ans[0] = startIndex; ans[1] = endIndex; return ans; } int search(int[] nums, int target, boolean findFirstIndex){ int ans = -1; int start = 0; int end = nums.length; while(start = nums.length) return ans; if (target < nums[mid]) end = mid - 1; else if (target > nums[mid]) start = mid + 1; else { ans = mid; if (findFirstIndex) end = mid -1; else start = mid + 1; } } return ans; }

[@Manishgupta200]

Solve the problem by using lower and upper bound approach was very tricky and smartly approach

[@nikhilhaspe2734]

Hats Off brother. Because your explanation I was able to code the below code. NOTE: Here is the dependency between first & last occurence, I mean you have to know if there is first occ. then you will find the last otherwise not. But what if we need to find them seprately i.e first & last occ. independently so below is the code for the same in Java class Solution { // Get Lower Bound // Means smallest index such that, arr[index] >= target public int getFirstOcc(int[] arr, int target){ int lb=0, ub=arr.length-1, mid, firstOccIndex=arr.length; while(lb = target){ firstOccIndex = mid; ub = mid - 1; }else{ lb = mid + 1; } } if(firstOccIndex == arr.length || arr[firstOccIndex] != target) return -1; else return firstOccIndex; } // Get Upper Bound // Means smallest index such that, arr[index] > target public int getLastOcc(int[] arr, int target){ int lb=0, ub=arr.length-1, mid, lastOccIndex=arr.length; while(lb target){ ub = mid - 1; lastOccIndex = mid; }else{ lb = mid + 1; } } if(lastOccIndex == 0) return -1; if(lastOccIndex == arr.length && arr[lastOccIndex-1] != target) return -1; if(arr[lastOccIndex-1] != target) return -1; return lastOccIndex - 1; } public int[] searchRange(int[] nums, int target) { int[] res = new int[2]; res[0] = getFirstOcc(nums, target); res[1] = getLastOcc(nums, target); return res; } }

[@PrianshYajnik]

I found the second solution myself after the recursion series . Thank you striver

[@BhaveshKumar-z1h]

Thank you Striver for creating such helpful content.

[@CodewithKing360]

understood perfectly stdBinarySearch & using lowerBound&upperBounds

[@chathuryachenchupalli6535]

Most useful video for beginners Totally satisfied and well understand

[@rishabh1S]

Understood! Please continue this placement series.

[@anuragsingh8910]

0:00 Intro 0:28 Problem Statement (First and Last Occurrences in Array) Explanation 1:28 Brute force method 2:46 Brute force pseudocode 3:33 Time Complexity of Brute force method 3:43 Optimised Solution (using lower_bound() method) 6:23 Covering the corner cases 8:21 Optimised Solution Code 9:47 Time and Space Complexity Analysis 10:35 Simple Binary Search approach for the problem 18:19 Pseudocode of the Binary Search approach 22:07 Code of the Binary Search approach (in C++) 23:15 Moving on to next problem (Count occurrences in Array) 24:34 Outro

[@raaviumasusmitha937]

awww!....23:43 @striver your smile🤩

[@rushidesai2836]

Optimal solution was pretty genius.

[@akhiljainth7960]

Striver, you are just amazing 🔥🔥🙏🙏, how simply you just taught a topic is insane.

[@manavsingh5919]

Thank You so much....Understood everything

[@Shivi32590]

Don't need any paid resources when there's a Striver's free DSA playlist and DSA sheet. I'm sooooo grateful to you, bro! Thank you!"

[@mohammedraiyaan-bt6iy]

Awesome lecture sir ❤❤❤❤

[@BhargaviKalla-hl4np]

thank you bro, i have learned a lot from this video,once again thank you bro

[@bhushanambhore8378]

Smoothest Explanation!

[@ashishbm3565]

bhai kya bande ho yar tum!! just awesome teaching like a woowww!!!

[@77-siddharthsattyam24]

class Solution { public: vector searchRange(vector& nums, int target) { vectorans(2,-1); int lo = 0; int hi = nums.size()-1; while(lo target) hi = mid-1; else lo = mid+1; } return ans; } };

[@paraschinchalkar1599]

did not understand it in first go,but will try again to find the solutions and the logic by myself

[@cinime]

Understood! Super fantastic explanation as always, thank you so so much for your effort!!

[@saswatrath4646]

Understood but it was unique in itself to know that some interviewers might also won't know about lower and upper bounds.

[@asphasquad3016]

Striver is a magician which have a magic to make any topic like a cup of cake😊

[@suryanshsingh5304]

Understood! Amazing series

[@LearnerAbhi21]

Understood very well bhai . And your energetic way of teaching makes it more interesting, thanx bhai, i am new to your channel, already late, but iguess its fine, no point in making regret in mind, eventually i will get my destination if i work hard, consistently...!!!

[@dipingrover1970]

normal binary search i was able to do it on my own thanks a lot . 😊

[@MYMIND252]

form now i am love with DSA thanks to you boss gulabi dil gulabi dil

[@PoojaGurumurtiTamragouri]

Understood, Best tutorial !!

[@arnabsarkar5245]

I solved the count occurrences wala question using lower bound and upper bound method, i hole it will be accepted in the interview :)

[@AnjuGupta-sz1uk]

understood! really well explained

[@naliniprakash7738]

It's crystal clear striver, I think this approach had more repeat nature. what if, when we find our x with BS, and move left side linearly to first index, and move right linearly to get last index ?

[@innocentgamer8670]

that's again 0(N) , means the time complexity will increase , because it will iterate through every point

[@agni5051]

Understood! lekin striver bhai ek chiz bolungi, thoda sa so bhi liya kro.

[@vishaljoshi7752]

One lowerBound function only - search key and key+1 (-1) int pos(const vector& arr,int n ,int key) { int l = 0; int h = n-1; int mid; int index = arr.size(); while(l= key) { index = mid; h = mid-1; } else l = mid+1; } return index; } pair firstAndLastPosition(vector& nums, int n, int k) { int fp=-1,lp=-1; fp = pos(nums,n,k); lp = pos(nums,n,k+1)-1; if(fp

[@AluwalaSrujan0523]

good work bro

[@mainakdasgupta7130]

ohhh yess !! i found the god

[@kingbadshah452]

thanks striver understood everything

[@striverdaaadi]

best playlist ever👌👌👌

[@blurbmusic1507]

love the energy sir

[@DevanshiKapla]

UnderStoodddddd , Super Fantastic explanation thankyouuuuuuuu striver

[@bhavuk2338]

the edge case is just that the lower bound should not be equal to upper bound for the first and last occurence problem. if lb==ub then ans={-1,-1} else {lb,ub-1}

[@tanya8353]

Understood!! and again thanks for such a wonderful job!!

[@fenilpatel6238]

count Occurence is done with map

[@fenilpatel6238]

But here we talk about binary search then it done with binary search don't be distract

[@tapans9275]

Why doesn't the upper bound have any conditions like the lower bound in the first and last occurrence of an element in an array?

[@CodeNinjaByte]

there are 2 cases: 1. if element present then lower bound present same element and uppper bound present element greater then that , in striver example lower bound is 8 and upper bound is 11 in case of x=8 2. but if its not present then upper bound and lower bound will point to the same element soo lower bound ki condition write kr de means voh he upper bound ki hogi

[@your_name96]

while checking for lb , he automatically checks if the element is present or not for ub as well.

[@KrishnaKumar-b4m9p]

in one sentence. because suppose if there happens any sort of problem with upper bound then the the first occurence of the element will also be the last occurence of the element. so after checking the conditions for lower bound no need to check anything for upper bound.

[@md.imrankhan6912]

Thank you mr legend

[@RISHABH-VERMA]

HATS OFF TO YOU SIR ❤, WHAT AN EXPLANATION

[@venkat.sairam]

🎯 Key Takeaways for quick navigation: 00:02 📺 The video is part of a playlist in a DSA course called "Strivers A to Z DSA." 00:30 🧐 The problem being discussed is about finding the first and last occurrence of a given number X in a sorted array. 01:35 🤔 The initial solution involves a linear iteration through the array, checking and updating the first and last occurrence indices. 03:35 ⏰ The time complexity of the initial solution is O(n), which is not optimal for sorted arrays. 04:18 🧠 The goal is to optimize the solution to have a time complexity better than O(n). 05:10 📈 The concept of "lower bound" and "upper bound" is introduced to optimize the solution. 08:24 💻 Pseudocode for using "lower bound" and "upper bound" to find first and last occurrences is presented. 09:56 ⚙️ The time complexity of this optimized solution is O(log n), a significant improvement. 10:24 🔍 Some interviewers may request a binary search solution without using "lower bound" and "upper bound." 16:13 🔄 Binary search for finding the first and last occurrences is demonstrated with different scenarios. 18:45 📝 Pseudocode for writing custom binary search functions to find first and last occurrences is provided. 22:36 ⚠️ Be careful about edge cases where the element X may not exist in the array, which could affect the last occurrence calculation. 24:13 🧩 To count occurrences of X in a sorted array with duplicates, you can use the formula: (last occurrence - first occurrence) + 1. 24:39 👍 The presenter encourages viewers to understand the logic behind low bound and upper bound implementations for future coding rounds. Made with HARPA AI

[@depelterturbo]

Amazing

[@aakashsharma780]

Understood Striver bhaiya 🙌

[@HarshChoudhary-vm6eh]

Understood! Very well.... thanks bhaiya for such energetic with awesome explanation videos... :)

[@k.satish3663]

Understood! Clean explanation

[@KrishnaKumar-b4m9p]

while finding the last occurence we are doing upper bound -- 1 . but suppose there do not exist any last occurence of an element. In that case what is gonna happen????

[@Pooja-wb7gy]

This is all good I do understand the logic properly even I know how it is working and everything but when ever I try to code this on my own , I end it up with errors, like I familiar with c++ but it becomes hard for me to code these types of problems pls guide me what should I do to write these codes on my own,

[@pacifier8282]

Your basics is not clear that may be the reason , practice solving questions thats the only way

[@visheshdadhich6636]

Very good video!

[@jayantachakraborty6066]

it feels really nice. Sitting in the Striver's Hostel Room of college and studying from you dada..😃 take love...

[@RagaviSathiyamoorthy]

Thank you bhaii understood so clearly and this is the first time I'm solving a medium level problem in leetcode with a clear understanding.

[@AnjaliChoudhary-r3f]

Is there some confusion in lower bound and upper bound

[@oyeesharme]

thanks bhaiya

[@abulkhayer8176]

Note : For the last problem(counting occurences), using unordered_map is the optimal approach.

[@RaunitJaiswal-s9v]

Done enough for today

[@crazybro4383]

I have a doubt in the approach in which we use lower bound and upper bound- In edge case you have taken if lb==n || arr[lb] !=k.........but according to me it should be if ub==n. Becoz what if array is 1 2 3 4 5 and target is 5......lb will point to the element 5 but ub will point to the the place after 5 ie n........so ub==n will take care of that edge case also but lb==n will not

[@NonameNoname-f2t]

UNDERSTOOD WELL AND GOOD SIR!!!!!!!!!!!

[@infernogamer52]

Understood Bhaiya!

[@pragatii9054]

Thank you 😊so much

[@khalasianiket816]

understood❤

[@SYCOA12CHAITANYAASOLE]

Understood !! 😍😍

[@abhaymandal4903]

Understood!! Able to silve

[@anishsinha3272]

can we simply do it by floor and ceil indices?

[@augustinradjou3909]

Understood baiya

[@NAMAN-gr5lc]

UNDERSTOODDDD!

[@divakarmishra_3792]

understood!

[@Lofisasddle]

understood bhaiya

[@AnmolGupta-oj4lm]

Understood Very Well!

[@abdussalam-4836]

Striver is the best we have.

[@sayantanpoddar5428]

understood understood understood

[@per.seus._]

UNDERSTOOD💔

[@ankush8243]

Thank you very much! 🙌💯❣

[@yikes3807]

Thankful 🥰 understood

[@VikasVerma-oo7fx]

Understood ❤

[@CodeMode9313]

Understood habibi

[@bkmeher9005]

outstanding bhai

[@mominarashad3103]

Is the link to code studio inaccessible ? or it is only me

[@NazeerBashaShaik]

Understood, thank you.

[@adityaverma898]

UNDERSTOOD😊

[@culeforever5408]

understood :)

[@tech_wizard9315]

Have you uploaded entire DP series?? ( From zero to advance level)

[@takeUforward]

Yes! Kitne br ek chiz puchoge

[@monstercoder3665]

​@@takeUforward He asks to drag your attention

[@AkanshaSahu-qp3kd]

@takeUforward Why did you remove the GFG problem links from the sheet bro??

[@VikasBagri-i5j]

Understood it very well... :)

[@deepakkumar13204]

Super explanation 😊

[@himanshidafouty347]

Understood

[@itzmartin20]

UNDERSTOOD SIR!

[@SubramanyanS-x3t]

can someone please ecplain how does this work .how he found out the answer of last problem by lastcourrence-firstocuracne +1?