1365. How Many Numbers Are Smaller Than the Current Number
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:
-
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.
-
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.
-
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:
-
Initialize a frequency array
cnt
with a size of 102 to include all possible values from0
to100
along with an extra slot for ease of calculation. Ifnums
contains numbers up tomaxValue
, the size ofcnt
should bemaxValue + 2
.cnt = [0] * 102
-
Iterate over each element
x
in the inputnums
and increment the count ofx + 1
in the frequency arraycnt
. This shift by one is to allow us to later easily calculate the number of elements smaller than a given number using prefix sums.for x in nums: cnt[x + 1] += 1
-
Calculate the prefix sum using Python's
accumulate
function from theitertools
module. This operation will give us a new lists
representing the cumulative frequency. Nows[x]
will represent the total count of numbers that are less thanx
.s = list(accumulate(cnt))
-
Iterate through the elements in
nums
again to create the results array. For each elementx
innums
, we look ups[x]
which gives us the number of elements that are less thanx
and add this count to our result array.return [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 EvaluatorExample 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
.
-
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:cnt = [0] * 102
-
We then iterate over each element in
nums
and increment the corresponding index incnt
(shifted by one):nums = [4, 0, 2, 1] After processing each element: - cnt[4 + 1] = cnt[5] += 1 # increment at index 5 - cnt[0 + 1] = cnt[1] += 1 # increment at index 1 - cnt[2 + 1] = cnt[3] += 1 # increment at index 3 - cnt[1 + 1] = cnt[2] += 1 # increment at index 2 The frequency array (`cnt`) looks like this after iteration: cnt = [0, 1, 1, 1, 0, 1, 0, ..., 0]
-
We use Python's
accumulate
function to calculate the prefix sum, which gives us the cumulative count of smaller numbers:from itertools import accumulate s = list(accumulate(cnt)) # s now looks like this: [0, 1, 2, 3, 3, 4, 4, ..., 4] # This array represents the cumulative count of numbers less than the index.
-
Lastly, we iterate through the elements in
nums
again and create our result array using thes
array we just computed:result = [s[x] for x in nums] # result = [s[4], s[0], s[2], s[1]] # result now should be: [3, 0, 1, 1]
The final
result
array indicates that:- 3 numbers are smaller than 4 (
0
,1
, and2
) - 0 numbers are smaller than 0
- 1 number is smaller than 2 (
0
) - 1 number is smaller than 1 (
0
)
- 3 numbers are smaller than 4 (
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 thenums
list and update thecnt
array.O(m)
for theaccumulate
function which iterates over thecnt
array of fixed size 102.O(n)
for the list comprehension that constructs the result list by iterating over thenums
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.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!