13:14 So now what I have understood we know the usual answer is, In a sorted array, difference between (first element+k ) and (last element -k), is maximum adding k and subtracting k is the only way we can bring them closer and thus minimise the difference between them, which is the maximum difference. But in cases where K is in order of elements and adding or subtracting K, changes the sorted order, and largest no longer remain largest, and smallest no longer the smallest, then we have to find the correct largest and smallest element. we keep them in mi, and ma, they are so far seen smallest(non-negative) and largest values and also, we always can either add k or subtract k from a number, so we try both on arr[i] and collect smallest and largest, one thing that would come in our mind is what if adding k and subtracting k on same element both worked and become a part of the answer and we can only do only one operation. Then we can surely say it won't happen, because if an element subtract by k, is smaller than the smallest element, then definitely it cannot become larger than largest element, only possible for arr[n-1] which is considered in largest. and using [i+1] saves an iteration. as arr[0]-k is already equal to smallest so avoided. and i going max to n-2, avoids calculating arr[i-1]+k, which is already considered in largest Now it got more clear after writing an explanation. Hope this helps someone too.
Can you explain? you are taking arr[0]+k as the smallest....fine.. But in loop you are doing arr[i+1]-k to find minimum Whyy? You said you want to minimise the difference which will happen only when we add k to min So in loop also you should increment a[i+1]+k ...like you did for smallest
@@parrotsparadise3914 See this example from GFG Input : arr[] = {1, 10, 14, 14, 14, 15} k = 6 Output: Maximum difference is 5 arr[] = {7, 4, 8, 8, 8, 9} here minimum element is 4 4 and 9 are actually obtained by subtracting K that technique is directly valid on normal case (where k is small) but there can be more cases, and the logic inside loop deal with it smartly It deserves some thinking,and you are smart enough to do that,maybe start from the base. even I am having trouble right now explaining it really well, but i will think about it tomorrow.🤣 Check sKSama's minimise the height II video, he explains using numberlines
THIS is the correct code passes all the test cases. sort(arr,arr+n); int ans=arr[n-1]-arr[0]; int largest=arr[n-1]-k; int smallest=arr[0]+k; int mi,ma; for(int i=1;i
If we have a small tower (let say of height = 4 ) and a large tower (height = 6) and we increase the height of small tower and decrease height of large tower (k=3) then smallTowerHeight = 7 and largeTowerHeight = 3 so smaller tower becomes greater than larger tower after the operation.
Mast explanation bro. I mean i am new to competitive. And i was solving dsa 450, and i got code through comments. Tried learning myself, I didn't understand...... but this explanation is beautiful.
@@techskeletons7381 you are taking arr[0]+k as the smallest....fine.. But in loop you are doing arr[i]-k to find minimum Whyy?? You said you want to minimise the difference So in loop also you should increment min...
It's because the code is sorted and initial the first tower will be lowest and last one would be highest so initial ans would be last-first [they are only largest and smallest] tower after sorting
Thanks for explaining each line of code in detail! But I want to give a small correction for "if(mi < 0) continue;" line. Instead of saying it as "increasing the difference" we may say that as mi shouldn't be less than 0 as "smallest" is always > 0 and "arr[i+1] - k" is >=0 as k shouldn't be subtracted from the element if it results in a negative number(As stated in the question).
Hello, is it logically correct to calculate the average of the array values . Than iterate through the array and check : If the value is bigger than the average we check if we substrat k from it it becomes closer to the average value if not we do nothing. And we do the same if the value is bigger than the average (but by adding k) Than we print max-min
9:58 📢📢🙋♂️suppose the heights are 3,4,5 and k=2, so a/c to the algo smallest= 3+2= 5 and largest = 5-2=3, but how it this possible. smallest>largest ??????????
In this question, We DON'T have to minimise the difference between heights!! We have to minimise the maximum difference between the heights! There's a difference guyss!! And he also explained the point wrong. At 13:30
you don't actually need the continue statement. if you subtract a negative value from a positive value then it'll always give you a positive value itself and then you can check it with current min difference so current min will in any case be less
It's wrong explaination! In video it is explained that min difference would be in the adjacent element, which is wrong. Had the elements been 3,4,9, instead of 3,9, etc, the min difference would be in the 1st and 3rd element!
This solution makes no sense to me, I can't understand why consecutive values are being considered when the question clearly says that we need to compare smallest and the largest tower, what is the guarantee that smallest tower and largest tower is always consecutive (after sorting, increment and decrement)?
Hey Bro... We cannot make it 0 because we, in our code taking min of arr with current value in a particular iteration Moreover... the min possible value of k is 0 So what will be the ans when k = 0 it will be arr[n-1] - arr[0]
I too regret that i did not dry dun the code.... See in this problem we need minimise the maximum difference between the tower heights so what i am doing is to take each tower increase its height by k and assume it to be the largest so far so that i can check its difference with my current smallest tower and if that difference is minimum so far i update the variable storing the final answer. At the end of the code we actually get the largest tower height in ma and smallest tower height in mi and ma-mi gives the minimised max difference of tower heights... Please read this again if you cant get it... *sorry for late reply*
I am using std::min and std::max functions predefined in the header file "algorithm" in c++ min(x,y) returns the min of x and y max(x,y) returns the max of x and y Also you could have done this if you dont wanna use the predefined methods : if(smallest
Can you explain me? you are taking arr[0]+k as the smallest....fine.. But in loop you are doing arr[i]-k to find minimum Whyy?? You said you want to minimise the difference So in loop also you should increment min...
yeah everything is right but i have a doubt since int the gfg it is said it is compulsory to perform a +k or -k then why we are not initializing it wit int_max morover it will also not pass the test case in gfg so its a huge bug in question
Can u give one example when there is a case that largest and smallest part in you code ..do not give minimum value?... Then what are those value which give min diff on adding or subtracting k, other than doing same with first and last element?
What if the elements are 3 4 12 16 17 And k = 5 Then smallest will be 3+5 =8 And 4 will be skipped bcoz 4-5 will be negative Hence the minimum number will remain 8
The minimum will not remain 8 my friend... The ans for this particular output is 5 and my code also giving this output. Please watch the video again and undertsand.
Let me clear one more thing... We always take minimum of (smallest and arr[i+1]-k) and these two things never become negative because in my code i continue to next iteration as soon as mi becomes less than 0
Yes thats what we need... 4 will never... i repeat... never participate in the pair that gives minimum max difference if we subtract 5 from it! Its very logical!
Because we are taking arr[i+1] and hence it will go to last index Also we will run out of bounds and it will throw an error when i is at last and we try to access arr[i+1]
See in this problem we need minimise the maximum difference between the tower heights so what i am doing is to take each tower increase its height by k and assume it to be the largest so far so that i can check its difference with my current smallest tower and if that difference is minimum so far i update the variable storing the final answer. At the end of the code we actually get the largest tower height in ma and smallest tower height in mi and ma-mi gives the minimised max difference of tower heights... Please read this again if you cant get it... *sorry for late reply*
@@techskeletons7381 hey! Actually the point where i am stuck is..(11:21).you said we compare the first or previous element with the largest one and the second or the next element with the smallest one.....but as acc to me and also acc to from (8:01) the (previous or the first one will be the small one so we should compare it with the SMALLEST) and ( the next or the second one in those two consecutive elements should be compared with the LARGEST one so that we get the optimized max and min element in each iteration ) soo..you see i am just understanding it in opposite direction...and i need some help...
Thanks for coming back to us... Actually whenever we increase the height of a tower we assume it to be the new largest (as it will approach more close to max) and hence we compare it with max or largest tower. Similarly when we decrease height of i+1th tower we assume it to be smallest tower and we compare it with mi. Also you see this that after sorting we are iterating over the tower heights in for loop and in every next iteration the tower whose height was increased in previous iteration is now decreased in next iteration so we are actually increasing and decreasing the heights of each tower and then comparing them with mi and ma and update the ans accordingly.
Lets assume the heights are 1,4,7 and k =4 Now you cannot decrease the height of tower of height 1 as it will become negative moreover i already explained in the video why we should increase the height of smallest tower and decrease the height of tallest tower... please watch the video again...
I am done with my studies and recently joined a product based company, and i did code that by myself! Practice dsa and solve problems regularly, you will also develop skills to code such solutions. All the best!
I have a doubt how can you calculate ans in each iteration bcz ma & mi are max & min elements seen so far in arr till index i ,but the ques says min diff between max & min of complete array.
Most of the problems are based on some pattern or some specific concept, keep practicing you wont get initially but once you keep practicing you will get it
13:14 So now what I have understood
we know the usual answer is, In a sorted array, difference between (first element+k ) and (last element -k), is maximum
adding k and subtracting k is the only way we can bring them closer and thus minimise the difference between them, which is the maximum difference.
But in cases where K is in order of elements and adding or subtracting K, changes the sorted order, and largest no longer remain largest, and smallest no longer the smallest, then we have to find the correct largest and smallest element.
we keep them in mi, and ma, they are so far seen smallest(non-negative) and largest values
and also, we always can either add k or subtract k from a number, so we try both on arr[i] and collect smallest and largest,
one thing that would come in our mind is what if adding k and subtracting k on same element both worked and become a part of the answer and we can only do only one operation.
Then we can surely say it won't happen, because if an element subtract by k, is smaller than the smallest element, then definitely it cannot become larger than largest element, only possible for arr[n-1] which is considered in largest.
and using [i+1] saves an iteration.
as arr[0]-k is already equal to smallest so avoided.
and i going max to n-2, avoids calculating arr[i-1]+k, which is already considered in largest
Now it got more clear after writing an explanation. Hope this helps someone too.
this explanation helped me more than this entire video.🤷♂️😂
Can you explain?
you are taking arr[0]+k as the smallest....fine..
But in loop you are doing arr[i+1]-k
to find minimum
Whyy? You said you want to minimise the difference which will happen only when we add k to min
So in loop also you should increment a[i+1]+k ...like you did for smallest
@@parrotsparadise3914 See this example from GFG
Input : arr[] = {1, 10, 14, 14, 14, 15}
k = 6
Output: Maximum difference is 5
arr[] = {7, 4, 8, 8, 8, 9} here minimum element is 4
4 and 9 are actually obtained by subtracting K
that technique is directly valid on normal case (where k is small)
but there can be more cases, and the logic inside loop deal with it smartly
It deserves some thinking,and you are smart enough to do that,maybe start from the base. even I am having trouble right now explaining it really well, but i will think about it tomorrow.🤣
Check sKSama's minimise the height II video, he explains using numberlines
@@foziezzz1250 Lol thanks anyways!
thanks
It was very difficult to grasp only looking at solution code, You made it easy to understand . Thank you!
best solution.. i was searching for this explanation, thanks for uploading!
Same here
Nice nice
@@manoranjankumarthakur9725 👐
THIS is the correct code passes all the test cases.
sort(arr,arr+n);
int ans=arr[n-1]-arr[0];
int largest=arr[n-1]-k;
int smallest=arr[0]+k;
int mi,ma;
for(int i=1;i
I wasn't able to understand from editorial and other videos so huge thanks to you for clarifying everything brother.
well, It's not everyone's cup of tea to explain something like that. kudos to you brother!
If we have a small tower (let say of height = 4 ) and a large tower (height = 6) and we increase the height of small tower and decrease height of large tower (k=3) then smallTowerHeight = 7 and largeTowerHeight = 3 so smaller tower becomes greater than larger tower after the operation.
i also want to ask that
Mast explanation bro. I mean i am new to competitive. And i was solving dsa 450, and i got code through comments. Tried learning myself, I didn't understand...... but this explanation is beautiful.
Thank You Navnit
Happy Coding!!
@@techskeletons7381 you are taking arr[0]+k as the smallest....fine..
But in loop you are doing arr[i]-k
to find minimum
Whyy?? You said you want to minimise the difference
So in loop also you should increment min...
Explaining each and every code line was really helpful in understanding the approach implementation. Thanks a lot!
Yes Every line explaination was very hellful
Mobile no. ?
My doubt is why you initialise ans=arr[n-1]-arr[0] ; ??
why we cant initialise ans= largest-smallest; ????????????????????????????????????????????
this code is just like mugging up
It's because the code is sorted and initial the first tower will be lowest and last one would be highest so initial ans would be last-first [they are only largest and smallest] tower after sorting
Thanks for explaining each line of code in detail! But I want to give a small correction for "if(mi < 0) continue;" line. Instead of saying it as "increasing the difference" we may say that as mi shouldn't be less than 0 as "smallest" is always > 0 and "arr[i+1] - k" is >=0 as k shouldn't be subtracted from the element if it results in a negative number(As stated in the question).
I think the same
Hello, is it logically correct to calculate the average of the array values .
Than iterate through the array and check :
If the value is bigger than the average we check if we substrat k from it it becomes closer to the average value if not we do nothing.
And we do the same if the value is bigger than the average (but by adding k)
Than we print max-min
Int diff = arr[n-1] - arr[0]
Yeh isliye kiya to handle a edge case of (arr[n-1] + k ) - (arr[0] + k )
Yeh bhi ek minimum difference ka candidate hai
Are you sure about this?
@@techskeletons7381 yesss
9:58 📢📢🙋♂️suppose the heights are 3,4,5 and k=2, so a/c to the algo smallest= 3+2= 5 and largest = 5-2=3, but how it this possible. smallest>largest ??????????
Thanks a lot for the explanation
nice explanation. you teach how each command has a purpose in this program.
In this question,
We DON'T have to minimise the difference between heights!!
We have to minimise the maximum difference between the heights!
There's a difference guyss!!
And he also explained the point wrong. At 13:30
you don't actually need the continue statement. if you subtract a negative value from a positive value then it'll always give you a positive value itself and then you can check it with current min difference so current min will in any case be less
Keep up the patience you portrayed here, you'll stand out.
It's wrong explaination!
In video it is explained that min difference would be in the adjacent element, which is wrong. Had the elements been 3,4,9, instead of 3,9, etc, the min difference would be in the 1st and 3rd element!
This solution makes no sense to me, I can't understand why consecutive values are being considered when the question clearly says that we need to compare smallest and the largest tower, what is the guarantee that smallest tower and largest tower is always consecutive (after sorting, increment and decrement)?
The question doesn't make sense it seems [ for you ]
AQ my perspective the condation if(mi
great video man but I have one question: why do we have to initialise ans as arr[n-1] - arr[0]? why cant we initialise it as INT_MAX or 0?
Hey Bro... We cannot make it 0 because we, in our code taking min of arr with current value in a particular iteration
Moreover... the min possible value of k is 0
So what will be the ans when k = 0 it will be arr[n-1] - arr[0]
@@techskeletons7381 thanks bro understood 👍
what if arr[n-1]-k
in that case diff will be arr[n-1] - arr[0] no need to increment or decrement any array element
Thanks for the walkthrough buddy.Really helpful
Thank you for the video. It's a good and easy approach.
best solution so far
thank you for the video!!!
Thanks bro finally understood after so many videos..
your knowledge is commendable but the dry run was not good for beginners
Thank you so much bro for easy algorithm and simple explanation
Fucking genius explanation
so need to sort the array... and make it so complex...
Exact explanation of my silly doubt in this question
You rock bro 😎
and what was that doubt...can u tell me
😅
Best solution of this question on You tube 👍👍👍👍 Thanks a lot bro
Great video man, How do you come up with solutions?
Practice!
I salute this code.
Very well explained. Thanks a lot.
Very good explanation I appreciate a lot 🔥
Neatly explained, but I am still stucked at mi and ma inside for loop... Can you please help me by making the code dry run...
I too regret that i did not dry dun the code....
See in this problem we need minimise the maximum difference between the tower heights so what i am doing is to take each tower increase its height by k and assume it to be the largest so far so that i can check its difference with my current smallest tower and if that difference is minimum so far i update the variable storing the final answer.
At the end of the code we actually get the largest tower height in ma and smallest tower height in mi and ma-mi gives the minimised max difference of tower heights...
Please read this again if you cant get it...
*sorry for late reply*
Thanks for the amazing explanation...
why we are not talking about the case when k is greater than maxValueInArray
I'm felling like I'm dumb, and this is only considered a easy to medium difficulty problem 🙃
omg finally understood this problem thankuu😄
Great explaination bro keep it up
Thank you so much, I was stuck on it for 2 days
Great explained
inside for loop, the first two sentence, mi = min(smallest, arr[i+1]-k); here you are taking i+1 but in next line you just taking i , why ?
Where is the min and max algorithm
I am using std::min and std::max functions predefined in the header file "algorithm" in c++
min(x,y) returns the min of x and y
max(x,y) returns the max of x and y
Also you could have done this if you dont wanna use the predefined methods :
if(smallest
@@techskeletons7381 thank for solving my question❓❓👍👍
Thanks bro for gettng thsi inside my head
Can you explain me?
you are taking arr[0]+k as the smallest....fine..
But in loop you are doing arr[i]-k
to find minimum
Whyy?? You said you want to minimise the difference
So in loop also you should increment min...
yeah everything is right but i have a doubt since int the gfg it is said it is compulsory to perform a +k or -k then why we are not initializing it wit int_max morover it will also not pass the test case in gfg so its a huge bug in question
thanks for explaining so well
Kya bhai is ka answer is se to bhut simple ho Sakta tha dikkat ye thi k aapne is algorithm ko dekh kr solution dunda
Can u give one example when there is a case that largest and smallest part in you code ..do not give minimum value?...
Then what are those value which give min diff on adding or subtracting k, other than doing same with first and last element?
Thank you bro,it finally worked .
👍
ok
Gem 🤩
What an awesome explanation. Thanks a ton man.
Jeegs
Elaborative explanation great!
🙏Thanks for Great Explanation
What if the elements are 3 4 12 16 17
And k = 5
Then smallest will be 3+5 =8
And 4 will be skipped bcoz 4-5 will be negative Hence the minimum number will remain 8
The minimum will not remain 8 my friend...
The ans for this particular output is 5 and my code also giving this output.
Please watch the video again and undertsand.
Let me clear one more thing...
We always take minimum of (smallest and arr[i+1]-k) and these two things never become negative because in my code i continue to next iteration as soon as mi becomes less than 0
@@techskeletons7381 that’s what i am saying
Won’t 4 be skipped that way
Yes thats what we need... 4 will never... i repeat... never participate in the pair that gives minimum max difference if we subtract 5 from it!
Its very logical!
It will participate only when we add 5 to it but not when we subtract 5 from it
Great explaination
Go for it ..you explain well
He hasn't explained anything just justifying the code but not intuition.
Gjb explanation
thank you soo much bro...
great soln. 👏👏
why is the loop form 0 to n-1 instead of 0 to n ???
Because we are taking arr[i+1] and hence it will go to last index
Also we will run out of bounds and it will throw an error when i is at last and we try to access arr[i+1]
@@techskeletons7381 thanks a lot .❤️
Sir,what is it's time complexity??
@@softwarehacks6604 o(n)
You are great bro👍
Thankyou brother
Great explanation , what's the answer of the array which u took ?
thanks bro keep makin such videos
Best solution
Excellent explanation!
I understand the whole part but the min and Max part in for loop, I don't get it please can you explain this
i am finding new candidates so that i get a new minimized max difference
if you are still confused please watch the video again as I explained it!
nicely explained..🙏🙏
Great Explanation
Genius bro
At 11:23 I'm not able to get current largest case and where you are comparing
ma = max(largest, arr[i]+k);
Please help.
+1
See in this problem we need minimise the maximum difference between the tower heights so what i am doing is to take each tower increase its height by k and assume it to be the largest so far so that i can check its difference with my current smallest tower and if that difference is minimum so far i update the variable storing the final answer.
At the end of the code we actually get the largest tower height in ma and smallest tower height in mi and ma-mi gives the minimised max difference of tower heights...
Please read this again if you cant get it...
*sorry for late reply*
@@techskeletons7381 hey! Actually the point where i am stuck is..(11:21).you said we compare the first or previous element with the largest one and the second or the next element with the smallest one.....but as acc to me and also acc to from (8:01) the (previous or the first one will be the small one so we should compare it with the SMALLEST) and ( the next or the second one in those two consecutive elements should be compared with the LARGEST one so that we get the optimized max and min element in each iteration ) soo..you see i am just understanding it in opposite direction...and i need some help...
Thanks for coming back to us...
Actually whenever we increase the height of a tower we assume it to be the new largest (as it will approach more close to max) and hence we compare it with max or largest tower.
Similarly when we decrease height of i+1th tower we assume it to be smallest tower and we compare it with mi.
Also you see this that after sorting we are iterating over the tower heights in for loop and in every next iteration the tower whose height was increased in previous iteration is now decreased in next iteration so we are actually increasing and decreasing the heights of each tower and then comparing them with mi and ma and update the ans accordingly.
Why do we start mi = min(smallest,arr[i+1]-k) there's a possibility that arr[0]-k is the smallest element
Lets assume the heights are 1,4,7 and k =4
Now you cannot decrease the height of tower of height 1 as it will become negative moreover i already explained in the video why we should increase the height of smallest tower and decrease the height of tallest tower... please watch the video again...
Btw for this particular example the ans is 2 (when we modify the array to 6 1 3)
Nice ❤️
Recursive solution for this?
hey brother can you tell me where are you currently doing in studies
and did you code this by yourself
I am done with my studies and recently joined a product based company, and i did code that by myself!
Practice dsa and solve problems regularly, you will also develop skills to code such solutions.
All the best!
understood
I have a doubt how can you calculate ans in each iteration bcz ma & mi are max & min elements seen so far in arr till index i ,but the ques says min diff between max & min of complete array.
I am getting wrong output.
My array is {1,5,10} and k is 6.
The min difference should be 3 but i am getting 7
Check again your code.
Its giving 3 only!
@@techskeletons7381 it's giving me 7 only except when i am doing ans=largest-smallest;
Then i am getting - 3
can soomeone explain how the bruteforce complexity is 2^n ?
why are you subtracting k in mi = min(smallest,arr[i+1]-k) while adding k in smallest?
Because when we subtract k it will become a new candidate for next min and hence we are comparing with smallest
Awesome buddy
Thanks Bhai ❤
Sort esi hi likhte hai...
Sahi hai tu
apni practice maintain krne ke liye aap english me zoor lagare ho otherwise hindi me 100x jyada ache se smjh aaega
There are so many who dont understand hindi
@@techskeletons7381 arey sir 😂,India hai
9/10 coder in India understands Hindi comfortably
Tamil Telugu Kannada, so 9/10, no bro
Thankyou bhai per aise soch kse lete ho
Practice
@@techskeletons7381 bhaiya khub se khub bruetforce soch paaga optimal kse sochu pls btao aaj ss aapki videos dekhuga helpful LG rhi♥️🙏🏻
Most of the problems are based on some pattern or some specific concept, keep practicing you wont get initially but once you keep practicing you will get it
Code is failing for some test cases
Submitting on GFG?
I just checked
Its accepted
All test case passed
I submitted on GFG
Make sure you sorted the array and check all conditions.
K thank you I did some mistakes
Actually ,I'm confused why we're sorting the array
I explained in the video why i sorted the array, kindly watch again!
@@techskeletons7381 I understand ,thanks
bad explanation but 100 marks for your effort
greatt bro
Kuch smjh ni aaya bro
Great in explaining You earned a sub !
Not working for me as of now.!!
kuch samajh nhi aaya