The O(n) Club: Smaller Numbers Than You (and Other Ego Checks)

The O(n) Club: Smaller Numbers Than You (and Other Ego Checks)

⚡ TL;DR

Need to count how many numbers are strictly smaller than each item in nums[]? Brute force is only for people who love timeouts. Quick Java taste:

// O(n^2) brute force, like running in flip-flops:
int[] smallerNumbersThanCurrent(int[] nums) {
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] < nums[i]) res[i]++;
        }
    }
    return res;
}

🧠 How Devs Usually Mess This Up

Common rookie missteps: Counting the current element (“Self-love is great, but not here”), assuming a 2 is less than another 2 (spoiler: it isn’t), or bravely launching brute force and waiting for the O(n²) apocalypse. Duplicates? Treat every number as a special snowflake—calculate only values strictly less, regardless of where the twins sit in the array.

🔍 What’s Actually Going On

Think of it like grading on a curve: For each number in your testy, anxious classroom, you want to know how many scored less. Not equal. If there’s a gang of 2s, none gets ahead. Here’s the cheat: Since every number is between 0 and 100 (clearly not SAT scores), you can count them all using a fixed-size array, keeping things swift—no sorting, no stalling, no server sobbing.

🛠️ PseudoCode

• Set up a score counter: Use count[101] to count the frequency of every possible value.

💻 The Code

public int[] smallerNumbersThanCurrent(int[] nums) {
    int[] count = new int[101];
    for (int num : nums) {
        count[num]++;
    }
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i] == 0 ? 0 : count[nums[i] - 1];
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Counting yourself? Only if you’re writing your own performance review (hint: don’t do it in code).
• Twins. Each ‘2’ is just another face in the crowd—don’t count them as smaller than each other.
• If numbers weren’t in 0–100, this could eat RAM for brunch. But here? Your call stack can chill.
• Complexity: O(n) time and O(1-ish) space, because 101 is basically pocket change.

🧠 Interviewer Brain-Tattoo

Don’t outsmart yourself: counting sort here is O(n) magic, but only because the number range is tiny. If your input ever looks like a phonebook, abandon ship—or at least this approach.