# How Many Numbers Are Smaller Than the Current Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number)
Canonical: https://scaleengineer.com/dsa/problems/how-many-numbers-are-smaller-than-the-current-number
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
Given the array `nums`, for each `nums[i]` find out how many numbers in the array are smaller than it. That is, for each `nums[i]` you have to count the number of valid `j's` such that `j != i` **and** `nums[j] < nums[i]`.

Return the answer in an array.

**Example 1:**

**Input:** nums = [8,1,2,2,3]
**Output:** [4,0,1,1,3]
**Explanation:** 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

**Example 2:**

**Input:** nums = [6,5,4,8]
**Output:** [2,1,0,3]

**Example 3:**

**Input:** nums = [7,7,7,7]
**Output:** [0,0,0,0]

**Constraints:**

* `2 <= nums.length <= 500`
* `0 <= nums[i] <= 100`

# Approaches
## Brute Force Approach
This is the most straightforward method. We iterate through the array for each element and compare it with every other element to count how many are smaller.
**Time:** O(N^2), where N is the number of elements in the input array. This is because for each of the N elements, we iterate through the entire array again, leading to N * N comparisons. · **Space:** O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Simple to understand and implement.; Requires no extra data structures besides the result array.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.
### Explanation
The brute force approach involves using nested loops. The outer loop picks an element `nums[i]`, and the inner loop iterates through all elements `nums[j]` in the array.
For each `nums[i]`, we initialize a counter. Inside the inner loop, we check if `j` is not equal to `i` and if `nums[j]` is smaller than `nums[i]`. If both conditions are true, we increment the counter.
After the inner loop completes, the counter holds the total number of elements smaller than `nums[i]`. We store this count in our result array at the corresponding index `i`.
This process is repeated for every element in the input array.
```java
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && nums[j] < nums[i]) {
                    count++;
                }
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
- Initialize a result array `ans` with the same length as `nums`.
- Loop through each element `nums[i]` from `i = 0` to `n-1`.
- For each `nums[i]`, initialize a `count` to 0.
- Start a nested loop for each element `nums[j]` from `j = 0` to `n-1`.
- Inside the nested loop, if `j != i` and `nums[j] < nums[i]`, increment the `count`.
- After the inner loop, assign the final `count` to `ans[i]`.
- Return the `ans` array.

## Sorting Approach
A more optimized approach involves sorting. By sorting a copy of the array, we can determine the count of smaller numbers for any given value by finding its first index in the sorted array. A hash map can be used to store these counts for efficient lookup.
**Time:** O(N log N), where N is the number of elements. The dominant operation is sorting the array. Populating the map and the final result array both take O(N) time. · **Space:** O(N) to store the copy of the array and the hash map. The space for the result array is also O(N).
**Pros:** Significantly more efficient than the brute-force approach for larger N.; Conceptually clear, leveraging a standard sorting algorithm.
**Cons:** Requires extra space for the sorted copy and the hash map.; Not the most optimal if the range of numbers is small and known.
### Explanation
This method improves upon the brute-force approach by avoiding repeated scans. First, we create a copy of the input array `nums` and sort it. Let's call the sorted copy `sortedNums`.
The number of elements smaller than a certain value `x` is simply the index of the first occurrence of `x` in `sortedNums`. For example, in the sorted array `[1, 2, 2, 3, 8]`, the first `2` is at index 1, meaning one number is smaller than it.
To efficiently retrieve this count for each number in the original `nums` array, we can pre-process the `sortedNums` array. We iterate through `sortedNums` and store the first index of each unique number in a hash map. The map will store `(number, count_of_smaller_numbers)`.
Finally, we iterate through the original `nums` array one last time. For each `nums[i]`, we look up its value in the hash map to get the count of smaller numbers and place it in our result array.
```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        int[] sortedNums = Arrays.copyOf(nums, n);
        Arrays.sort(sortedNums);
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(sortedNums[i], i);
        }
        
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = map.get(nums[i]);
        }
        
        return ans;
    }
}
```
### Algorithm
- Create a copy of the `nums` array, named `sortedNums`.
- Sort the `sortedNums` array in ascending order.
- Create a `HashMap` to store the mapping from a number to the count of smaller numbers.
- Iterate through the `sortedNums` array. For each number, if it's not already in the map, add the number as the key and its index as the value. This works because the index of the first occurrence of a number in a sorted array is equal to the count of elements smaller than it.
- Initialize a result array `ans`.
- Iterate through the original `nums` array. For each `num`, get its corresponding count from the map and store it in `ans`.
- Return the `ans` array.

## Frequency Counting Approach
The most efficient approach leverages the problem's constraint that numbers are in a small, fixed range (0-100). We can use a frequency array (or counting sort idea) to count occurrences of each number and then use prefix sums to find the number of smaller elements for each value in O(1) time.
**Time:** O(N + K), where N is the length of `nums` and K is the range of possible values (101). Since K is a constant, the complexity is linear, O(N). · **Space:** O(K + N). We use an array of size K for frequency counts and prefix sums, and an array of size N for the result. Since K is constant (101), this simplifies to O(N).
**Pros:** Most efficient solution with linear time complexity.; Perfectly suited for problems with a small and fixed range of input values.
**Cons:** Space complexity depends on the range of numbers (K). It would be inefficient if the range of numbers were very large.
### Explanation
Given the constraint `0 <= nums[i] <= 100`, we can use an array as a frequency map. We create an integer array `counts` of size 101, initialized to all zeros.
We iterate through the input `nums` array once. For each number `num`, we increment `counts[num]`. After this pass, `counts[i]` will hold the frequency of the number `i` in the input array.
Next, we transform the `counts` array to store the number of elements smaller than the index. We can do this by calculating a running sum (prefix sum). Let's say we have a new array `smallerCounts`. `smallerCounts[0]` is 0 (no numbers are smaller than 0). For `i > 0`, `smallerCounts[i]` is the sum of all frequencies of numbers from 0 to `i-1`. This can be calculated iteratively: `smallerCounts[i] = smallerCounts[i-1] + counts[i-1]`.
After computing the prefix sums, `smallerCounts[x]` directly gives us the count of numbers in the original array that are strictly smaller than `x`.
Finally, we iterate through the original `nums` array again. For each `nums[i]`, we find the answer by looking up `smallerCounts[nums[i]]` and store it in the result array.
```java
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        // Constraints: 0 <= nums[i] <= 100
        int[] counts = new int[101];
        for (int num : nums) {
            counts[num]++;
        }
        
        // Calculate prefix sum for smaller counts
        int[] smallerCounts = new int[101];
        smallerCounts[0] = 0;
        for (int i = 1; i < 101; i++) {
            smallerCounts[i] = smallerCounts[i-1] + counts[i-1];
        }
        
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = smallerCounts[nums[i]];
        }
        
        return ans;
    }
}
```
### Algorithm
- Create a frequency array `counts` of size 101 (for values 0-100) and initialize it with zeros.
- Iterate through the input `nums` array and populate the `counts` array: `counts[num]++`.
- Create a prefix sum array, let's call it `smallerCounts`, also of size 101.
- Calculate the prefix sums: `smallerCounts[0] = 0`, and for `i` from 1 to 100, `smallerCounts[i] = smallerCounts[i-1] + counts[i-1]`.
- Initialize the result array `ans`.
- Iterate through the original `nums` array. For each `num = nums[i]`, set `ans[i] = smallerCounts[num]`.
- Return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] smallerNumbersThanCurrent(int[] nums) {
    int[] arr = nums.clone();
    Arrays.sort(arr);
    for (int i = 0; i < nums.length; ++i) {
      nums[i] = search(arr, nums[i]);
    }
    return nums;
  }
private
  int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> smallerNumbersThanCurrent(vector<int> &nums) {
    vector<int> arr = nums;
    sort(arr.begin(), arr.end());
    for (int i = 0; i < nums.size(); ++i) {
      nums[i] = lower_bound(arr.begin(), arr.end(), nums[i]) - arr.begin();
    }
    return nums;
  }
};

```

### Python

```python
class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: arr = sorted(nums) return [bisect_left(arr, x) for x in nums]

```