Solution: Evicting on Push

The ArrayMonotonicStack is the same as ArrayStack except for push. We use a backing array and a size field. The pop, top, and isEmpty operations are identical to those in ArrayStack, so we will not repeat them.

Here is the code for push:

public void push(Integer item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  while (size > 0 && arr[size - 1] < item) {
    arr[size - 1] = null;  // evict the top, clearing the slot
    size--;
  }
  if (size == arr.length) {
    grow();
  }
  arr[size] = item;
  size++;
}

Note the comparison is <, not <=, so ties stay on the stack.

Why does this keep the stack in order? When the loop stops, either the stack is empty or the top holds a value greater than or equal to the new item. So the new value is always placed on top of something at least as large as itself. Every element on the stack passed that same test when it was pushed, so from bottom to top the values never increase.

Let’s push(8) with 5 and 3 already on the stack.

┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
          ↑
        size

The loop compares the top to the new item: $3<8$, so 3 is evicted. Its slot is cleared and size drops to 1.

┌───┬───┬───┬───┬───┐
│ 5 │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
      ↑
    size

Now 5 is on top. Again $5<8$, so 5 is evicted too, and the stack is empty.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑
size

With size at 0 the loop stops, and 8 is placed in the first slot.

┌───┬───┬───┬───┬───┐
│ 8 │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
      ↑
    size

What does the new push cost? We already know ArrayStack’s push is amortized $O(1)$: each push places one item, and because the array doubles, the occasional $O(n)$ grow is rare enough that it averages out to a constant per push. ArrayMonotonicStack’s push does everything that ArrayStack’s push does and can also evict items, and the number of evictions is not fixed. So we have to check whether the bound still holds.

Let’s consider the worst case: a push that evicts every item on the stack. That single call does $O(n)$ work. Is it the rare kind, like a grow, which we can spread over many cheap pushes? Or can every push cost $O(n)$?

Push a decreasing sequence, then one larger value:

The last push is $O(n)$. Those four items were placed by four earlier pushes, and each of them was cheap. An item also cannot be evicted twice, because after it is evicted it is no longer on the stack for a later push to find. So the expensive push had to be paid for in advance by cheap ones, which makes it the rare kind of $O(n)$. So push is still amortized $O(1)$.