How Many Numbers Are Smaller Than the Current Number

How Many Numbers Are Smaller Than the Current Number

What is this problem about?

The How Many Numbers Are Smaller Than the Current Number interview question asks you to take an array nums and, for each element nums[i], determine how many other elements in the array are strictly smaller than it. You need to return an array of these counts.

Why is this asked in interviews?

This is a popular screening question at Google, Amazon, and Meta. It evaluates your ability to optimize a brute-force $O(n^2)$ solution. While a nested loop works, interviewers are looking for an $O(n \log n)$ or $O(n)$ approach. It tests your knowledge of Hash Table interview patterns and sorting techniques to map values to their rank in a sorted set.

Algorithmic pattern used

There are two main ways to optimize this:

1. Sorting and Mapping ($O(n \log n)$):
   • Create a copy of the array and sort it.
   • Iterate through the sorted array. The first time you see a value, its index in the sorted array is exactly the count of numbers smaller than it.
   • Store these counts in a Hash Map.
   • Map the original numbers back to these counts.
2. Frequency Array/Counting Sort ($O(n)$):
   • If the input values are small (e.g., 0-100), count the frequency of each number.
   • Calculate prefix sums of the frequencies to find how many numbers exist below each value.

Example explanation

nums = [8, 1, 2, 2, 3]

1. Sorted copy: [1, 2, 2, 3, 8].
2. Create Map:
   • Value 1: first seen at index 0. Map: {1: 0}.
   • Value 2: first seen at index 1. Map: {1: 0, 2: 1}.
   • Value 3: first seen at index 3. Map: {1: 0, 2: 1, 3: 3}.
   • Value 8: first seen at index 4. Map: {1: 0, 2: 1, 3: 3, 8: 4}.
3. Apply to original: [4, 0, 1, 1, 3].

Common mistakes candidates make

• Nested Loops: Implementing the $O(n^2)$ solution when better alternatives exist.
• Handling Duplicates: In the sorting approach, forgetting to only map the first occurrence of a duplicate number (otherwise you'd count the duplicate itself).
• Index Confusion: Miscalculating the prefix sums in the frequency array approach.

Interview preparation tip

Always check the value constraints. If numbers are between 0 and 100, Counting Sort is almost always the intended optimal solution. If the range is large, the sorting and mapping approach is more robust.