Solution: Shrinking at Half Empty

The obvious rule is the reverse of grow. Since grow doubles when the array is full, shrink should halve when the array is half empty. For this first attempt, shrink when size reaches arr.length / RESIZE_FACTOR, which is half the capacity. Here is removeLast with that rule, and the shrink it calls:

public int removeLast() {
  if (size == 0) {
    throw new IllegalStateException();
  }
  size--;
  int value = arr[size];
  arr[size] = 0;  // clear the now-unused slot
  if (size == arr.length / RESIZE_FACTOR && arr.length > MIN_CAPACITY) {
    shrink();
  }
  return value;
}

// Divides the capacity by RESIZE_FACTOR.
private void shrink() {
  int[] smaller = new int[arr.length / RESIZE_FACTOR];
  for (int i = 0; i < size; i++) {
    smaller[i] = arr[i];
  }
  arr = smaller;
}

removeLast decrements size first and then reads the slot that size now points at, which is the last element. That is add in reverse: add writes the slot and then increments. Clearing the slot afterward is not needed for correctness. It just keeps the unused part of the array at zero, the way grow leaves it.

The arr.length > MIN_CAPACITY guard stops the array from shrinking below its starting capacity. Without it, a long run of removeLast calls would halve the capacity down to $1$. Then arr.length / RESIZE_FACTOR is $0$, so the next shrink allocates an array with no slots, and grow cannot double a capacity of $0$.

A single call has the same cost bounds as add. In the best case there is no shrink, and removeLast does a constant amount of work, so it is $O(1)$. In the worst case it calls shrink, which allocates an array of half the capacity and copies $n$ elements into it, so it is $O(n)$ time and $O(n)$ auxiliary space. With no qualifier, removeLast is $O(n)$. The question is whether amortized analysis brings that down to $O(1)$ the way it did for add.

When we analyzed add, it was the only operation that could resize the array. So studying a sequence of adds covered all the resizing behavior we needed to consider.

Once we introduce shrinking, adds and removes affect each other’s future costs:

• An add can grow the array, putting it close to the shrink threshold.
• A removeLast can shrink the array, putting it close to the growth threshold.

Analyzing only consecutive removes misses that interaction. The half-empty rule is cheap if we only remove. Starting with a full array of $n$ elements and removing all of them, shrinking copies fewer than $n$ elements in total across those $n$ calls. The first shrink copies $n/2$ elements, the next copies $n/4$, and so on:

$$\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots +\frac{n}{2^k}=n\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}\right)<n$$

The $\frac{n}{2^k}$ is MIN_CAPACITY. The expression inside the parentheses is a geometric series where the first term is $1/2$ and the ratio is $1/2$, so it sums to $1-\frac{1}{2^k}$. (Look up “geometric series sum formula” if you want to see why.)

Adding the constant work each removal does on its own, those $n$ removes cost $O(n)$ in total, or $O(1)$ per remove amortized.

The same rule is expensive when we alternate adds and removes, because each operation can trigger another resize. The problem is switching between growth and shrinking, not repeated removal.

Remember what the chapter’s argument for add needed: after each grow, we have a run of cheap add calls, long enough to pay for the next expensive call. So the question is how many cheap calls we get after a grow before the next resize. Take an array with capacity $16$ that is full, and run this sequence of calls:

The first add finds the array full and grows it to $32$, copying $16$ elements. After that grow, the array holds $16$ elements in $32$ slots, exactly half full. One removeLast brings the size to $16$, and $16$ is arr.length / RESIZE_FACTOR, so the array is half empty by our rule and we shrink back to $16$, copying $16$ elements. Now the array is full again, so the next add grows it, and the next removeLast shrinks it.

Every add grows the array, and every remove shrinks it again. Each call copies $16$ elements in this example. With a larger array, each call copies more elements. There are no cheap calls between resizes to spread out that cost.

Keep in mind what the amortized definition requires: a bound on the average cost over any sequence of calls. One bad sequence is enough to break the bound. When a structure resizes in both directions, look for a sequence like that first.