The O(n) Club: Count of Smaller Numbers After Self (or, Why Timing Out Is a Lifestyle Choice)

The O(n) Club: Count of Smaller Numbers After Self (or, Why Timing Out Is a Lifestyle Choice)

⚡ TL;DR

For each number in your array, count how many numbers to its right are smaller. Brute force works great—if you’re solving for ‘most patient developer.’ Here it is in Java:

// Brute-force: Not for production!
int[] countSmaller(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[i]) res[i]++;
        }
    }
    return res;
}

If your input is longer than your coffee order, expect pain.

🧠 How Devs Usually Mess This Up

Classic missteps include:

• Counting ‘greater than’ instead of ‘smaller than.’ Reading is hard.
• Checking both sides, or including the current element. Nope, it’s only what’s after.
• Using brute force and hoping the runtime fairy will save them. She won’t.

🔍 What’s Actually Going On

Think of this as a factory line. You finish assembling each widget, and you want to know: among the upcoming widgets, how many are strictly smaller? Repeat x N, or get smarter: process backwards, stuff values into a sorted ‘box,’ and efficiently ask, ‘How many of you are smaller than this?’ This is perfect for a merge sort remix—track counts while you merge, tally up as you go.

🛠️ PseudoCode

• Pair each number with its original index—because order matters here.
• Apply merge sort recursively.
• During merging, for each left-side element, count how many right-side elements have leaped ahead (they’re smaller and after self).
• Record this count in a result array at the original index.
• Return counts after the final glorious merge.

💻 The Code

// Merge sort remix for counting smaller-after-self
class Solution {
    public List
<integer> countSmaller(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int[][] arr = new int[n][2]; // [num, original index]
        for (int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        mergeSort(arr, 0, n - 1, result);
        List
<integer> list = new ArrayList<>();
        for (int cnt : result) list.add(cnt);
        return list;
    }
    private void mergeSort(int[][] arr, int l, int r, int[] res) {
        if (l >= r) return;
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m, res);
        mergeSort(arr, m + 1, r, res);
        merge(arr, l, m, r, res);
    }
    private void merge(int[][] arr, int l, int m, int r, int[] res) {
        int[][] temp = new int[r - l + 1][2];
        int i = l, j = m + 1, k = 0, cntRight = 0;
        while (i <= m && j <= r) {
            if (arr[j][0] < arr[i][0]) {
                temp[k++] = arr[j++];
                cntRight++;
            } else {
                res[arr[i][1]] += cntRight;
                temp[k++] = arr[i++];
            }
        }
        while (i <= m) {
            res[arr[i][1]] += cntRight;
            temp[k++] = arr[i++];
        }
        while (j <= r) {
            temp[k++] = arr[j++];
        }
        for (int p = 0; p < temp.length; p++) {
            arr[l + p] = temp[p];
        }
    }
}</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Make sure you only count numbers strictly less—duplicates aren’t ‘smaller.’
• Don’t forget the result array must use original indexes, not whatever the merge did last.
• Your O(n log n) is lovely, but don’t run this on a potato if your array is huge.

🧠 Interviewer Brain-Tattoo

“If it needs nested loops for big inputs, it’s not problem solving—it’s wishful thinking.”