Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Count of Smaller Numbers After Self

Count of Smaller Numbers After Self

Master this topic with zero to advance depth.

Count of Smaller Numbers After Self

Counting smaller elements to the right can be solved by iterating backwards and using a data structure that supports 'insert' and 'count elements smaller than X'. Candidates include Binary Indexed Trees (BIT), Segment Trees, or modifying Merge Sort to track displacements. The Merge Sort approach is highly efficient as it naturally counts how many times an element from the right half is moved before an element from the left half.

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Visual Representation

nums = [5, 2, 6, 1] Right of 5: [2, 6, 1] -> 2 smaller (2, 1) Right of 2: [6, 1] -> 1 smaller (1) Right of 6: [1] -> 1 smaller (1) Right of 1: [] -> 0 smaller Result: [2, 1, 1, 0]
Hard

Examples

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

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each element at index i, iterate through all elements to its right (index j > i) and count how many are smaller than nums[i]. This is the most straightforward approach but inefficient for large arrays.

⏱ O(N²) - two nested loops.💾 O(1) extra space (excluding the result array).

Detailed Dry Run

nums = [5, 2, 6, 1]

  1. i=0, v=5: [2, 6, 1] -> 2, 1 are smaller. Count=2.
  2. i=1, v=2: [6, 1] -> 1 is smaller. Count=1.
  3. i=2, v=6: [1] -> 1 is smaller. Count=1.
  4. i=3, v=1: [] -> Count=0. Result: [2, 1, 1, 0]
java
import java.util.*;

public class Main {
    public static List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) count++;
            }
            result.add(count);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums)); // [2, 1, 1, 0]
    }
}
Approach 2

Level II: Better Solution (Binary Indexed Tree)

Intuition

Iterate through the array from right to left. For each element, we want to know how many elements we've already seen that are smaller than it. We can use a Binary Indexed Tree (BIT) to store the frequencies of the elements seen so far. Since the numbers can be large or negative, we use Coordinate Compression to map them to a small range [1, unique_elements].

⏱ O(N log N) - sorting for compression and BIT operations.💾 O(N) to store ranks and BIT.

Detailed Dry Run

BIT State Walkthrough

nums = [5, 2, 6, 1] -> Sorted Unique: [1, 2, 5, 6] Ranks: {1:1, 2:2, 5:3, 6:4} Backward Traversal: 1. val=1, rank=1: Query sum(0)=0. Update BIT at index 1. 2. val=6, rank=4: Query sum(3)=1. Update BIT at index 4. 3. val=2, rank=2: Query sum(1)=1. Update BIT at index 2. 4. val=5, rank=3: Query sum(2)=2. Update BIT at index 3. Result: [2, 1, 1, 0]
java
import java.util.*;

public class Main {
    static int[] bit;
    private static void update(int i, int n) {
        for (; i <= n; i += i & -i) bit[i]++;
    }
    private static int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += bit[i];
        return sum;
    }
    
    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 1;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i-1]) rank.put(sorted[i], r++);
        }
        
        bit = new int[r];
        Integer[] res = new Integer[n];
        for (int i = n - 1; i >= 0; i--) {
            res[i] = query(rank.get(nums[i]) - 1);
            update(rank.get(nums[i]), r - 1);
        }
        return Arrays.asList(res);
    }
    
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums));
    }
}
Approach 3

Level III: Optimal Solution (Modified Merge Sort)

Intuition

This approach uses the property of Merge Sort: while merging two sorted halves left and right, if we pick an element from left, any elements already moved from right to the temporary array are smaller than the current element and were originally to its right. We track original indices to update the counts array correctly.

⏱ O(N log N) - standard Merge Sort complexity.💾 O(N) for indices and temporary arrays.

Detailed Dry Run

Merge Step Trace

Left: [5, 2] (Indices: [0, 1]) Right: [6, 1] (Indices: [2, 3]) During Merge [5, 2] and [6, 1]: - 1 from Right is picked: Smaller count for elements in Left increases. - 2 from Left is picked: Counts[1] += (number of elements already picked from Right).
java
import java.util.*;

public class Main {
    private static int[] counts;
    private static int[] indices;

    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        indices = new int[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        
        mergeSort(nums, 0, n - 1);
        
        List<Integer> res = new ArrayList<>();
        for (int x : counts) res.add(x);
        return res;
    }

    private static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private static void merge(int[] nums, int left, int mid, int right) {
        int[] tempIndices = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0, rightCount = 0;

        while (i <= mid && j <= right) {
            if (nums[indices[j]] < nums[indices[i]]) {
                rightCount++;
                tempIndices[k++] = indices[j++];
            } else {
                counts[indices[i]] += rightCount;
                tempIndices[k++] = indices[i++];
            }
        }

        while (i <= mid) {
            counts[indices[i]] += rightCount;
            tempIndices[k++] = indices[i++];
        }
        while (j <= right) tempIndices[k++] = indices[j++];

        for (int p = 0; p < tempIndices.length; p++) indices[left + p] = tempIndices[p];
    }
    
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums)); // [2, 1, 1, 0]
    }
}
← Previous QuestionInsert Delete GetRandom O(1)
Next Question →Valid Sudoku