Solution: Shrinking at a Quarter Full

An add that calls grow leaves the array one element above half full, so one removeLast reaches the half-empty shrink threshold. No cheap calls happen between the two resizes. The fix is to move the shrink threshold to a smaller fraction of the capacity, so that a freshly grown array is many removes away from shrinking.

Let’s shrink only when the array is a quarter full. Introduce a new constant, SHRINK_THRESHOLD = 4, to control when shrinking happens.

private static final int SHRINK_THRESHOLD = 4;

In removeLast, change the threshold from arr.length / RESIZE_FACTOR to arr.length / SHRINK_THRESHOLD.

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 / SHRINK_THRESHOLD && arr.length > MIN_CAPACITY) {
    shrink();
  }
  return value;
}

Inside shrink, the new array still has arr.length / RESIZE_FACTOR slots.

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

With this change, shrink fires at a quarter full, but still halves the capacity. For example, an array with $32$ slots shrinks when the size falls to $8$, and $8$ elements in the new $16$ slots is half full.

Immediately after grow returns, the array is half full, but add still has to insert the new element. The completed add leaves it one element above half full. A removeLast that calls shrink leaves it half full. So after either resizing operation finishes, the array is approximately half full, and the count of cheap calls starts over from there.

Take the array we just shrank: it has $8$ elements and $16$ slots. What would make it resize again?

• If we keep adding, the first $8$ adds fill the unused slots. The ninth add grows the array. That gives us $8$ cheap calls before an expensive one.
• If we keep removing, the size drops to $7$, then $6$, then $5$, then $4$. The fourth remove shrinks the capacity from $16$ to $8$. That gives us $3$ cheap calls before an expensive one.

Mixing adds and removes only increases the number of cheap calls before the next resize. If we are filling the array, a remove undoes an add. If we are emptying it, an add undoes a remove.

The same idea works for larger arrays. A larger array costs more to resize, but it also takes more adds or removes to reach the next resize. Doubling the capacity roughly doubles both the resize work and the number of cheap calls before it. So we still have enough cheap calls to spread out the cost of the expensive one.

There is nothing special about a quarter. Any fixed positive fraction strictly below one-half works as the shrink threshold. The gap between the size after a resizing operation and the next grow or shrink threshold then grows with the capacity, so there are enough cheap calls to pay for the next resize. That is the same lesson as the growth factor. For grow, the factor has to be a fixed constant greater than $1$, and $2$ is just a convenient choice. A quarter is just a convenient choice for the shrink threshold in the same way.