315. Count of Smaller Numbers After Self


Problem Description

The problem at hand is a classic algorithmic challenge where we are given an array of integers, which we will refer to as nums. The goal is to find, for each element in the array, how many numbers to its right are smaller than it. To clarify, for every index i in the array, we want to calculate the count of elements that are located at any index greater than i and have a value less than nums[i]. The output should be an array of integers where each element counts[i] represents the number of smaller elements to the right of nums[i].

For example, if the input array nums is [5, 2, 6, 1], the output array should be [2, 1, 1, 0]. For the first element 5, there are two elements (2 and 1) to the right that are smaller. For the second element 2, there is only one element (1) to the right that is smaller, and so on.

Intuition

The straightforward brute force solution would be to go through each element in the array and count the number of smaller elements to its right with nested loops. However, this method would result in a time complexity of O(n^2), which is not efficient for large arrays.

To optimize this, we can use a data structure called a Binary Indexed Tree (BIT), also known as a Fenwick Tree, or alternatively, a Segment Tree. The Binary Indexed Tree is a data structure that allows us to update values and calculate prefix sums in a logarithmic time complexity, which is much faster than the brute force approach.

The intuition behind using BIT in this solution is as follows:

  1. First, we need to discretize the values in the array to make sure they can fit into our Binary Indexed Tree without taking too much space. Discretization involves mapping each value to its corresponding rank in the sorted list of unique values.

  2. We process the elements of the original array in reverse order. This means we start with the rightmost element and move to the left. This allows us to use the tree to keep track of the number of elements that have already been seen and are less than the current element.

  3. For each element, we find its index in the discretized array, which represents its value in the BIT.

  4. Before we add the current element to the tree, we query the tree to find out how many elements less than the current one have already been processed (those to the right in the original array). This query gives us the count of smaller numbers to the right.

  5. Update the Binary Indexed Tree to indicate that we have now seen an instance of the current element.

  6. We store the query result in the result list, which we then reverse at the end since we processed the elements from right to left.

Using the BIT, both the query and update operations are performed in O(log n) time, which significantly improves the efficiency for large datasets.

Solution Approach

The solution relies on two key components: the discretization of array values and a Binary Indexed Tree (BIT). Let's walk through the implementation step by step, highlighting how the algorithms, data structures, and patterns are used:

  1. Discretization of Values: Before we can work with the BIT, we need to make sure array indices won't be too large. This is achieved by discretizing the array values. In Python, this can be done by sorting the unique values and then creating a mapping from the original values to their indices in the sorted array, starting with 1 (since BIT works with 1-based indexing). This process can be seen in the code with:

    1alls = sorted(set(nums))
    2m = {v: i for i, v in enumerate(alls, 1)}

    Here, alls is the array of unique, sorted values and m maps each original value to its rank in the sorted array.

  2. Implementation of BIT: A BIT is a data structure that supports updating individual elements and calculating prefix sums efficiently. The Python class BinaryIndexedTree includes methods for updating the tree (update) and querying prefix sums (query), utilizing a helper method lowbit to isolate the rightmost bit of a binary representation.

    1class BinaryIndexedTree:
    2    def __init__(self, n):
    3        self.n = n
    4        self.c = [0] * (n + 1)
    5
    6    @staticmethod
    7    def lowbit(x):
    8        return x & -x
    9
    10    def update(self, x, delta):
    11        while x <= self.n:
    12            self.c[x] += delta
    13            x += BinaryIndexedTree.lowbit(x)
    14
    15    def query(self, x):
    16        s = 0
    17        while x > 0:
    18            s += self.c[x]
    19            x -= BinaryIndexedTree.lowbit(x)
    20        return s
    • self.c is the internal array of the BIT, initialized with zeros.
    • lowbit method isolates the lowest one bit of x, which is essential for navigating the tree structure.
    • update method adds delta to the value at index x, affecting all subsequent sums that include this element.
    • query method sums all the elements up to index x (exclusive), allowing us to get the count of smaller elements seen so far.
  3. Processing Elements in Reverse: We initialize a BIT with the size equal to the number of unique elements in nums. Then, we traverse the nums array in reverse, translating each element to its discretized form and using the update and query operations of BIT to build the counts array.

    1tree = BinaryIndexedTree(len(m))
    2ans = []
    3for v in nums[::-1]:
    4    x = m[v]
    5    tree.update(x, 1)
    6    ans.append(tree.query(x - 1))
    7return ans[::-1]
    • For each element v encountered, we look up its discretized index x.
    • Before updating x in BIT, we perform a query to get the count of elements smaller than x.
    • The result of each query is added to ans.
    • Since we've traversed the array in reverse, we need to reverse ans before returning it to get the correct order.

This implementation ensures that each update and query call is handled in O(log n) time, leading to an overall time complexity of O(n log n) due to processing each of the n elements once. It's a significant improvement over the brute force method and is well-suited for handling large input arrays.

Example Walkthrough

Let's consider a small example with the input array nums = [3, 4, 2, 7, 5]. Using the solution approach outlined, we want to find the number of elements to the right that are smaller than each element in nums.

  1. Discretization of Values: First, we discretize the array. The sorted unique values will be [2, 3, 4, 5, 7]. Our mapping m will be {2: 1, 3: 2, 4: 3, 5: 4, 7: 5}.

  2. Implementation of BIT: We create a Binary Indexed Tree for the five unique values.

    1tree = BinaryIndexedTree(5)
  3. Processing Elements in Reverse: We process the elements from right to left, updating the tree and querying for counts:

    • Starting with the last element 5, its discretized value is 4. Before we update, there are no smaller elements, so ans[] starts with [0].
    • Next is 7, with discretized value 5. The query(4) will find 0 elements smaller, so ans[] becomes [0, 0].
    • Now 2 is encountered with a discretized value of 1. Previous smaller elements don't exist (query(0)), thus ans[] is [0, 0, 0].
    • The fourth element is 4, corresponding to discretized 3. The query(2) shows there is one smaller (2), so ans[] is [0, 0, 1, 0].
    • The first element in reverse is 3, with discretized value 2. A query(1) will find there is one element smaller (2), adding up to ans[] as [0, 1, 1, 0, 0].

After processing, we have ans[] = [0, 1, 1, 0, 0], and we reverse it to get the final output: [0, 0, 1, 1, 0].

This corresponds to:

  • 3 (no smaller elements to the right),
  • 4 (no smaller elements to the right),
  • 2 (one smaller element, 5, to the right),
  • 7 (one smaller element, 5, to the right),
  • 5 (no smaller elements to the right).

Final Output: [0, 0, 1, 1, 0].

The Binary Indexed Tree speeds up the process where each update and query happens in logarithmic time relative to the number of unique elements. Overall, the time complexity of processing the array in this manner is O(n log n).

Python Solution

1class BinaryIndexedTree:
2    def __init__(self, size):
3        # Initialize Binary Indexed Tree with given size
4        self.size = size
5        self.tree = [0] * (size + 1)
6
7    @staticmethod
8    def lowbit(index):
9        # Get the lowest bit that is 1 in the binary representation of index
10        return index & -index
11
12    def update(self, index, delta):
13        # Increase the value at a specific index by delta and update the tree
14        while index <= self.size:
15            self.tree[index] += delta
16            index += BinaryIndexedTree.lowbit(index)
17
18    def query(self, index):
19        # Compute and return the prefix sum up to a given index
20        sum = 0
21        while index > 0:
22            sum += self.tree[index]
23            index -= BinaryIndexedTree.lowbit(index)
24        return sum
25
26
27class Solution:
28    def countSmaller(self, nums):
29        # Counts the smaller elements to the right for each element in nums
30
31        # Deduplicate and sort the list of numbers
32        unique_nums = sorted(set(nums))
33        # Create a mapping from number to its index in sorted unique numbers
34        num_to_index = {value: idx for idx, value in enumerate(unique_nums, 1)}
35      
36        # Initialize Binary Indexed Tree with size equal to the number of unique elements
37        tree = BinaryIndexedTree(len(num_to_index))
38        counts = []  # List to store counts of smaller elements
39      
40        # Iterate through the numbers in reverse order
41        for value in reversed(nums):
42            # Get the index of the current value in the sorted unique list
43            index = num_to_index[value]
44          
45            # Update the Binary Indexed Tree with the index
46            tree.update(index, 1)
47          
48            # Compute the count of smaller elements by querying the tree
49            # Query for index - 1 because it needs to return count for numbers less than current value
50            counts.append(tree.query(index - 1))
51      
52        # Since we iterated in reverse order, reverse the counts to match the original order
53        return counts[::-1]
54

Java Solution

1import java.util.*;
2
3class Solution {
4    public List<Integer> countSmaller(int[] nums) {
5        // Create a set to hold unique values from the input array
6        Set<Integer> uniqueValues = new HashSet<>();
7        for (int value : nums) {
8            uniqueValues.add(value);
9        }
10
11        // Create a sorted list of unique values
12        List<Integer> sortedUniqueValues = new ArrayList<>(uniqueValues);
13        Collections.sort(sortedUniqueValues);
14
15        // Map each unique number to its index in the sorted array
16        Map<Integer, Integer> valueToIndex = new HashMap<>();
17        for (int i = 0; i < sortedUniqueValues.size(); ++i) {
18            valueToIndex.put(sortedUniqueValues.get(i), i + 1);
19        }
20
21        // Initialize a Fenwick Tree (Binary Indexed Tree)
22        FenwickTree fenwickTree = new FenwickTree(sortedUniqueValues.size());
23
24        // Use a LinkedList to store the results as we need to add elements to the beginning
25        LinkedList<Integer> result = new LinkedList<>();
26
27        // Iterate over the input array in reverse order
28        for (int i = nums.length - 1; i >= 0; --i) {
29            int index = valueToIndex.get(nums[i]); // Get the index in the Fenwick Tree
30            fenwickTree.update(index, 1);          // Update the tree with the current number
31            result.addFirst(fenwickTree.query(index - 1)); // Query the count of numbers smaller than the current number
32        }
33
34        return result;
35    }
36}
37
38class FenwickTree {
39    private int size;
40    private int[] tree;
41
42    // Constructor for Fenwick Tree with a given size
43    public FenwickTree(int size) {
44        this.size = size;
45        this.tree = new int[size + 1];
46    }
47
48    // Update the Fenwick Tree with a given value at a specified index
49    public void update(int index, int delta) {
50        while (index <= size) {
51            tree[index] += delta;
52            index += lowBit(index);
53        }
54    }
55
56    // Query the cumulative frequency from index 1 to the given index
57    public int query(int index) {
58        int sum = 0;
59        while (index > 0) {
60            sum += tree[index];
61            index -= lowBit(index);
62        }
63        return sum;
64    }
65
66    // Method to get the lowest one bit value of a given number
67    public static int lowBit(int x) {
68        return x & (-x);
69    }
70}
71

C++ Solution

1#include <vector>
2#include <unordered_set>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
6
7// Binary Indexed Tree class for efficient update and prefix sum queries.
8class BinaryIndexedTree {
9public:
10    int size;                   // Size of the array for which the tree is constructed.
11    vector<int> treeArray;      // The tree array storing the cumulative frequencies.
12
13    // Constructor that initializes the size and tree array.
14    BinaryIndexedTree(int sz)
15        : size(sz), treeArray(sz + 1, 0) {}
16
17    // Update the tree with the given value 'delta'.
18    void update(int index, int delta) {
19        while (index <= size) {
20            treeArray[index] += delta;       // Add 'delta' to the current index.
21            index += lowBit(index);          // Move to the next index to be updated.
22        }
23    }
24
25    // Query the prefix sum up to a given index 'x'.
26    int query(int index) {
27        int sum = 0;
28        while (index > 0) {
29            sum += treeArray[index];         // Accumulate the sum.
30            index -= lowBit(index);          // Move to the previous index to accumulate.
31        }
32        return sum;
33    }
34
35private:
36    // Helper function to get the least significant bit of an integer 'x'.
37    int lowBit(int x) {
38        return x & -x;
39    }
40};
41
42// Solution class that uses BinaryIndexedTree to solve the problem.
43class Solution {
44public:
45    // Method that returns a vector of counts of smaller elements after each element.
46    vector<int> countSmaller(vector<int>& nums) {
47        unordered_set<int> elementsSet(nums.begin(), nums.end());
48        vector<int> uniqueElements(elementsSet.begin(), elementsSet.end());
49        sort(uniqueElements.begin(), uniqueElements.end());           // Sort to assign ranks.
50        unordered_map<int, int> ranks;                               // Map to store the element's rank.
51      
52        int numSize = uniqueElements.size();
53        for (int i = 0; i < numSize; ++i) ranks[uniqueElements[i]] = i + 1;
54      
55        BinaryIndexedTree binaryIndexedTree(numSize);
56        vector<int> countSmaller(nums.size());
57
58        // Starting from the end of the input array, update and query the tree.
59        for (int i = nums.size() - 1; i >= 0; --i) {
60            int rank = ranks[nums[i]];
61            binaryIndexedTree.update(rank, 1);                       // Update the tree with the current element's rank.
62            countSmaller[i] = binaryIndexedTree.query(rank - 1);     // Get count of smaller elements seen so far.
63        }
64
65        return countSmaller;
66    }
67};
68

Typescript Solution

1// Equivalent to std::vector in C++, TypeScript arrays are flexible and dynamic.
2// Define the array that will be used as the Binary Indexed Tree.
3let treeArray: number[] = [];
4
5// "size" will be used to represent the size of the array for which the tree is constructed.
6let size: number = 0;
7
8// Initializes the Binary Indexed Tree with a specific size.
9function createBinaryIndexedTree(sz: number): void {
10    size = sz;
11    treeArray = Array(sz + 1).fill(0);
12}
13
14// Updates the Binary Indexed Tree with the given value 'delta' at a specific 'index'.
15function update(index: number, delta: number): void {
16    while (index <= size) {
17        treeArray[index] += delta; // Add 'delta' to the current index.
18        index += lowBit(index);    // Move to the next index to be updated.
19    }
20}
21
22// Queries the prefix sum up to a given index 'index'.
23function query(index: number): number {
24    let sum = 0;
25    while (index > 0) {
26        sum += treeArray[index]; // Accumulate the sum.
27        index -= lowBit(index);  // Move to the previous index to accumulate.
28    }
29    return sum;
30}
31
32// Helper function to get the least significant bit of an integer 'x'.
33function lowBit(x: number): number {
34    return x & -x;
35}
36
37// Method that returns an array of counts of smaller elements after each element.
38function countSmaller(nums: number[]): number[] {
39    const elementsSet: Set<number> = new Set(nums);
40    const uniqueElements: number[] = Array.from(elementsSet).sort((a, b) => a - b); // Sort to assign ranks.
41    const ranks: Map<number, number> = new Map(); // Map to store the element's rank.
42
43    const numSize = uniqueElements.length;
44    for (let i = 0; i < numSize; ++i) ranks.set(uniqueElements[i], i + 1);
45
46    createBinaryIndexedTree(numSize);
47    const countSmaller: number[] = new Array(nums.length).fill(0);
48
49    // Starting from the end of the input array, update and query the Binary Indexed Tree.
50    for (let i = nums.length - 1; i >= 0; --i) {
51        const rank = ranks.get(nums[i]);
52        if (rank !== undefined) {
53            update(rank, 1);   // Update the binary indexed tree with the current element's rank.
54            countSmaller[i] = query(rank - 1); // Get count of smaller elements seen so far.
55        }
56    }
57
58    return countSmaller;
59}
60

Time and Space Complexity

The given Python code implements a Binary Indexed Tree (also known as a Fenwick Tree) to solve the problem of finding the count of smaller numbers after each element for a given list of integers.

Time Complexity:

  1. Sorting unique values (sorted(set(nums))):

    • This operation involves extracting unique elements from nums and then sorting them, which has a time complexity of O(k log k) where k is the number of unique elements.
  2. Building a map for value to index (m = {v: i for i, v in enumerate(alls, 1)}):

    • This takes O(k) time, as it is iterating over all unique elements once.
  3. Binary Indexed Tree operations within the main loop (for v in nums[::-1]: ...):

    • For each v in the list nums, we perform an update and a query operation on the tree. Since each update and query takes O(log n) time and we are doing it for all n elements, this part takes a total of O(n log n) time.
  4. Reversing the answer list (return ans[::-1]):

    • This operation takes O(n) time for a list of n elements.

Combining these parts, the overall time complexity is O(n log n) since the sorting can be considered a preprocessing step with a negligible O(k log k) complexity compared to the O(n log n) complexity of the main operations with the Binary Indexed Tree.

Space Complexity:

  1. Storage for the Binary Indexed Tree (self.c = [0] * (n + 1)):

    • The space used by the tree is O(n) where n is the number of elements in the input nums.
  2. Space for the sorted unique values and map (alls and m):

    • The sorted list of unique values alls and the map m both take O(k) space where k is the number of unique elements.
  3. Space for the answer (ans):

    • Since we store the count of smaller elements for each input element, this also takes O(n) space.

The dominant space complexity for the entire algorithm is O(n), which takes into account the space for the Binary Indexed Tree and the results list.

In conclusion, the code has a time complexity of O(n log n) and a space complexity of O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫