Leetcode Amazon Interview Questions

Min Stack

Leetcode - No. 155

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.
1
2
3
4
5
6
7
8
9
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Min Satck

Problem Analysis

Keep the order and keep tracking the min elelment in this stack.

Algorithm Analysis

Solution1: Used a list with a topIndex pointer and find the min in O(n) time.

  • pop(): O(N) - Sometimes, we need to update the current min by looking through the list.
  • push(): O(1) - Add element into the list and update the current min.
  • top(): O(1) - return the element pointed by topIndex.
  • getMin(): O(1) - return min.

Solution2: Used a LinkedList. In each Node, we recored the current Min. Everytimes, when we push a node, compare its value with the head node.

  • pop(): O(1) - remove the head node.
  • push(): O(1) - Add element into the head node and update the curMin
  • top(): O(1) - return a head node
  • getMin(): O(1) - return a curMin recorded in head node.

Solution3: Used two Stacks - normal stack and min stack. One stack record the order and another stack only record the element that has been min.

  • pop(): O(1) - If the popped element is min, pop the top element in the minStack.
  • push(): O(1) - If the added element is smaller then min, update both stack.
  • top(): O(1) - return peek in normal stack
  • getMin(): O(1) - return peek in min stack

Solution4:Used one Stack.

  • pop(): O(1) - pop out the top, if it’s value equal to min, pop it second times
  • push(): O(1) - If the element is min, push it twice into the stack and check the min
  • top(): O(1) - return top
  • getMin(): O(1) - return min

Code Implementation - List with O(N) time to find the min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MinStack {
    int topIndex;
    int min;
    List<Integer> stack;
    
    /** initialize your data structure here. */
    public MinStack() {
        topIndex = -1;
        min = Integer.MAX_VALUE;
        stack = new ArrayList<>();
    }
    
    public void push(int x) {
        if(x < min) {
            min = x;
        }
        stack.add(x);
        topIndex++;
    }
    
    public void pop() {
        int poped = stack.get(topIndex);
        stack.remove(topIndex --);

        if(poped == min) {
            min = Integer.MAX_VALUE;
            /* Find new min */
            for(int i = 0; i <= topIndex; i++) {
                min = Math.min(min, stack.get(i));
            }
        }
        
    }
    
    public int top() {
        return stack.get(topIndex);
    }
    
    public int getMin() {
        return min;
    }
}

Code Implementation - Linked List (All O(1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class MinStack {
    
    private Node head;

    /** initialize your data structure here. */
    public MinStack() {
        /* no need to do anything when constructing */
    }
    
    public void push(int x) {
        if(head == null) {
            head = new Node(x, x);
        } else {
            Node newNode = new Node(x, Math.min(x, head.curMin));
            newNode.next = head;
            head = newNode;
        }
    }
    
    public void pop() {
        if(head != null) {
            head = head.next;
        }
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.curMin;
    }
}

class Node {
    int val;
    int curMin;
    Node next;
    public Node(int val, int curMin) {
        this.val = val;
        this.curMin = curMin;
    }
}

Code Implementation - Two Stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MinStack {

    private Deque<Integer> stack1;
    private Deque<Integer> stack2;
    
    
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }
    
    public void push(int x) {
        stack1.offerFirst(x);
        if(stack2.isEmpty() || x <= getMin()) stack2.offerFirst(x);
    }
    
    public void pop() {
        if(top() == getMin()) stack2.pollFirst();
        stack1.pollFirst();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int getMin() {
        return stack2.peek();
    }
}

Code Implementation - One Stack (Push min twice)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack {
    int min;
    Deque<Integer> stack;
    
    public MinStack() {
        min = Integer.MAX_VALUE;
        stack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.offerFirst(min);
            min = x;
        }
        stack.offerFirst(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pollFirst() == min) min = stack.pollFirst();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

徐維謙ya


FEATURED TAGS
Leetcode Amazon Interview Questions