I have a novel solution: use a delta ~~queue~~ stack! Instead of pushing straight numbers, push the delta of each new value against the next smaller value currently in the stack. Sadly I can't find a resource for this data structure. I learned about it in university when writing a sleep() function for an OS I was writing. On each tick, you simply decrement the first value (or pop it if it's 0).

[]

push(1) : [1]

push(2) : [1,1]

push(3) : [1,1,1]

push(3) : [1,1,1,0]

pop() : 3, [1,1,1]

pop() : 3, [1,1]

pop() : 2, [1]

pop() : 1 [0]

Have a few questions .. (1) doesn't it seem like this only works for elements that have an ordering as well a binary operation multiplication, subtraction and addition defined on them, making it too specific ? (I'm talking about the whole 2x - minelement) (2) If I have a variable hanging around a stack, is it still a stack? (3) When I pop out the min value in the stack, and want the next min Value, how do I get that,? seems like the previous min value still sticks around? (4) With comparisons and 1 value that hols state, do I really need to transform the values going into the stack?

Do you mean "design a stack where you can find the minimum value in O(1) both time and space complexity"? Because I don't see how you can do O(1) with an arbitrary stack.

Yes thats right, you can come up with any solution. But make sure O(1) is satisfied (both in time and space complexity).

Anyways I had failed to give proper answer and I was rejected in the interview. This was the last question of my last round!

Spoiler: Here is one such solution using a simple but very clever trick: http://www.geeksforgeeks.org/design-a-stack-that-supports-ge...

What field of programming have you implemented that? I'm curios, is it in kernel development, some DB design. Not trolling, just curios where that usecase where this would come in handy and why ask it if it's not a direct relation to what you are doing.

Make another stack with the latest minimum, then when you pop that top value, you also pop it off the minimums stack. Then you have the last minimum before that one.

Is that it?

What if you added values that are greater then the minimum at the top of the minimum stack but less than the next value on the minimum stack?

Your using two stacks now. This is the solution that I had told but your not satisfying the condition w.r.t to space , its O(n) not O(1).