5 First and Last occurrence of an Element
Vložit
- čas přidán 10. 03. 2020
- FIND FIRST AND LAST POSITIONS OF AN ELEMENT IN A SORTED ARRAY:
Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.
Example:
Input : arr[] = {1, 3, 5, 5, 5, 5 ,67, 123, 125}
x = 5
Output : First Occurrence = 2
Last Occurrence = 5
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/find-fi...
PLAYLIST LINK: • Binary Search | Interv... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Sir, please bring in new lectures on the remaining topics . You have really been a boon to students who don't possess enough money to get paid courses. Thankyou .
Before this one, I was totally dependent on std::lower_bound and std::upper_bound. Thanks!
i am aslo trying it with lower_bound and upper-bound , but it's not working . can you please tell me about this
@@saikatchattaraj7441 lowerbound and upperbound works only in sorted arrays and vectors.Try using it in set in c++.
@@saikatchattaraj7441 if you got arr[mid]= target ,then
Find first occurence using lower_bound() and store it as index1, and then last occurrence using upper_bound() and store is at index2.
Final ans will be an {index1,index2-1}
@@vatsalmehta7159 Binary search also works on sorted arrays only .
Clear explanation. Was confused with Leet code template 1, template 2, template 3 for binary search. But Your explanation made it easy for me. Thanks !
love your short and crisp explanation. God bless you.
Awesome and most simplified. I was unable to think that we can save the mid and try to minimize. I was instead trying to go to a point where nums[mid] == target && (nums[mid - 1] < nums[mid]). All cases worked in my code except the one case. Hence, came here for solution and found easy logic to just save the mid and continue searching. Bhai tussi great ho!!
After diving through so many videos on this question, Yours is the one that made most sense to me!
Thanks Aditya!
Thanks bro..nice way of teaching. Please also add topics like Recursion, Greedy and Divide and conquer.
just Amazing. This word even can't describe how good you are as a teacher.
Before watching I found this problem on leetcode and can't solve in O(log n) but now I can.
What a great explanation!
One of the most underrated channel for good resources and easy explanations and approaches to complex problems.
Would be waiting for more topics coverage.
Thanks for your precious time in putting up this content. 🤝
Thanks! You explained very well.
Bro way of explanation is next level 🔥🔥
Really well explained! thanks
Bhai tum bahot achcha explain krte ho yaar.....thanks a lot...aise hi videos banate rahe
Nice explanation, was confused why high-1 is done, thanks :)
Bro nice explanation..Thank U ❤️❤️
Excellent tutorial, need not to change pen, your session becomes so interesting that the color combinations doesn't matter
Thanks Aditya, please come back ans teach us others topic. You are the best
Thank you brother a lot. It helped me a lot during my assignment.
I was actually looking for a video explaining using pen paper, Thanks
Did it by own, thanx for the concept
after getting the job I will definitely donate some amount to the growth of this channel.
mili job ?
@@MahimDashoraHackR Yup and thanks for asking.
If you want to connect then send connection request on LinkedIn @iampkr
@@piyushkumarrajput2779 Bro , I have searched your username in Linked in didn't find it . Want to connect with you
@@bsaikumarreddy1413 Connect with me using below link
www.linkedin.com/in/iampkr/
@@piyushkumarrajput2779 Kya salary h bhai
Crazy bro !! keep posting new solutions
Badiya bhai maaza agaya problem solve karke
Bhai boht shi video bnaya re jese apne dost smjhate hai vaise bdiya smjh aaya bidu 🔥🔥
Thank you vai what a explaination ❤️👍
if we have to return both first and last occurrence in a single program what will be the changes
Thank you very much. You are a genius.
The best explanation!!
I always learn something new in every video
Bro big thanks..
Better than most of the popular CZcams channels
thanks man you helped me alot in revisions and how we can link concepts
thanks for the video!
explained in a very easy manner
Thanks bhai, ek ghante se video dekh raha tha, sab chinese log samjha rahe the but ghanta kuch samjha nahi. Abhi apne bataya toh samjha.
Thank you Aditya !!!!!!!
Most underrated channel on CZcams
Can't we apply exponential search for this problem?
Bhaiya from where to find more problems jisme aste aste krke problem ka level increase kiya ho aur almost problem/question cover kiya ho ??
Thank you 👍👍
Thank you so much
Bhott acha pdhate ho ap bhaii!
after solving around 50 questions, I was able to think this logic on my own. Phew... more to go.
Thank you bhaiya
understood each and everything.....
thanks!!!
can we find both first and last in only one traversal ?
But how we can make the first and last occurrence in one program? PLease help
Nice.
Can you plz make videos on graph and backtracking
One correction : For last occurrence there will be "ArrayIndexOutOfBoundsException" if while loop condition is "start
nope,
@@Adarsh-mn7pl yes
Jada dimag maat lagya kar
Agar hum arr[start] ko access krte to aata ye error , hum ye nahi kr he to ni aayega
kya explnation tha man u nailed it
Sir In this binary search problem is already sorted and if the target is get so why need to do repeat process to find first occurrence,
We can just apply while loop when arr[mid]=target than res=mid; mid=mid-1;while(arr[mid]==target){res=mid; mid--;}
return res;
This thing can we do ?
Great 👍
What if, if we use lower bound for found first occurencee,,,
BTW,,Nice explanation ,bhaiaa,,,
Love from Bangladesh..
Please bhaiya aur videos dalo ....It is very helpful.
I saw many different videos but your way to explaining different to other .
I was just wondering ki what if the mid element itself is the first occurence , here then we are unnecessarily running binary search on left side array of mid element . So is its time complexity so neglible that we can ignore???????
I got one solution to it @Aditya Verma can you please check or even viewers can you u guys check this out
int firstOccurrence(int arr[],int len, int x)
{
int start = 0;
int end = len-1;
int res;
while(start
if l[mid] == x:
while l[mid-1]==x:
mid-=1
return mid
#you can have a look at it, it's in python though.
@@DeepakGupta-zz1vf Even if the mid element is the first occurrence, binary search has log n complexity which you can say is negligible to consider different cases.
Worst case complexity of binary search is logn
Shukriya Bhai, per ek aur help kar do isse recursion se karke bata do.
How can I write a more short code for this problem ??
vector searchRange(vector& nums, int target) {
int first=0,last=nums.size()-1,mid=ceil((first+last)/2);
vector v(2,-1);
if(nums.size()>0)
{
while(first
vector searchRange(vector& nums, int target) {
return {search(nums, target, "FIRST"),search(nums, target, "LAST")};
}
int search(vector nums, int target, string find){
int start = 0;
int end = nums.size() - 1;
int ans = -1;
while(start nums[mid]){
start = mid + 1;
}
else{
ans = mid;
if(find == "FIRST"){
end = mid - 1;
}
else{
start = mid + 1;
}
}
}
return ans;
}
@@divyanshverma495 Thanks a lot! This solution is really nice I understood it and tried it, it's working perfectly.
wat is its space complexity
JavaScript
Leetcode: 34
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const binarySearch = (arr, target, last) => {
let start = 0;
let end = arr.length - 1;
let res = -1;
while (start target) {
end = mid - 1;
} else if (arr[mid] < target) {
start = mid + 1;
}
}
return res;
}
var searchRange = function(arr, target) {
let res = [-1, -1]
if (arr.length === 0) {
return res;
}
const firstElement = binarySearch(arr, target, false);
const lastElement = binarySearch(arr, target, true);
res[0] = firstElement;
res[1] = lastElement;
return res;
};
Simple python code:
#1st and last occurance of element
class Solution:
def bs(self,nums,target):
l=0
r=len(nums)-1
res=-1
while l
so they dont ask complete code in interviews? just u can explain with pseudo code and working ?
It may also chance they will agree with pseudo code and its working flow. But in worst case ready to write code. It is minor tweak in original binary search algo.
unless you got them convinced that writing code is no big deal for you, they will make you write code for sure after discussing the approach.
How can i impliment of them together
can we use while loop here?
this one is also working.....
while (arr[mid] == target){
mid = mid -1;
}
return mid+1;
it will work but the time complexity will be linear. it defeats the reason we are using BS in the first place
bhaiya agar dimaag mein ye approach na aaye aur hum first occurance ke liye start index 0 se ek for loop chala de aur last occurance ke liye last index se reverse loop chala de to kaam chal sakta hai kya?i mean tle aane ke kya chances hain?
depend karta hai... aditya ka ek interview steps wala video hai... jisme woh TLE aur constraints ke barein mein bol raha hai.
to us se pata lag jaega... ki kitna time mein nikalna hai.
tumhara logic 2 loop wala.. O(n) mein execute hoga.
agar test case aur constrants ko O (log n) hi chahiye hoga.. to TLE lag jaega.
par itna buddhu to interview nain hota hai ki tumhe O(n) mein pooche... to identification kam aega us time pe
agar sorted array hai.. to binary search lagane ki soch sakte ho.
Sir if we need to do both then do we have to write 2 seperate programs?
yes... write two seprate function 1. first and 2, last. call them separately to get the results....
@@PradeepKumarIIITD Thanks
great
if array is in sorted order , and we found the element at mid, y we need to go left and right to check for another occurrence, we also check if arr[mid-1] == element and arr[mid+1] == element as it's sorted .
may be there will so many occurence which leads to time complexity problem as you are just checking linearily
this may be the code according to sir's explaination: class Solution {
public:
int firstOccurance(vector &nums, int target){
int start=0;
int end=nums.size()-1;
int result=-1;
while(starttarget){
end=mid-1;
}
else{
start=mid+1;
}
}
return result;
}
int lastOccurance(vector &nums, int target){
int start=0;
int end=nums.size()-1;
int result=-1;
while(starttarget){
end=mid-1;
}
else{
start=mid+1;
}
}
return result;
}
vector searchRange(vector& nums, int target) {
vector pair;
pair.push_back(firstOccurance(nums,target));
pair.push_back(lastOccurance(nums,target));
return pair;
}
};
find function can also br used to find the first occurrence. Isn't it better?
that would take linear time as builtin functions take up internal time
Ayan Das okay. Thanks
Thanks!
11 months phle hi padh liya BS :) your TA from iiitd :)
@@PradeepKumarIIITD areee bhai bhai bhai bhai😃 You got really good memory 😂
@@ajeetyadav1093 can't forget that DP....
@@PradeepKumarIIITD 😂
❤️❤️❤️❤️❤️
counting the no.of times you spoke "apan"...loll
#code using python
class Solution:
def Firstoccurence(self,A,B):
l=0
r=len(A)-1
l_ele=-1
while l
❤
when we find our mid == element, instead of doing BS again.. shouldn't we just check previous elements? As the array is sorted.
Okay, so lets just consider a case (worst case to be specific). let the array be
arr[]: [2(0),2(1),2(2),2(3),2(4),2(5),2(6),2(7),2(8)]--> where the number in brackets()--are the indexes, just try to run your approach and my approach on this, I think you will get it. If not continue reading this-> so basically in yours after having our mid which 2(4)--> you will have to do a linear search till end ie., 2(0). While in mine it will be log of n. I hope that clears your doubt.
makes sense.. (one suggestion: in your videos can you also discuss time complexities at least in the base scenario cases you discuss like in subset prob in DP .. here in classic BS problem..)
@@TheAdityaVerma we dont have to do linear search for it.. if we found that another same element is present in left side then we will call binary search else current element will be first occurance....
@@shailendrajain4231 I tried using that approach its giving TLE on gfg
thats a very good question and explanation by aditya sir is op too!
I have a doubt, i have used two pointers to get the starting and ending position, would the time complexity will be same as your approach?
left = mid;
right = mid;
while (left - 1 >= 0 && arr[left - 1] == x)
{
left--;
}
while (right + 1 < n && arr[right + 1] == x)
{
right++;
}
nahi bhai ye O(N) ho jaegi aur idhar tum galat assume kr rhe ho ki array me saare elements are target but array will have diff elements
The idea is that if we found the element at any place then for first occurance go to left part again and for last occurance go to right part again simple
don't forget to reinitializethe first and last i hope it helped someone
pair indexes(vector v, long long x)
{
// code here
int res=-1;
int ser=-1;
int first=0;
int last=v.size()-1;
while(first
what if, we have asked both first and last occurrences together
we can do if(ele==arr[mid] && arr[mid-1]!=ele)
What will be the complexity of this algorithm?
got it
Time Complexity : O(log n)
Auxiliary Space : O(1)
Yeah, I think yhi hona chahiye
The time complexity of normal binary search is O(log n), and we've added just one extra line to it, so it will be same .
We've Haven't used any auxiliary space, so yes constant space
can you add english titles please
trying out something in api call
I think the code is bit wrong ,here is my solution
int firstOccurence(vector &v,int element){
int hi = v.size()-1,lo = 0,mid;
int res = -1;
while (hi-lo>=0)
{
mid = lo + (hi-lo)/2;
//2 4 10 10 10 18 20
if (v[mid]==element)
{
res = mid;
hi = mid-1;
}
else if(v[mid] < element)
{
lo = mid +1;
}
else //(element< v[mid])
{
hi = mid-1;
}
}
return res;
}
int lastOccurence(vector &v, int element){
int hi = v.size()-1,lo = 0,mid;
int res = -1;
while (hi-lo>=0)
{
mid = lo + (hi-lo)/2;
if (v[mid]==element)
{
res = mid;
lo = mid +1;
}
else if (v[mid]
trying out mantain
While searching first occurrence find mid then further one can just check mid-1 element if that is less then mid
Then can directly return mid as answer
And no need to continue further search. 😊
Anyways thanks Aditya
This will create a corner case if you have answer as first index Eg searching 10 in {10,10,10,10,10,13,15,79}
Also check if mid-1 is greater than -1.
If mid-1=0 and arr[mid-1]==arr[mid] then end = mid-1
If mid-1>=0 and arr[mid-1]!=arr[mid] thrn return mid
lol what if there are >3 occurences ? then??
Nothing is useless kimd , use your brain for learning new thing not finding god's errors coz there are none
For my recurrence:
6:36
Kon se college se ho aap
College does not Matter a lot Bro if you have a Good Logic skill
Here is my solution: Leetcode: 34
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def getIndex(nums, left, right, target, search_for_first = True):
location = -1
while left target:
right = mid - 1
else:
left = mid + 1
return location
if len(nums) == 0:
return [-1,-1]
start_index = getIndex(nums, 0, len(nums) - 1, target)
if start_index != -1:
end_index = getIndex(nums, 0, len(nums) - 1, target, search_for_first=False)
if start_index != -1:
return [start_index, end_index]
else:
return [-1, -1]
I don't know why... but my last occurrence is not working
send code
You can check out my code:-
class Solution {
public:
vector searchRange(vector& nums, int target) {
int first=0,last=nums.size()-1,mid=ceil((first+last)/2);
vector v;
v.push_back(-1);
v.push_back(-1);
if(nums.size()>0)
{
while(first
Yrr ye pen kaise ghumata ho aap fingers mein🤨🤨
iske liye apko udemy ka course karna padega😂😂
5:27 pe galti hai, high = mid hoga, NOT high=mid-1, humko mid ko include karna hai, kyuki wo ek possible answer ho sakta hai, mid-1 nahi le sakte
Check kario bro ek baar
mid ko hum already res mein store karwa chuke hai then still we require to include mid as high=mid??
bhai us mid se phle hi toh check krenge ab kyuki usko toh vase bhi result mein store kr rkha h .isliye high=mid-1 shi h
trying out something
class Solution {
public:
vector searchRange(vector& nums, int target) {
return {BinarySearch(nums, target, "FIRST"), BinarySearch(nums, target, "LAST")};
}
int BinarySearch(vector nums, int num, string find) {
int left = 0, right = nums.size() - 1, mid;
int result = -1;
while (left num) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return result;
}
};
class Solution {
int f(long v[], long x){
int first = -1;
int s = 0;
int e = v.length -1;
while(sx)
e = mid -1;
else
s = mid + 1;
}
return first;
}
int l(long v[], long x){
int last = -1;
int s = 0;
int e = v.length -1;
while(sx)
e = mid -1;
else
s = mid + 1;
}
return last;
}
public pair indexes(long v[], long x)
{
// Your code goes here
return new pair(f(v,x),l(v,x));
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
Arrays.fill(res, -1);
//first occurrence
int start = 0;
int end = nums.length - 1;
while (start
function binary_serach_f(arr, key){
let start = 0;
let end = arr.length -1;
let res = -1;
// let asc = (arr[start] > arr[end]) ? false : true;
while(start