Count of Smaller Numbers After Self

Count of Smaller Numbers After Self

What is this problem about?

The "Count of Smaller Numbers After Self interview question" is a classic hard-level challenge. You are given an integer array, and for each element, you need to count how many elements to its right are strictly smaller than it. The output is an array of these counts. For instance, in the array [5, 2, 6, 1], there are two numbers smaller than 5 to its right (2 and 1), and zero numbers smaller than 1 to its right.

Why is this asked in interviews?

Tech giants like Microsoft, Meta, and TikTok use the "Count of Smaller Numbers After Self coding problem" to test a candidate's ability to work with dynamic statistics. It requires more than a simple sort; it requires a structure that can update and query counts simultaneously as you move through the array. It evaluates knowledge of "Segment Tree interview pattern" or "Binary Indexed Tree (BIT)" and the ability to adapt Merge Sort for counting.

Algorithmic pattern used

This problem is typically solved using one of three patterns:

1. Merge Sort: As you merge two sorted sub-lists, if an element from the right list is moved into the merged list before an element from the left list, it means that element is smaller than all remaining elements in the left list.
2. Binary Indexed Tree (BIT) / Fenwick Tree: Traverse the array from right to left. For each number, query the BIT for the count of numbers smaller than it, and then update the BIT with the current number.
3. Binary Search Tree (BST): Build a specialized BST from right to left where each node stores the size of its left subtree.

Example explanation

Input: [5, 2, 6, 1]

1. Start from the right: 1. Count of smaller numbers seen so far: 0. Result: [?, ?, ?, 0].
2. Move to 6: Smallest numbers seen so far is 1. Count smaller than 6 is 1. Result: [?, ?, 1, 0].
3. Move to 2: Smallest number seen so far is 1. Count smaller than 2 is 1. Result: [?, 1, 1, 0].
4. Move to 5: Numbers seen are 1, 6, 2. Smaller than 5 are 1 and 2. Count is 2. Result: [2, 1, 1, 0].

Common mistakes candidates make

• Naive $O(N^2)$ Approach: Using two nested loops to count smaller elements for each position. This is the most common failure and will not pass large test cases.
• Incorrect BIT Range: Failing to handle negative numbers or large ranges when using a Binary Indexed Tree (requires coordinate compression).
• Merge Sort Indexing: Losing track of the original indices of elements during the sorting process, which is necessary to update the correct position in the output array.

Interview preparation tip

Practice "Coordinate Compression." It is a vital companion technique for "Binary Indexed Tree interview pattern" problems. It allows you to map large or negative values into a smaller range of positive integers, making BIT or Segment Tree solutions much more robust.