Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Min Stack

Medium · Stack & Queue · Asked at Amazon, Microsoft, Google, Bloomberg

Design a stack that supports push x, pop, top and getMin, each in O(1). Process the operations and print the result of every top and getMin. All pop, top and getMin operations are done on a non-empty stack.

Input

First line: q. Next q lines: one operation each.

Output

One line for every top or getMin operation.

Constraints

Keep a second stack (or store pairs) with the minimum so far.

Example 1

Input

6
push -2
push 0
push -3
getMin
pop
getMin

Output

-3
-2

Example 2

Input

3
push 5
top
getMin

Output

5
5

Hints

  1. Scanning the stack for the minimum is O(n) per query.
  2. Store, next to every value, the minimum of the stack at the moment it was pushed. getMin is then just the top's stored minimum.

Approach

Each stack entry is a pair (value, minSoFar), where minSoFar = min(value, previous top's minSoFar). A pop removes the pair, so the minimum below it comes back automatically. All four operations are O(1). Read the operations as words, and print the results for top and getMin together at the end.

Complexity: O(1) per operation · O(q) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<pair<long long, long long>> st;  // (value, min so far)
    while (q--) {
        string op;
        cin >> op;
        if (op == "push") {
            long long x;
            cin >> x;
            long long m = st.empty() ? x : min(x, st.back().second);
            st.push_back({x, m});
        } else if (op == "pop") {
            st.pop_back();
        } else if (op == "top") {
            cout << st.back().first << "\n";
        } else {
            cout << st.back().second << "\n";
        }
    }
    return 0;
}

Python solution

import sys

tokens = sys.stdin.read().split()
q = int(tokens[0])
stack, out, pos = [], [], 1  # stack holds (value, min so far)
for _ in range(q):
    op = tokens[pos]
    pos += 1
    if op == "push":
        x = int(tokens[pos])
        pos += 1
        stack.append((x, min(x, stack[-1][1]) if stack else x))
    elif op == "pop":
        stack.pop()
    elif op == "top":
        out.append(stack[-1][0])
    else:
        out.append(stack[-1][1])
print("\n".join(map(str, out)))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine().trim());
        long[] vals = new long[q], mins = new long[q];  // (value, min so far)
        int size = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            if (op.equals("push")) {
                long x = Long.parseLong(st.nextToken());
                vals[size] = x;
                mins[size] = size == 0 ? x : Math.min(x, mins[size - 1]);
                size++;
            } else if (op.equals("pop")) {
                size--;
            } else if (op.equals("top")) {
                sb.append(vals[size - 1]).append('\n');
            } else {
                sb.append(mins[size - 1]).append('\n');
            }
        }
        System.out.print(sb);
    }
}

Solve Min Stack online · All practice problems