in deletion proof why current element is equal to x and get cancelled?
Doubt in proof of deletion
@kingshuk441
hey are you talking about the equation
2*current_min -y
First thing, we are updating our current_min while inserting whenever we get a number smaller than current_min, suppose x < current_min, now we are not inserting x, into the stack, we are inserting 2*x-current_min
Now let the number 2*x-current_min = a, a <x as proved in video, now we update current_min=x(a is smaller than current_min).
Now suppose no further updation is done to current_min(all element inserted are greater than x or current_min from this point onwards).
Now we start deleting, we will simply remove all the elements greater than current_min as they are not affecting it.
When we get an element smaller than current_min it means we are at point where current_min was updated. Now we must get back our previous min element, we also know that when the current min was updated, we did not simply insert the element into stack we first performed transformation (2*x1-current_min1 (our a)).
and latter made current_min=x1,(x1 is the element to be inserted and current_min1 was the min element that time, now current_min1 is previous_min) now to get back that previous min, we will current_min=**2current_min - a).
2current_min - (2x1-current_min1)
now we also know that x1= current_min
so
2x1 - 2*x1 + current_min1
current_min1
and current_min1 is nothing but previous min element.
I would suggest that you try to perform these operation on pen and paper using some variables , you will better understand the concept.
If this resolves your doubt mark it as resolved.
