Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Count of Smaller Numbers After Self

Problem (restated)

For each index i, count how many j > i have nums[j] < nums[i]. Return the array of those counts.

Intuition

Walk right to left so “after self” is “already inserted.” A Fenwick tree of frequencies, indexed by compressed rank, answers “how many inserted values are < x” as a prefix sum. Then insert x.

Approaches

Fenwick on compressed ranks

Unverified

Time O(n log n)Space O(n)

Idea. Sort unique values to ranks. From the right: ans[i] = prefixSum(rank[x]-1), then update(rank[x], +1).

Walkthrough. [5,2,6,1]. Insert 1 (0 smaller). Insert 6 (1 smaller). Insert 2 (1). Insert 5 (2). Result [2,1,1,0].

Trade-offs. Coordinate compression is required because values are not a small 0..n range. Merge-sort inversion counting is an equivalent divide-and-conquer read.

Solution

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function countSmaller(nums: number[]): number[] {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  const res = new Array<number>(nums.length).fill(0);
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i]!)!;
    res[i] = bit.prefixSum(r - 1);
    bit.update(r, 1);
  }
  return res;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function countSmaller(nums: number[]): number[] {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  const res = new Array<number>(nums.length).fill(0);
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i]!)!;
    res[i] = bit.prefixSum(r - 1);
    bit.update(r, 1);
  }
  return res;
}

Template connection

BIT as a dynamic frequency table. LC 493 and LC 1649 are the same “query then insert” walk with a different predicate.

Reflection

Walk from the right. The tree counts how many already-seen values are smaller. Values are compressed ranks.
Query, then insert. An equal value is not smaller. Scanning left to right would count the left side instead.
One element is 0. A strictly increasing array is all zeros. A strictly decreasing array counts n - 1 down to 0.