Problem Statement

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:

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

Constraints:

• 2 <= nums.length <= 500

• 0 <= nums[i] <= 100

Explanation

Here we have been given a nums array and we need to find the numbers smaller than nums[i] present in the array.

Let's consider the given example,
nums = [8,1,2,2,3]
Output: [4,0,1,1,3]

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).

Solution

Let's see how we can solve this

Brute Force Approach

The simple approach to solve this question I can think of is

" Traverse the whole array for each nums[i] and count the numbers smaller than it and then store it in a new array "

public int[] smallerNumbersThanCurrent(int[] nums) {
        // to store the number of smaller elements
        int arr[] = new int[nums.length];

        for (int i=0; i<nums.length; ++i) {
            // Traversing the array for each nums[i]
            for (int j=0; j < nums.length; ++j) {
                // store smaller elements in arr
                if (nums[j] < nums[i])
                    arr[i]++;
            }
        }

        return arr;
    }

Let's see the Dry Run of the code
nums = [8,1,2,2,3]

First Loop is iterating for 5 times and for each nums[i], second loop does 5 iterations
so 5 + 5 + 5 + 5 + 5 = 25
In general, for n iterations, other n iterations are done for each iteration
Time Complexity - O(n^2)
Space Complexity - O(n)

Optimized Solution

Let's see how we can optimize our approach

• First, we calculate the occurrence of each number in nums

int arr[] = new int[101];
for (int i=0; i<nums.length; ++i) 
            arr[nums[i]]++;

- Here arr is used to store the number of occurrences of nums[i] in arr[nums[i]]
- arr is of size 101 because the maximum value nums array can have is 100(because of the constraints) so to store its occurrence in arr we take the size greater than 100
nums = [8,1,2,2,3]
nums[2] =2 and nums[3] = 2 so arr[nums[2]] is arr[2] and by arr[2]++ we count that 2 occur 1 time in nums so when nums[3] = 4 then arr[nums[3]] is arr[2] then we increment arr[2] to 2.

arr = [0, 1, 2, 1, 0, 0, 0, 0, 1, 0 .......]
arr[8] = 1 means 8 occurred 1 time in nums

• Now, we will find the running sum of arr

In the end, arr will look like this [0, 1, 3, 4, 4, 4, 4, 4, 5 .....].

Now Why we did it?

Suppose I want you to tell me how many numbers smaller than 3 are present in nums array by just looking at arr array

arr = [0, 1, 2, 1, 0, 0, 0, 0, 1, 0 .......]

What you will do?
you will count the number of occurrences before arr[3] and add them. There are 3 numbers smaller than 3 in nums array. Thats why we find the running sum of the array

After the running sum, arr will look something like this

arr = [0, 1, 3, 4, 4, 4, 4, 4, 5 .....]

Here, you can see that number before nums[i] represents the number of numbers smaller than i.

For example, arr[3] has 3 before it which means 3 small numbers are present in nums array

• Now we will just store the smaller numbers in another array

    int ans[] = new int[nums.length];
    for (int i=0; i<nums.length; ++i) {
                // '0' is the smallest number in nums array so
                if (nums[i] == 0) 
                    ans[i] = 0;
                else
                    // storing the previous element of num[i] in arr[i]
                    ans[i] = arr[nums[i] -1];
     }
  

  Here we are storing numbers smaller than i in ans

  nums[i] = 3
  then arr[2] -> contains numbers smaller than 3

  ans[i] -> stores numbers smaller than 3

public int[] smallerNumbersThanCurrent(int[] nums) {
        // to store occurences of nums[i]
        int arr[] = new int[101];
        // to store numbers smaller than nums[i]
        int ans[] = new int[nums.length];

        // calculating and storing occurences of nums[i] in arr
        for (int i=0; i<nums.length; ++i) 
            arr[nums[i]]++;

        // Running sum of arr array
        for (int i=1; i<101; ++i)
            arr[i] = arr[i] + arr[i-1];

        // storing numbers smaller than nums[i] in ans[i]
        for (int i=0; i<nums.length; ++i) {
            if (nums[i] == 0) 
                ans[i] = 0;
            else
                ans[i] = arr[nums[i] -1];
        }
        return ans;
    }

Time Complexity - O(n) [Calculate by yourself]
Space Complexity - O(n)

Thanks for reading this blog, I Hope it helped you in understanding the question better.
If you want more solutions like this then subscribe to my newsletter, I am making a series of DSA-Days in which I will post one solution a day of leetcode question. The series will cover all types of questions like Easy/Medium/Hard and they will be topic-wise.