← Goldman Sachs questions

Max Stack using one stack

Filed under Goldman Sachs

Free read 2 of 3

Confirm that the interviewer specifically requires optimizing space down to one stack instead of the standard auxiliary max stack approach.

The question

Implement a stack that supports push, pop, top, and retrieving the maximum element in constant time, using only one underlying stack to optimize space.

Constraints

  • All operations (`push`, `pop`, `top`, `getMax`) must run in $O(1)$ time complexity.
  • Must use only one underlying stack data structure.

Examples

Input
operations: push(-2), push(0), push(-3), getMax(), pop(), top(), getMax()
Output
[-3, 0, -2]
Why
Max tracks the current maximum value efficiently using a single stack encoding strategy.

Approach

  1. Confirm that the interviewer specifically requires optimizing space down to one stack instead of the standard auxiliary max stack approach.

Solution

O(1) time for all operations, O(N) space

Python
class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_val = None

    def push(self, val: int):
        if not self.stack:
            self.stack.append(val)
            self.max_val = val
        elif val < self.max_val:
            self.stack.append(val)
        else:
            self.stack.append(2 * val - self.max_val)
            self.max_val = val

    def pop(self):
        if not self.stack:
            return
        top = self.stack.pop()
        if top > self.max_val:
            self.max_val = 2 * self.max_val - top

    def top(self) -> int:
        t = self.stack[-1]
        return self.max_val if t > self.max_val else t

    def getMax(self) -> int:
        return self.max_val

Tips

  • What they are testing: Test with strictly increasing and decreasing sequences of numbers to ensure the maximum tracking mechanism handles updates correctly.
  • Common mistake: When pushing a new maximum, forgetting to store the previous maximum so that it can be restored when the current maximum is popped.

Related Goldman Sachs questions

Collected from public candidate posts and coding forums. Updated Nov 2026.