1365. How Many Numbers Are Smaller Than the Current Number

EasyArrayHash TableCountingSorting
Leetcode Link

Problem Description

The problem is to find for each element in the array nums, how many elements are smaller than the current element. In other words, you walk through each item in the input list, and for each of these items, you need to count all other numbers in the list that are less than it. It's important to remember that you should not include the current element in the count. The goal is to create an output array of the same length as nums where each index contains this count of smaller numbers.

Example: If nums = [8,1,2,2,3], the output would be [4,0,1,1,3]. Here, four numbers are smaller than 8, no number is smaller than 1, one number is smaller than the first occurrence of 2, and so on.

Intuition

To find a solution to this problem, we could consider the following:

  1. Brute Force: We could use a nested loop to compare each pair of elements and count how many elements are smaller, but this would be O(n^2) in time complexity, which is not efficient for large arrays.

  2. Sorting: We could sort the array and then map each element to its corresponding index, but this would lose the original order of the elements, which we need to preserve.

  3. Counting Sort Principle: Since we know the elements in nums are integers and the problem typically has constraints that limit their range (not stated in the problem description here but usually up to 100), we can use a counting sort approach. This means we tally how many times each number occurs (the frequency), and then we can deduce how many numbers are smaller by looking at numbers (frequencies) to the left of the current number.

The intuition behind the provided solution is to build a frequency array cnt with an extra element so we can easily accumulate the counts. We use the accumulate function from Python's itertools to get a prefix sum of counts, effectively giving us a running total of how many numbers are smaller than each value up to 101 (assuming nums contains numbers up to 100 for this argument). By doing this, s[x] corresponds to the count of numbers less than x in the original array, as desired. Thus, s is used to create the output result conveniently and efficiently.

Learn more about Sorting patterns.

Solution Approach

The implementation of the solution makes use of a frequency array approach, which is a technique commonly used in counting sort algorithm. Here is a detailed walkthrough of the solution:

  1. Initialize a frequency array cnt with a size of 102 to include all possible values from 0 to 100 along with an extra slot for ease of calculation. If nums contains numbers up to maxValue, the size of cnt should be maxValue + 2.

    1cnt = [0] * 102
  2. Iterate over each element x in the input nums and increment the count of x + 1 in the frequency array cnt. This shift by one is to allow us to later easily calculate the number of elements smaller than a given number using prefix sums.

    1for x in nums:
    2    cnt[x + 1] += 1
  3. Calculate the prefix sum using Python's accumulate function from the itertools module. This operation will give us a new list s representing the cumulative frequency. Now s[x] will represent the total count of numbers that are less than x.

    1s = list(accumulate(cnt))
  4. Iterate through the elements in nums again to create the results array. For each element x in nums, we look up s[x] which gives us the number of elements that are less than x and add this count to our result array.

    1return [s[x] for x in nums]

The solution thus effectively uses the counting sort algorithm, which is often preferred for small integer ranges due to its O(n + k) complexity, where n is the number of elements in the array and k is the range of input numbers. This is more efficient than comparison-based sorting methods when k is relatively small compared to n.

This approach leverages the itertools.accumulate function to avoid manually calculating prefix sums, which provides a clean and efficient way to obtain the cumulative frequency.

The beauty of this solution lies in its simplicity and efficiency, allowing us to conclude the counts of smaller numbers in a single pass while utilizing a non-comparison-based sorting concept.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a smaller example array, nums = [4, 0, 2, 1]. Here we want to find out how many elements are smaller than each element in nums.

  1. We initialize the frequency array cnt with a size of 102 to cover all possible values in the range 0 to 100 inclusively, with an extra slot:

    1cnt = [0] * 102
  2. We then iterate over each element in nums and increment the corresponding index in cnt (shifted by one):

    1nums = [4, 0, 2, 1]
    2
    3After processing each element:
    4- cnt[4 + 1] = cnt[5] += 1  # increment at index 5
    5- cnt[0 + 1] = cnt[1] += 1  # increment at index 1
    6- cnt[2 + 1] = cnt[3] += 1  # increment at index 3
    7- cnt[1 + 1] = cnt[2] += 1  # increment at index 2
    8
    9The frequency array (`cnt`) looks like this after iteration:
    10cnt = [0, 1, 1, 1, 0, 1, 0, ..., 0]
  3. We use Python's accumulate function to calculate the prefix sum, which gives us the cumulative count of smaller numbers:

    1from itertools import accumulate
    2
    3s = list(accumulate(cnt))
    4# s now looks like this: [0, 1, 2, 3, 3, 4, 4, ..., 4]
    5# This array represents the cumulative count of numbers less than the index.
  4. Lastly, we iterate through the elements in nums again and create our result array using the s array we just computed:

    1result = [s[x] for x in nums]
    2# result = [s[4], s[0], s[2], s[1]]
    3# result now should be: [3, 0, 1, 1]

    The final result array indicates that:

    • 3 numbers are smaller than 4 (0, 1, and 2)
    • 0 numbers are smaller than 0
    • 1 number is smaller than 2 (0)
    • 1 number is smaller than 1 (0)

This example walkthrough demonstrates each step of the method described in the content above, yielding an efficient outcome that correctly matches each element in nums with the count of elements that are smaller than it.

Solution Implementation

1from itertools import accumulate
2
3class Solution:
4    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
5        # Initialize a count array with additional space to accumulate counts.
6        # We use 102 instead of 101 because we're using cnt[x+1] in the loop.
7        count = [0] * 102  
8      
9        # Count how many times each number (0-100) appears in nums.
10        # We increment the count at index x+1 to later use this space for accumulate.
11        for number in nums:
12            count[number + 1] += 1
13
14        # Calculate the prefix sum to determine how many numbers are
15        # less than the current number. This would help in getting counts directly.
16        # The 'accumulate' function is like a cumulative sum.
17        sum_count = list(accumulate(count))
18
19        # For each number in the original array, we now look up 
20        # how many numbers are smaller than it by referring to our sum_count.
21        # The result for each number is simply sum_count at the index of that number.
22        return [sum_count[number] for number in nums]
23
1class Solution {
2    public int[] smallerNumbersThanCurrent(int[] nums) {
3        // Container to store the count of the number of smaller elements for each element in 'nums'.
4        int[] count = new int[102]; // We use 102 instead of 101 to simplify the algorithm,
5                                    // so we don't need to handle the case of 0 separately.
6      
7        // Populate the count array where index represents the number+1 and
8        // the value at that index represents the count of that number in 'nums'.
9        for (int num : nums) {
10            ++count[num + 1];
11        }
12      
13        // Convert the count array to a prefix sum array
14        // where count[i] contains the number of elements less than i.
15        for (int i = 1; i < count.length; ++i) {
16            count[i] += count[i - 1];
17        }
18      
19        // Length of the original 'nums' array.
20        int n = nums.length;
21        // Result array where each element will be replaced by the count of numbers less than it.
22        int[] result = new int[n];
23      
24        // Fill the result array using the count array.
25        for (int i = 0; i < n; ++i) {
26            result[i] = count[nums[i]]; // nums[i] gives the number and count[nums[i]] gives
27                                        // the count of elements less than that number.
28        }
29      
30        // Return the result array.
31        return result;
32    }
33}
34
1#include <vector>
2
3class Solution {
4public:
5    // Function to find the number of elements smaller than each element in the array
6    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
7        // Array to store the count of each number plus one value ahead (prefix sum)
8        int count[102] = {0}; // Initialize all elements to 0
9
10        // Count how many times each number appears in the input vector
11        for (int number : nums) {
12            ++count[number + 1];
13        }
14
15        // Calculate the prefix sum to get the number of elements less than current
16        for (int i = 1; i < 102; ++i) {
17            count[i] += count[i - 1];
18        }
19
20        // Initialize the answer vector to store the results
21        vector<int> answer;
22
23        // Determine the number of smaller elements for each element in nums
24        for (int number : nums) {
25            // The count at the index 'number' of the prefix sum will be the
26            // number of elements smaller than 'number'
27            answer.push_back(count[number]);
28        }
29
30        // Return the complete answer
31        return answer;
32    }
33};
34
1function smallerNumbersThanCurrent(nums: number[]): number[] {
2    // Initialize a frequency array with 102 elements (to cover numbers 0-100 inclusive and an extra one for indexing purposes).
3    const frequencyArray: number[] = new Array(102).fill(0);
4
5    // Populate the frequency array with the count of each number in the input array (shifted by one index).
6    for (const num of nums) {
7        ++frequencyArray[num + 1];
8    }
9
10    // Transform the frequency array into a prefix sum array.
11    // Each element at index i now holds the total count of numbers less than i-1.
12    for (let i = 1; i < frequencyArray.length; ++i) {
13        frequencyArray[i] += frequencyArray[i - 1];
14    }
15
16    // The length of the input array.
17    const lengthOfNums = nums.length;
18
19    // Initialize an array to hold the answer.
20    const result: number[] = new Array(lengthOfNums);
21
22    // For each number in the input array, find the count of numbers smaller than itself using the prefix sum array.
23    for (let i = 0; i < lengthOfNums; ++i) {
24        result[i] = frequencyArray[nums[i]];
25    }
26
27    // Return the resulting array with counts for each number.
28    return result;
29}
30

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the number of elements in the input nums list and m is the range of numbers in nums. Here, the range m is fixed at 101 since we are using a count array cnt of size 102 (the extra one is to accommodate the 0 indexing and the fact that we started from x + 1). The time complexity breaks down as follows:

  • O(n) for the first for-loop where we iterate over the nums list and update the cnt array.
  • O(m) for the accumulate function which iterates over the cnt array of fixed size 102.
  • O(n) for the list comprehension that constructs the result list by iterating over the nums list again.

Thus, the overall time complexity is dominated by the terms O(n) and O(m), resulting in O(n + m).

The space complexity of the code is O(m), which comes from the cnt array of fixed size 102, and the s array, which will have the same size due to the use of the accumulate function on cnt. The space required for the output list is not counted towards the space complexity as it is required for the output of the function. Since m is a fixed constant (102), the space complexity can also be considered O(1), constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?


Recommended Readings