How Many Numbers Are Smaller Than the Current Number in an Array - The Coding Shala

Home >> Interview Questions >> how many numbers are smaller than the current number in an array

 In this post, we will learn how to check How Many Numbers Are Smaller Than the Current Number in an Array using Java Program.

How Many Numbers Are Smaller Than the Current Number in an Array Java Program

Given the array nums, for each num [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].

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

Java Solution

Approach 1

Using brute force(Two loops).

Java Program: 

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] ans = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            int tmp = 0;
            for(int j=0; j<nums.length; j++) {
                if(i!=j){
                    if(nums[i] > nums[j]) tmp++;
                }
            }
            ans[i] = tmp;
        }
        return ans;
    }
}

Approach 2

Here All the given numbers are between 0 and 100 so we can create an array of length 101 and put all the numbers in this array with the count at the corresponding index. 

Java Program: 

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] count = new int[101]; 
        for(int i=0;i<nums.length;i++) {
            count[nums[i]]++;
        }
        
        for(int i=1;i<101;i++){
            count[i] += count[i-1];
        }
        
        int[] ans = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            if(nums[i] == 0) ans[i] = 0;
            else ans[i] = count[nums[i]-1];
        }
        return ans;
    }
}

Other Posts You May Like

• How to find the second largest element in an array
• Find first duplicate in an array
• Remove duplicates from sorted array
• Triplets with a sum between the given range
• The intersection of two arrays

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.