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!
🎯 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
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
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
#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.....
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
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!❣❣
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; } }
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; }
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...!!!
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
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;
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
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.
First occurance by definition it means that whether the number is present in array or not Let's suppose the number is at last index that means first occurance is at last index and that would also mean last occurrence is also at last index but if it was never there then first occurance will point to hypothetical index ie after last index which means it was never there and if it's never there at first place it will never have a last occurrence
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,
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 ?
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}
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????
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
Please comment understood and give us a like if you got everything :)
Understood
Understood
Understood Sir.Thank you so much for your efforts
understood
understood
"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!"
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!
You make us Feel DSA.
Thanks for Amazing Lectures.
🎯 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
Amazing
I have gone through many TH-cam playlist and paid courses, but this playlist is one of the best I have ever seen.
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
If lower bound does not exist there is no need to find upperbound
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
#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.....
man this guys teaching energy levels are in whole another level dude !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1
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
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!❣❣
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
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;
}
}
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;
}
Every topic of DSA learnt from you with such beautiful explanation. Thanks striver❤
the best playlist in the internet.
Thank you Striver for creating such helpful content.
I found the second solution myself after the recursion series . Thank you striver
Understood! Super fantastic explanation as always, thank you so so much for your effort!!
Optimal solution was pretty genius.
awww!....23:43 @striver your smile🤩
Solve the problem by using lower and upper bound approach was very tricky and smartly approach
Most useful video for beginners
Totally satisfied and well understand
bhai kya bande ho yar tum!! just awesome teaching like a woowww!!!
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!"
Understood!
Please continue this placement series.
Striver in first question for loop should be i=0 to i
understood perfectly stdBinarySearch & using lowerBound&upperBounds
thank you bro, i have learned a lot from this video,once again thank you bro
Done on 11 Jan 2025 at 12:50
Place : Study Room 2 , Hostel 5, IIT Bombay
Bhai sahab iitb wale bhi iska channle dekhte hai. Means haintonham sab same lkein place ment achi iit waloki miltihai na ki hame
Striver, you are just amazing 🔥🔥🙏🙏, how simply you just taught a topic is insane.
form now i am love with DSA thanks to you boss gulabi dil gulabi dil
Striver is a magician which have a magic to make any topic like a cup of cake😊
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...!!!
Thank You so much....Understood everything
striver's energy 🔥🔥🔥🔥🔥🔥🔥
Awesome lecture sir ❤❤❤❤
Understood, Best tutorial !!
I solved the count occurrences wala question using lower bound and upper bound method, i hole it will be accepted in the interview :)
Understood! Very well.... thanks bhaiya for such energetic with awesome explanation videos... :)
normal binary search i was able to do it on my own thanks a lot . 😊
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
good work bro
Smoothest Explanation!
understood everything @Striver
UnderStoodddddd , Super Fantastic explanation thankyouuuuuuuu striver
Understood!! and again thanks for such a wonderful job!!
Understood but it was unique in itself to know that some interviewers might also won't know about lower and upper bounds.
Huge respect for your strife in explaining algorithms efficiently and clearly for beginners, dear sir.
Akshat Sharma
IIT Kanpur.
Year sir
it feels really nice. Sitting in the Striver's Hostel Room of college and studying from you dada..😃 take love...
Understood !!......Thanks Striver
understood! really well explained
did not understand it in first go,but will try again to find the solutions and the logic by myself
best playlist ever👌👌👌
Understood Striver bhaiya 🙌
Understood! Amazing series
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;
}
};
HATS OFF TO YOU SIR ❤, WHAT AN EXPLANATION
Understood! Clean explanation
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.
Note : For the last problem(counting occurences), using unordered_map is the optimal approach.
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?
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
while checking for lb , he automatically checks if the element is present or not for ub as well.
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.
I didn't understand 22:35.
Pls somebody explain this, if we didn't find it in first occurance, why will we not find it in last occurance?
First occurance by definition it means that whether the number is present in array or not
Let's suppose the number is at last index that means first occurance is at last index and that would also mean last occurrence is also at last index but if it was never there then first occurance will point to hypothetical index ie after last index which means it was never there and if it's never there at first place it will never have a last occurrence
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,
Your basics is not clear that may be the reason , practice solving questions thats the only way
Understood! lekin striver bhai ek chiz bolungi, thoda sa so bhi liya kro.
let's go --> 12 january 🔥🔥
There is in uilt function for upper and lower bound in cpp so u can use them
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 ?
that's again 0(N) , means the time complexity will increase , because it will iterate through every point
Is there some confusion in lower bound and upper bound
thanks striver understood everything
ohhh yess !! i found the god
Very good video!
Understood Bhaiya!
Understood !! 😍😍
Thank you mr legend
love the energy sir
Have you uploaded entire DP series?? ( From zero to advance level)
Yes! Kitne br ek chiz puchoge
@@takeUforward He asks to drag your attention
UNDERSTOOD WELL AND GOOD SIR!!!!!!!!!!!
understood very clearly
What is time complexity for the 2logn solution and last solution. two same right?
UNDERSTOOD💔
Understood it very well... :)
Super explanation 😊
what is last and first here 21:30 please let me know
can we simply do it by floor and ceil indices?
STRIVER 🔥🔥🔥🔥🔥🔥
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}
Thank you very much! 🙌💯❣
Thankful 🥰 understood
Understood Very Well!
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????
first watch.big fan bhaiya .
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
Understood!! Able to silve
Striver is the best we have.
Understood ❤
Understood habibi
Superb, understood.
Maza aa gya yr ❤
Understood sir 🙌🙌🤝
UNDERSTOOD😊