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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala