p92 — Count of Smaller Numbers After Self

Source: LeetCode 315 · Hard · Topics: Fenwick Tree, Merge Sort, Coordinate Compression Companies (2024–2025): Google (high), Meta (medium), Amazon (medium), Bytedance (high) Loop position: Inversion counting in disguise. Tests the leap from “what does the problem ask” to “this is an inversion problem; use BIT or merge sort”.

1. Quick Context

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

Reframe: for each element, count smaller values to its right = count of inversions involving this element on the right.

Two solutions:

  • BIT over coordinate-compressed values, right-to-left: walk i from n-1 down to 0; query prefix(rank(nums[i]) - 1) to count smaller already-seen-to-the-right; then update(rank(nums[i]), +1).
  • Merge sort with index tracking: during merge, when taking from left, the count of right-elements already merged contributes to that left-index’s inversion count.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/count-of-smaller-numbers-after-self/

STOP. 35-min timer.

3. Prerequisite Concepts

  • Fenwick tree (LC 307).
  • Coordinate compression (sorted(set(nums)) + dict for rank).
  • Merge sort with index permutation.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Inversion count per element with j > i.

2. Clarify: Values can be negative; large range → compress.

3. Examples: [5,2,6,1] → [2,1,1,0].

5. Brute: O(n²) double loop.

6. Target: O(n log n).

7. Pattern: BIT or merge sort.

8. Develop: see solution.py.

9. Test: sorted asc (all 0); sorted desc (n-1, n-2, …); duplicates.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 BIT-right-to-left intuition

Walk i from right to left. At each step, the BIT holds the multiset of values to the right of i. Query “how many smaller than nums[i] have I already seen?” → bit.prefix(rank(nums[i]) - 1).

Coordinate compression maps n possibly-huge values into ranks [1..k] where k ≤ n.

6.2 Merge-sort intuition

Standard inversion-count adapted: during the merge step, maintain original indices. When you pop from the LEFT half, the count of elements already popped from the RIGHT half is the # of elements that are smaller AND to the right of this left element.

sort sublist by value while tracking original index
during merge, when left[i] is popped, ans[original_idx[left[i]]] += right_popped_so_far

6.3 Why both run in O(n log n)

  • BIT: each query/update O(log n); n elements.
  • Merge sort: O(n log n) standard; per-level merge is O(n) and there are log n levels.

6.4 BIT requires coordinate compression for arbitrary integer ranges

Without compression, BIT size = max_value − min_value + 1, blowing up memory. Compression maps to dense ranks.

6.5 Variants

  • LC 327 Count of Range Sum: similar reframe; sort prefix sums and BIT-count.
  • LC 493 Reverse Pairs: count pairs (i, j) with i < j and nums[i] > 2·nums[j]; merge-sort variant.
  • LC 1505 Min Possible Integer After K Swaps: BIT to track which digits remain.

6.6 Family: inversion / order-statistics

  • LC 315 Count Smaller After Self (this).
  • LC 327 Count of Range Sum.
  • LC 493 Reverse Pairs.
  • LC 1395 Count Number of Teams.
  • LC 2179 Count Good Triplets in an Array.

7. Anti-Pattern Analysis

  1. Naive O(n²) — works on small inputs; fails on n > 10⁴.
  2. Sort upfront, then index — destroys positional info needed.
  3. BIT without coordinate compression — TLE/MLE on large values.
  4. Off-by-one in BIT prefix — query prefix(rank-1) not prefix(rank) (else includes equal values).
  5. Merge sort modifying values directly — must track original indices in an auxiliary array.
  6. Use a sorted list with bisect.insort — O(n²) worst case because insert is O(n).

8. Skills & Takeaways

  • Inversion-counting reframe.
  • BIT over coordinate-compressed values.
  • Merge sort with index tracking.

9. When to Move On

  • Solve cold in 25 min.
  • Articulate why BIT solves inversion problems naturally.
  • Cite LC 493 Reverse Pairs as a generalization.

10. Company Context

  • Google: L6; expects BIT + compression.
  • Meta: E5/E6.
  • ByteDance: very common; loves merge-sort variant.
  • Amazon: L6.

Strong: “Reframed as inversion count. BIT over coordinate-compressed values, right-to-left scan. Also achievable via merge sort with index tracking; O(n log n) either way.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
ReframeMissesAfter hintCold+ cites inversion theory
BIT implNoneAfter hintClean+ coordinate compression
Merge sortNoneNoneSketch+ clean index-tracking
FamilyNoneNoneLC 327+ LC 493 + LP framing

12. Level Delta

  • Mid (L4): BIT after hint; works but messy compression.
  • Senior (L5): Cold BIT or merge sort.
  • Staff (L6): + both solutions + LC 493.
  • Principal (L7+): + framing as rank-aggregation problem / Kendall-tau distance + connection to sorting-network lower bounds (Ω(n log n) comparisons).

13. Follow-up Q&A

Q1: Count larger numbers after self instead. A1: Symmetric. prefix(max_rank) - prefix(rank) on the same BIT, or process left-to-right.

Q2: Reverse pairs (i < j, nums[i] > 2·nums[j]) — LC 493. A2: Merge sort variant; during merge, for each left[i], two-pointer scan right half counting r[j] < left[i]/2.

Q3: Online (streaming inserts) — count smaller after each insert. A3: Order-statistic balanced BST (skiplist or Treap) supporting insert + rank query in O(log n).

Q4: 2D version (count points dominated below-right). A4: Offline sweep + 2D BIT or persistent segment tree.

Q5: Total inversion count (sum of counts). A5: Just sum the result, or equivalent classical merge-sort inversion count in O(n log n).

14. Solution Walkthrough

See solution.py:

  • count_smaller_bit — Fenwick + coordinate compression.
  • count_smaller_mergesort — merge sort with index tracking.
  • count_smaller_brute — O(n²) oracle.

15. Beyond the Problem

Principal code review: “Count Smaller After Self is inversion counting dressed as an array problem. The Staff+ leap is recognizing this from the problem statement in 30 seconds — and once you have, the solution is mechanical: either BIT over coordinate-compressed values (right-to-left) or merge sort with index tracking. The deeper lesson: inversion count is the Kendall-tau distance between the input and its sorted form, and it’s a fundamental measure in rank aggregation (used in: recommender systems for ranking similarity, search-result re-ranking metrics, statistical tests like Mann-Whitney U). The principal-level recognition is that ANY problem reducible to ‘how many (i,j) pairs satisfy this monotone predicate’ can be solved in O(n log n) by BIT or merge sort. This pattern appears in: financial reconciliation (out-of-order trades), distributed system event reordering analysis, A/B test ranking metrics. Once you internalize the inversion-counting lens, dozens of seemingly-different problems collapse to the same algorithm.”