How do you approach Count of Smaller Numbers After Self?

A brute force O(n^2) approach checks all pairs. Can you use a modified sort?

What is the time complexity of Count of Smaller Numbers After Self?

Time complexity: O(n log n). Space complexity: O(n).

What are common mistakes on Count of Smaller Numbers After Self?

Splitting without actually shrinking, so the recursion never bottoms out on a two-element range. Allocating a fresh array at every level of the merge rather than reusing one buffer. Treating the split as the hard part. The combine step is where these problems are actually solved.

gitGood.dev

← Back to problems

Count of Smaller Numbers After Self

HardData Structures

Description

Given an integer array `nums`, return an integer array `counts` where `counts[i]` is the number of smaller elements to the right of `nums[i]`.

Example 1

Input: nums = [5,2,6,1]

Output: [2,1,1,0]

Explanation: For 5: two smaller elements (2 and 1). For 2: one (1). For 6: one (1). For 1: zero.

Example 2

Input: nums = [-1]

Output: [0]

Example 3

Input: nums = [-1,-1]

Output: [0,0]

Constraints

- 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4

Count of Smaller Numbers After Self: approach, complexity and pitfalls

A hard divide & conquer problem, graded against 6 test cases (3 of them hidden).

The pattern: Divide & Conquer

Split the problem, solve the halves, and combine the results.

Reach for it when you see: A problem that halves cleanly, or a required O(log n) / O(n log n) bound.

More Divide & Conquerproblems →

If you are stuck

Show the 3-step hint ladder

A brute force O(n^2) approach checks all pairs. Can you use a modified sort?
Use merge sort and count inversions during the merge step.
Track original indices alongside values so you can attribute counts correctly.

The optimal approach

Show the approach: Modified Merge Sort

Use merge sort on indices rather than values. During the merge step, when an element from the left half is placed, the number of elements already placed from the right half tells you how many smaller elements were to its right. Accumulate these counts in a result array.

Time: O(n log n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Divide & Conquer mistakes

These apply to the pattern as a whole, not just this problem.

Splitting without actually shrinking, so the recursion never bottoms out on a two-element range.
Allocating a fresh array at every level of the merge rather than reusing one buffer.
Treating the split as the hard part. The combine step is where these problems are actually solved.