"Count smaller elements to the right" — classic problem testing whether you can go beyond the obvious O(n²).

Brute force — O(n²)

function countSmallerRight(arr) {
  const res = Array(arr.length).fill(0);
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) res[i]++;
    }
  }
  return res;
}
countSmallerRight([5, 2, 6, 1]); // [2, 1, 1, 0]

Two nested loops. Fine for small inputs; state it, then offer better.

Optimal — O(n log n)

The trick: process right to left and maintain a sorted view of everything seen so far. For each element, "how many already-seen elements are smaller" = its rank in that sorted set.

Approach A — binary insertion into a sorted array:

function countSmallerRight(arr) {
  const sorted = [];
  const res = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    // find insertion index = count of elements smaller than arr[i]
    let lo = 0, hi = sorted.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (sorted[mid] < arr[i]) lo = mid + 1;
      else hi = mid;
    }
    res[i] = lo;
    sorted.splice(lo, 0, arr[i]); // splice is O(n) — see caveat
  }
  return res;
}

Binary search is O(log n), but splice insertion is O(n) — so this is still O(n²) worst case. To get true O(n log n):

Approach B — Fenwick tree (BIT): coordinate-compress the values, then for each element right-to-left, query the prefix sum of counts below it and update. Both query and update are O(log n) → O(n log n) total.

Approach C — merge sort: count "inversions to the right" while merging — also O(n log n).

The framing

"Brute force is the nested loop, O(n²) — I'd write that first and confirm it works. The insight for the optimal solution is to scan right-to-left and ask 'what's the rank of this element among everything to its right.' A Fenwick tree or count-during-merge-sort answers that in O(log n) each, giving O(n log n) overall."