Leaderboard: add, Phase 2 — Insert

Once the guard has ruled out values that do not belong on the board, the rest is a SortedArray insert: find where value belongs, shift the elements that come after it one slot over, and write it in.

The only difference is that arr is sorted descending, and SortedArray’s binary search assumes ascending order. The search has to be mirrored.

insertionPoint, mirrored

SortedArray.insertionPoint searches right when the middle element is smaller than value, because in ascending order that means value belongs further along. In a descending array, the direction that means “further along” is reversed: we search right when the middle element is bigger than value.

private int insertionPoint(T value) {
  int low = 0;
  int high = size - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    int cmp = arr[mid].compareTo(value);
    if (cmp == 0) {
      return mid;
    } else if (cmp > 0) {
      low = mid + 1;       // arr[mid] is bigger than value — value goes further right
    } else {
      high = mid - 1;      // arr[mid] is smaller than value — value goes further left
    }
  }
  return low;
}

The two branches under cmp > 0 and cmp < 0 swap places, because “bigger” and “smaller” now point in opposite directions along the array. Every other line is identical to SortedArray’s version.

Shift and insert

Once insertionPoint returns the right index, opening a gap and writing the value in looks exactly like SortedArray.add. This part is the same regardless of which direction the array is sorted: the elements from the insertion point onward move one slot to make room:

public void add(T value) {
  if (size == k && value.compareTo(arr[size - 1]) <= 0) {
    return;
  }
  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++;
  // trim comes next
}

At this point the board might briefly hold k + 1 elements. The backing array keeps a spare slot for exactly this case. The invariant “no more than k elements” is not restored yet. That is the trim’s job.