0:34 understanding the problem statement 5:26 Brute Force O(N^2) 6:16 Intution 9:56 Dry Run on Example 16:27 Prefix sum approach in array playlist 16:44 Code (Binary search) 20:50 Time Complexity O(nlogn)
Hello bhaiya a small suggestion in the last line Apne kaha ki the answer might be INT_MAX if all elements are equal. But that would not be the case because even if the min_element and max_element are equal, the binary search would still work for l
One question-Though it works correctly, but how, just comparing the consecutive costs for m and m+1 guarantees that cost is going to increase towards the direction where cost(by making every element equal to m+1)>cost(by making every element equal to m) for entire domain? ugh, like what if for m-1 and m+1 both, the cost decreases..
In context of the brute force approach how did you came to conclusion that to get minimum cost you need to make it equal to the element already present in tha array? can the equal element be equal to some other value not present in the array which may give minimum cost?
Good Qn. If you notice, if you make all elements equal to a value which is not in array say x, then ALL element conversion will cost me an amount > 0 , because no element in nums is equal to x. However, if we equate all elements to a value say y which is present in nums, then for atleast that value, the cost will be 0. So, there is no point in taking a value x which is not in nums.
JAVA IMPLEMENTATION class Solution { public long minCost(int[] nums, int[] cost) { int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE; for(int x:nums){ min=Math.min(min,x); max=Math.max(max,x); } int l=min,r=max; long ans=Integer.MAX_VALUE; while(l costForMid){ r=mid-1; }else{ l=mid+1; } } return ans==Integer.MAX_VALUE ? 0 : ans; } public long findCost(int mid,int[]nums,int[]cost){ long res=0L; for (int i = 0; i < nums.length; i++) { // int diff=Math.abs(mid-nums[i]); // res+=(long)diff*cost[i]; res+=(long)Math.abs(mid-nums[i])*cost[i]; } return res; } }
Important consideration here, why we can apply BS search and How can sure by checking mid+1 , we can neglect that half. The important thing we should check whenever we are applying BS is, what is the behaviour of search space. Here the search space from left to right is decreasing , local minimum and then increasing(& vice versa). We are just trying to find local min here. Since there is only single local min , hence we can arrive at a solution. If there is multiple local min we wont be able to apply binary search.
I think the last statement "answer == INT_MAX ? 0 : answer" is not needed since we have already declared answer to be max, and the cost will come out to be 0 if all the elements are equal which will make our answer = 0. Correct me if I'm wrong.
Basically this code assumes that all the test cases will be having unimodal graph but it might be the case that some test case has two minima , then it wont work correctly
you are making direct assumption that its not worth going to right if we get cost > cost at mid sir. can u prove that cost function is convex function ? how will i explain this assumption in interview ?
great explanation. please make a video on below Question, no explanation is available: Determine the minimal adjustment cost of an array Write an algorithm to replace each element in an array of positive integers such that the difference between adjacent elements in the array is less than or equal to a given target. The goal is to minimize the adjustment cost, which is the sum of differences between new and old values. In other words, minimize ∑|A[i] - Anew[i]|, where 0
if you try to check no of operation for all the values from (0 to MAX_VALUE ) you will see the values will first decrease and than increase inshort the graph will be in V shape and you can apply the binary search to find the minimum value nad he already explained with some test cases at 5:00 timestamp
Utube doesn't allow to post a link here. go to desmos (it creates graph) and then write the expression 2.\left|1-x ight|+3.\left|3-x ight|\ +1.\left|5-x ight|+14.\left|2-x ight| and create a table you will be able to visualize.
@@girikgarg8 let say y= ci * | Ni - x | where ci is the cost of the ith index Ni is the ith element and x is the val which we need to found here y = ci * | Ni - x | is a convex function so sum ( ci * | Ni - x | ) will also be convex there is also a proof which you can google it
Thanks For This Awesome Explaination...
You Are The Best 🔥
Thank you so much ❤️❤️
0:34 understanding the problem statement
5:26 Brute Force O(N^2)
6:16 Intution
9:56 Dry Run on Example
16:27 Prefix sum approach in array playlist
16:44 Code (Binary search)
20:50 Time Complexity O(nlogn)
❤️❤️❤️
greatest , bestest , and top level video on youtube of this queison , amazing sir
Thank you 😊 ❤️
Hello bhaiya a small suggestion in the last line
Apne kaha ki the answer might be INT_MAX if all elements are equal. But that would not be the case because even if the min_element and max_element are equal, the binary search would still work for l
Mik Sir you are the best ....Very Awesome Explanation.....God bless you sir
Thanks a lot ❤️❤️❤️
Superb explanation , Thank you
I’m glad you found it helpful! 🙏❤️
New concepts i learnt from this video:
Big constraints aren't scary
Binary search isn't as weak as i thought
Typedef
Hard questions are fun
Indeed ❤️❤️
Learned this useful concept ...Thanks for the explanation
Itna Easy hogya intuition dekh kr ki U can code by yourself
Thank you ❤️
You a leetcode God for me😭❤
❤️❤️❤️❤️
Did it on my own thanks for such nice videos
Clear and concise!
❤️❤️❤️
Simplest explanation ❤❤
❤️❤️
THANKU SO MUCH FOR MAKING HARDER QUESTION IN VERY EASY WAY
Means a lot ❤️❤️
One question-Though it works correctly, but how, just comparing the consecutive costs for m and m+1 guarantees that cost is going to increase towards the direction where cost(by making every element equal to m+1)>cost(by making every element equal to m) for entire domain? ugh, like what if for m-1 and m+1 both, the cost decreases..
I had the same doubt
8:54 I think ye greedy approach le rhe. But what is the proof? We need to minimise the cost not steps so how to prove this conclusion?
In context of the brute force approach
how did you came to conclusion that to get minimum cost you need to make it equal to the element already present in tha array?
can the equal element be equal to some other value not present in the array which may give minimum cost?
Good Qn.
If you notice, if you make all elements equal to a value which is not in array say x, then ALL element conversion will cost me an amount > 0 , because no element in nums is equal to x.
However, if we equate all elements to a value say y which is present in nums, then for atleast that value, the cost will be 0.
So, there is no point in taking a value x which is not in nums.
@@codestorywithMIK okk thanks
@@codestorywithMIK But still you can't comment on the overall cost, because only for that element cost is zero , for others it might me more.
Tysm just watched the intution and codeed up with my own :-
here is my implementation :-
typedef long long ll;
ll ans;
ll findcost(int mid ,vector& arr , vector& cost )
{
ll currcost = 0;
for(int i =0 ; i < arr.size();i++)
{
ll diff = abs(mid-arr[i]);
currcost += (diff*cost[i]);
}
return currcost;
}
long long minCost(vector& arr, vector& cost) {
//creating the search space
int low = *min_element(arr.begin(),arr.end());
int high = *max_element(arr.begin(),arr.end());
while(low midcost) //left side is good
high = mid-1;
else
low = mid+1;
}
return ans;
}
Awesome.
So glad to hear this ❤️❤️❤️
JAVA IMPLEMENTATION
class Solution {
public long minCost(int[] nums, int[] cost) {
int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
for(int x:nums){
min=Math.min(min,x);
max=Math.max(max,x);
}
int l=min,r=max;
long ans=Integer.MAX_VALUE;
while(l costForMid){
r=mid-1;
}else{
l=mid+1;
}
}
return ans==Integer.MAX_VALUE ? 0 : ans;
}
public long findCost(int mid,int[]nums,int[]cost){
long res=0L;
for (int i = 0; i < nums.length; i++) {
// int diff=Math.abs(mid-nums[i]);
// res+=(long)diff*cost[i];
res+=(long)Math.abs(mid-nums[i])*cost[i];
}
return res;
}
}
Thank you for sharing JAVA code ❤️❤️
Thanks bro but little bit confusing
Important consideration here, why we can apply BS search and How can sure by checking mid+1 , we can neglect that half. The important thing we should check whenever we are applying BS is, what is the behaviour of search space. Here the search space from left to right is decreasing , local minimum and then increasing(& vice versa). We are just trying to find local min here. Since there is only single local min , hence we can arrive at a solution. If there is multiple local min we wont be able to apply binary search.
Awesome. Do you know what is the proof that there will be always one minima?
Great explanation as always,only one question can this question be done using dp i tried doing it but cant think of the approach
in the binary search approach we generally try to reject one half and go another half .
can we reject one half on the basis of just one comparison ?
Does this inutition and solution will work on all questions of this pattern ?
u made a hard question so easy
Thank you so much ❤️❤️❤️
It's amazing 🤩, can you also post video using prefix sum .
thank you bhaiya
Thank you for watching 😇
I think the last statement "answer == INT_MAX ? 0 : answer" is not needed since we have already declared answer to be max, and the cost will come out to be 0 if all the elements are equal which will make our answer = 0.
Correct me if I'm wrong.
We can simply return "answer" is what I'm saying.
Yup
yess you are right
Basically this code assumes that all the test cases will be having unimodal graph but it might be the case that some test case has two minima , then it wont work correctly
thanks for the explanation, can we solve this question using DP asking because i thought this was dp question.
Without You I would've skipped this question.
❤️❤️❤️
L.E.G.E.N.D
The unsung HERO
Please explain where I am wrong ....class Solution {
public:
long long minCost(vector& nums, vector& cost) {
long long ans=0;
unordered_map mp;
for(int i=0;i max_cost){
max_cost = pair.second;
req_key = pair.first;
}
}
for(auto& p : mp){
if(p.first != req_key){
long long sec =p.second;
ans+= abs(p.first - req_key)*sec;
}
}
return ans;
}
};
Thanks .
bhaiya kya guarantee hain maan lo mid+1 greater aa raha h agar mid + 2 less than aa raha ho toh kya kare ge plz explain bhaiya this onle very confused
Bhai ase problem single maxima ya minima hota hai dry run karke dekh lo ho sake to ternary search padh lena
if mid+1 is coming large,
Then obviously mid+2 will be even larger. Take any test case and dry run will help clear the doubt for sure
@@codestorywithMIK Dont you think cost might change the answer.
You can refer to the question "Find peak element".Here exactly the same approach is followed,hope it helps
@@CodeFal exactly my point
Why we are only checking mid+1 value I didn't understood that?
Either way, it doesn't matter
If you check for mid - 1 instead then the if else statements will get swapped that's it
@@sinnohperson8813 thanks
you are making direct assumption that its not worth going to right if we get cost > cost at mid sir.
can u prove that cost function is convex function ?
how will i explain this assumption in interview ?
great explanation. please make a video on below Question, no explanation is available:
Determine the minimal adjustment cost of an array
Write an algorithm to replace each element in an array of positive integers such that the difference between adjacent elements in the array is less than or equal to a given target. The goal is to minimize the adjustment cost, which is the sum of differences between new and old values.
In other words, minimize ∑|A[i] - Anew[i]|, where 0
brother dp playlist mai video daal do please
One video came today. ua-cam.com/video/oeYLF-u2DIA/v-deo.html
More coming this week ❤️
Again Hard made easy 🔥
🔥🔥🔥
Thank you 😊
But iska proof kya hai, ki agar cost(mid)
if you try to check no of operation for all the values from (0 to MAX_VALUE ) you will see the values will first decrease and than increase inshort the graph will be in V shape and you can apply the binary search to find the minimum value nad he already explained with some test cases at 5:00 timestamp
@@AnandKumar-kz3ls Any link bro?
Utube doesn't allow to post a link here. go to desmos (it creates graph) and then write the expression 2.\left|1-x
ight|+3.\left|3-x
ight|\ +1.\left|5-x
ight|+14.\left|2-x
ight| and create a table you will be able to visualize.
@@girikgarg8 let say y= ci * | Ni - x | where ci is the cost of the ith index Ni is the ith element and x is the val which we need to found here y = ci * | Ni - x | is a convex function so sum ( ci * | Ni - x | ) will also be convex there is also a proof which you can google it
This solution is not working now It's giving Integer overflow even after using long long in C++
❤
I first though this was a DP question T_T
ɥɐllɐɥsɐɯ
❤️❤️