Min Stack

Store history of the minimum

A normal stack loses the previous minimum when its smallest value is popped. Store either pairs (value, minimumSoFar) in one stack or maintain a second stack of running minima. On push of x, pair it with min(x, previousMinimum); on pop, remove the same pair; getMin reads the second field of the current top. Duplicates must be preserved, so do not store only one occurrence of a minimum unless the auxiliary stack records counts or pushes equal minima too.

Make the invariant explicit

After every operation, the top record's minimum equals the smallest value among all elements currently in the primary stack. Push establishes it from the previous top; pop restores the prior record automatically. Thus push, pop, top, and getMin are all O(1) time, using O(n) extra storage. A clever encoded-single-stack variant can reduce stored metadata but risks overflow and is usually less readable. Define behavior for empty top, pop, and getMin according to the API rather than returning a magic value silently. Test duplicate minima, increasing pushes, and popping back through the original minimum.