Solution: Removing a Pair: remove

ArrayMap removes a pair by moving its last entry into the gap. That works there, because ArrayMap’s array has no order. Here it would break the map. The last key is the largest, so moving it into the gap would put it out of order, and binary search could miss keys that are in the map. So remove does what SortedArraySet’s remove does: it shifts the later keys one slot left to close the gap. As in put, the values shift with them.

@Override
public boolean remove(K key) {
  if (key == null) {
    throw new IllegalArgumentException();
  }
  int i = indexOf(key);
  if (i == -1) {
    return false;  // not present; nothing changed
  }
  for (int j = i; j < size - 1; j++) {  // shift later keys and values left
    keys[j] = keys[j + 1];
    values[j] = values[j + 1];
  }
  keys[size - 1] = null;  // clear the vacated slots
  values[size - 1] = null;
  size--;
  return true;
}

Here is remove("apple") on the map after put("banana", 4). "apple" is at index 0, so all three later pairs shift left:

before remove("apple")

keys    ┌─────────┬──────────┬───────┬────────┐
        │ "apple" │ "banana" │ "fig" │ "pear" │
        └─────────┴──────────┴───────┴────────┘
values  ┌─────────┬──────────┬───────┬────────┐
        │    5    │    4     │   2   │   3    │
        └─────────┴──────────┴───────┴────────┘
size 4

after remove("apple")

keys    ┌──────────┬───────┬────────┬───┐
        │ "banana" │ "fig" │ "pear" │   │
        └──────────┴───────┴────────┴───┘
values  ┌──────────┬───────┬────────┬───┐
        │    4     │   2   │   3    │   │
        └──────────┴───────┴────────┴───┘
size 3

The shift makes remove $O(n)$.