4 ms·

Find the minimum value in the stack in O(1) both time and space complexity.

glandium 10y ago
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.
- antoaravinth 10y ago
  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-getmin-in-o1-time-and-o1-extra-space/ http://www.geeksforgeeks.org/design-a-stack-that-supports-ge...
wadeboggs 10y ago
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?
- sand500 10y ago
  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?
- antoaravinth 10y ago
  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).
daysforbeef 10y ago
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?
deleted 10y ago
[deleted]
api_or_ipa 10y ago
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]
balamaci 10y ago
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.

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.

antoaravinth 10y ago
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-getmin-in-o1-time-and-o1-extra-space/ http://www.geeksforgeeks.org/design-a-stack-that-supports-ge...

wadeboggs 10y ago

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?

sand500 10y ago
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?
antoaravinth 10y ago
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).

daysforbeef 10y ago

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?

deleted 10y ago

[deleted]

api_or_ipa 10y ago

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]

balamaci 10y ago

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.