19:10 Here, we won't insert 3 but 2 i.e, we won't be pushing size of the array but the position at which we inserted(1 based indexing wise). Nice solution btw :)
Thankyou, It was a nice video before jumping to the solution intuition were developed. Great work. But I have a small doubt when we are making helper array here we are storing the seq but there is no as such sequence exist as 1,2,6 just didn't get the binary search technique of yours. Rest was great
Thanks Sriram for asking , No, its not possible to build it in o(n) because to find the position and place the element, the best search is binary search with o(logn) time complexity and since you do this for elements, it is o(n*logn), In the approach using stack, consider 1 5 8 as example, stack has 1 5 8 now you want to place element 2 you pop 8 from stack you pop 5 from stack you push 2 in stack you put back 8 in stack (you will have to store 8 and put it again) time complexity would be o(n) fro each stack operation and for n elements it would be o(n2), similar to linear search , it has no advantage in terms of time complexity
Yes didi i understood the approach Like let's take this example 1 7 8 10 11 14 2 13 As long as the array is monotonically increasing , the stack solution seems to work, and the first time when this pattern is breached, (i.e) for 2 , this too would work as 2 would pop out everything except for 1 in it's quest to find the nearest smaller to it's left, The problem now occurs with 13 Because although 13 is greater than 2 we have no idea of how many monotonically increasing elements are lesser than 13 as they have been erased from the stack, 13 could essentially lie in a range which is in between the popped elements , like here 13 should come between 11 and 14 but we don't have access to that info. This is why the stack solution wouldn't work in o(n) as we would have to re-push the elements which would make the conplexity o(n^2). Hence we can use binary search to ascertain the number of elements lesser than it to find it's lis or the number of elements greater than it to form the lds. It makes sense now 🔥🔥👍👍😁😁 Thanks for pointing it out didi and hope our convo here helps someone understand the question even better 🙏👍
Sister once pay attention to the LIS you build using LIS naive and LIS optimal You explained.. Dont you think while using LIS optimal when we encounter lesser element then the count of lis correspoding to that element should be the index which we are searching using binary search
@@nisheksharma7583 No it is not based on intuition or any such bullshit. In order to solve this problem, you need to know LIS. Thats the pre-requisite. If you dont know LIS, you can't solve this problem. As simple as that. If you know LIS, you know it can be solved by DP. Hence it is also a DP problem. The reason this question is hard is because it needs you to find the LIS from different sides and than do some more calculations on top of it. We create this stigma that you need to have intuition and what not to learn and solve DP problems, but the reality is not that. It boils down to whether you have seen similar problems before or not, and if you have, whether you can apply that knowledge in the new problems.
code solution :
class Solution {
vector LIS(vectornums)
{
int n=nums.size();
vectordp(n,1);
vectorhelper;
helper.push_back(nums[0]);
int ind=0;
for(int i=1;ihelper[ind]) {
ind++;
helper.push_back(nums[i]);
}
else {
putproper(nums[i],helper,ind);
}
dp[i]=ind+1;
}
return dp;
}
void putproper(int val,vector&arr,int lastind) //binary search to put element at correct position
{
int start=0;
int end=lastind;
int mid;
while(startval)
end=mid;
else
start=mid+1;
}
arr[start]=val;
}
public:
int minimumMountainRemovals(vector& arr) {
int n=arr.size();
vectorinc=LIS(arr);
reverse(arr.begin(),arr.end());
vectordec=LIS(arr);
reverse(dec.begin(),dec.end());
int ans=n;
for(int i=0;i1 and dec[i]>1)
ans=min(ans,n-inc[i]-dec[i]+1);
}
return ans;
}
};
Been a fan of your example based logic bilding approach! Keep up the great work!
Thank you so much
19:10
Here, we won't insert 3 but 2 i.e, we won't be pushing size of the array but the position at which we inserted(1 based indexing wise).
Nice solution btw :)
Nice Solution , Keep making videos like this :) .
Thankyou,
It was a nice video before jumping to the solution intuition were developed. Great work.
But I have a small doubt when we are making helper array here we are storing the seq but there is no as such sequence exist as 1,2,6 just didn't get the binary search technique of yours. Rest was great
class Solution {
public:
int minimumMountainRemovals(vector& nums) {
int n=nums.size();
vectorlis1(n,0);
vectorlis2(n,0);
vectortemp;
for(int i=0;itemp.back()){
temp.push_back(nums[i]);
lis1[i]=temp.size();
}
else{
int idx=lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
temp[idx]=nums[i];
lis1[i]=idx+1;
}
}
temp.clear();
reverse(nums.begin(),nums.end());
for(int i=0;itemp.back()){
temp.push_back(nums[i]);
lis2[i]=temp.size();
}
else{
int idx=lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
temp[idx]=nums[i];
lis2[i]=idx+1;
}
}
reverse(lis2.begin(),lis2.end());
int ans=INT_MAX;
for(int i=0;i
Thank u
Thanks😃
Nice explanation
Samaj aagya, thanks!
nice explanation
One doubt. Where is INT_MAX defined? And what is it's value?
That's fixed value
Can you share the code?
Can we build the lis array with the nearest smaller to left approach in o(n) the size of the stack would be the ans of the lis array for each index
Thanks Sriram for asking , No, its not possible to build it in o(n) because to find the position and place the element, the best search is binary search with o(logn) time complexity and since you do this for elements, it is o(n*logn),
In the approach using stack, consider 1 5 8 as example,
stack has 1 5 8
now you want to place element 2
you pop 8 from stack
you pop 5 from stack
you push 2 in stack
you put back 8 in stack (you will have to store 8 and put it again)
time complexity would be o(n) fro each stack operation and for n elements it would be o(n2), similar to linear search , it has no advantage in terms of time complexity
Yes didi i understood the approach
Like let's take this example
1 7 8 10 11 14 2 13
As long as the array is monotonically increasing , the stack solution seems to work, and the first time when this pattern is breached, (i.e) for 2 , this too would work as 2 would pop out everything except for 1 in it's quest to find the nearest smaller to it's left,
The problem now occurs with 13
Because although 13 is greater than 2 we have no idea of how many monotonically increasing elements are lesser than 13 as they have been erased from the stack, 13 could essentially lie in a range which is in between the popped elements , like here 13 should come between 11 and 14 but we don't have access to that info. This is why the stack solution wouldn't work in o(n) as we would have to re-push the elements which would make the conplexity o(n^2). Hence we can use binary search to ascertain the number of elements lesser than it to find it's lis or the number of elements greater than it to form the lds.
It makes sense now 🔥🔥👍👍😁😁
Thanks for pointing it out didi and hope our convo here helps someone understand the question even better 🙏👍
beautiful explaination !!. Can you share your github?
Sister once pay attention to the LIS you build using LIS naive and LIS optimal You explained.. Dont you think while using LIS optimal when we encounter lesser element then the count of lis correspoding to that element should be the index which we are searching using binary search
Like What you Build Using naive is:
1 1 1 2 3 2 3 1(corrct)
And what you build using optimal
1 1 1 2 3 3 3 1(incor)
Can any one say how can we thought that it is dp programming?
it's purely based on intuition which comes with practice
@@nisheksharma7583 No it is not based on intuition or any such bullshit. In order to solve this problem, you need to know LIS. Thats the pre-requisite. If you dont know LIS, you can't solve this problem. As simple as that. If you know LIS, you know it can be solved by DP. Hence it is also a DP problem. The reason this question is hard is because it needs you to find the LIS from different sides and than do some more calculations on top of it. We create this stigma that you need to have intuition and what not to learn and solve DP problems, but the reality is not that. It boils down to whether you have seen similar problems before or not, and if you have, whether you can apply that knowledge in the new problems.
Which college you are from?
rakhi bandhni hai kya?