Count number of elements smaller than current number.

Given an array num of size n, for each element of num count the number of elements of the array that are smaller than the current element. It means for each element num[i] you need to count the number of elements such that num[j] < num[i] and j != i. Return the counts in an array.

Example:

Example 1:
Input: num[] = {3, 2, 5, 1, 7};
Output: {2, 1, 3, 0, 4}

Explanation: 
Number of Elements smaller than num[0] = 3 are (1 and 2) = 2 
Number of Elements smaller than num[1] = 2 are (1) = 1
Number of Elements smaller than num[2] = 5 are (1, 2 and 3) = 3
Number of Elements smaller than num[3] = 1 are () = 0
Number of Elements smaller than num[4] = 7 are (1, 2, 3 and 5) = 4

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: {0, 0, 0, 0}

Example 3:
Input: num[] = {3, 2, 2, 5, 1, 7}
Output: {3, 1, 1, 4, 0, 5}

The question is very simple, you just have to get the counts of smaller elements for each and store them one by one in an array or vector and return them as your output. This question can be solved by multiple approaches let's discuss them here.

Note: We are using a C++ vector in our solution instead of an array because vectors are dynamic in nature and provide more functionality. (alert-passed)

Approach 1: Brute Force Solution.

You can run two nested loops, the outer loop will pick elements of the array one by one, and the inner loop will traverse the whole array each time to check and count the elements that satisfy the given condition. Each time the inner loop terminates store the count value into a new resulting array and return this array at the end.

C++ Solution code:

/*C++ program for how many number of elements smaller
 than current number.*/
#include<iostream>
#include<vector>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    vector<int> ans;
    int count;

    for(int i = 0; i < num.size(); i++){
        count = 0;
        for(int j = 0; j < num.size(); j++){
            if(num[i] > num[j])
               count++;
        }
        ans.push_back(count);
    }
    return ans;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

    for(int i = 0; i < result.size(); i++)
       cout<<result[i]<<" ";

    return 0;   
}

Output:

3 1 1 4 0 5

Time Complexity: Running two nested loops from 0 to n will take n x n units of time so the time complexity will be O(n^2).
Space Complexity: No extra space is required to perform any operation except the answer vector that is used to store the counts but we cannot consider this for calculating space complexity so overall space complexity will be O(1).

Approach 2: Using Hash Map and Sorting.

The above approach is solving the problem in O(n^2) time complexity but we can optimize the solution and can bring it to O(nlogn) time complexity by following the below algorithm.

Given num = [3, 2, 2, 5, 1, 7]

Step 1: Make a copy of the given array and sort it in ascending order.

copy = [1, 2, 2, 3, 5, 7]

Step 2: Store the values in a hash map corresponding to their index in reverse order. A map can store only unique values and storing values in reverse will help you to get the count of smaller values by their index.

mp[copy[5]] = mp[7] = 5
mp[copy[4]] = mp[5] = 4
mp[copy[3]] = mp[3] = 3
mp[copy[2]] = mp[2] = 1(overwritten 2 to 1)  
mp[copy[0]] = mp[1] = 0

Step 3: Store the values back in the num array.

num[0] = mp[num[0]] = mp[3] = 3
num[1] = mp[num[1]] = mp[2] = 1
num[2] = mp[num[2]] = mp[2] = 1
num[3] = mp[num[3]] = mp[5] = 4
num[4] = mp[num[4]] = mp[1] = 0
num[5] = mp[num[5]] = mp[7] = 5

Step 4: Return the num array as our answer.

num = [3, 1, 1, 4, 0, 5]

C++ Solution code:

/*C++ Optimized program for how many number of elements 
smaller than current number.*/
#include<bits/stdc++.h>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    unordered_map<int, int> mp;

    //make a copy vector
    vector<int> copy = num;
    //sort the copy vector in ascending order
    sort(copy.begin(), copy.end());

    //store elements corresponding to their index
    for(int i = num.size() - 1; i >= 0; i--){
        mp[copy[i]] = i;
    }
    
    //store map value back to num array
    for(int i = 0; i < num.size(); i++){
        num[i] = mp[num[i]];
    }
    return num;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

    for(int i = 0; i < result.size(); i++)
       cout<<result[i]<<" ";

    return 0;   
}

Output:

3 1 1 4 0 5

Time Complexity: Sorting the copied array will take O(nlogn) time, and running two separate loops for n elements will take 2O(n) time so the overall time complexity of our solution is O(nlogn).
Space Complexity: As we are using a new copy vector and unordered map for storing the element so overall space complexity is O(n).

Count number of elements smaller than current number.

Approach 1: Brute Force Solution.

Approach 2: Using Hash Map and Sorting.

No comments:

Post a Comment