Stack - Get Minimum element in O(1) operation from Stack

Solution - 1: Using two stacks
- We'll keep on adding the element in Stack - 1 & whenever minimum chnages, we update in stack - 2
- While pop, if popped element is equal to min element, we remove from stack-2 as well
- In case of min element query, we return the peek of stack-2

Time Complexity: O(1)
Space Complexity: O(n)

Solution - 2: Using one stacks
- While pushing, if element is greater than min element, we just push element, if element is less than min value than we push 2 * current element - minValue, so that if min value removed later, we can retrieve the min element.
- While pop, if popped element is greater than min element, then we simply remove element, if it's smaller, we need to update the min element, as this is min element, which we're removing, so we update min element = 2 * current_min_element - popped value
- In case of min element query, we return the min

Time Complexity: O(1)
Space Complexity: O(n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[cherrydaniel]

Nice Logic. can't we use val-minElement as formula, what is purpose of multiplying val with 2.

[surajgrandhi]

amazing, but i have a doubt that in second code we used for loop which means time complexity is O(n) i think.

[shweta-singh]

your proved source code giving me this output two time why? 1 1 3 7 7
1 1 3 7 7