Leaderboard: add, Phase 3 — Trim

After the insert, the board may hold k + 1 elements. If it does, the lowest score is removed.

dropSmallest, without shifting

In SortedArray, removing an element means shifting everything after it one slot left to close the gap. Removing the smallest element of an ascending array is the worst case for that: index 0, so every remaining element shifts.

Descending storage avoids this entirely. The smallest element is now the last used one, at index size - 1. Removing the last element of an array does not require shifting anything. There is nothing after it, so there is no gap to close:

private void dropSmallest() {
  size--;
  arr[size] = null;
}

add, assembled

The complete add method, with the guard, insert, and trim phases in order:

public void add(T value) {
  if (size == k && value.compareTo(arr[size - 1]) <= 0) {
    return;                    // can't beat the lowest score — doesn't make the cut
  }
  int i = insertionPoint(value);
  for (int j = size; j > i; j--) {
    arr[j] = arr[j - 1];       // shift smaller elements one slot right
  }
  arr[i] = value;
  size++;
  if (size > k) {              // we overshot capacity — the smallest falls off
    dropSmallest();
  }
}

Both invariants hold when add returns: the insert keeps the array sorted, and the trim keeps size within k.

What add costs

add does at most one binary search plus one shift. The binary search is about $\log k$ comparisons. The shift copies at most k slots. The trim costs nothing extra — no shift of its own, just clearing one slot. So a single add costs on the order of k, the same as adding to a SortedArray holding k elements.