Given an array arr[] consisting of N integers, the task is for each array element, say arr[i], is to find the number of array elements that are smaller than arr[i].
Examples:
Input: arr[] = {3, 4, 1, 1, 2}
Output: 3 4 0 0 2
Explanation:
The elements which are smaller than arr[0](= 3) are {1, 1, 2}. Hence, the count is 3.
The elements which are smaller than arr[1](= 4) are {1, 1, 2, 3}. Hence, the count is 4.
The elements arr[2](= 1) and arr[3](= 1) are the smallest possible. Hence, the count is 0.
The elements which are smaller than arr[4](= 2) are {1, 1}. Hence, the count is 2.Input: arr[] = {1, 2, 3, 4}
Output: 0 1 2 3
Naive Approach: The simplest approach is to traverse the array and for each array element, count the number of array elements that are smaller than them and print the counts obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count for each array// element, the number of elements// that are smaller than that elementvoid smallerNumbers(int arr[], int N){ // Traverse the array for (int i = 0; i < N; i++) { // Stores the count int count = 0; // Traverse the array for (int j = 0; j < N; j++) { // Increment count if (arr[j] < arr[i]) { count++; } } // Print the count of smaller // elements for the current element cout << count << " "; }}// Driver Codeint main(){ int arr[] = { 3, 4, 1, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); smallerNumbers(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to count for each array// element, the number of elements// that are smaller than that elementstatic void smallerNumbers(int arr[], int N){ // Traverse the array for(int i = 0; i < N; i++) { // Stores the count int count = 0; // Traverse the array for(int j = 0; j < N; j++) { // Increment count if (arr[j] < arr[i]) { count++; } } // Print the count of smaller // elements for the current element System.out.print(count + " "); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 4, 1, 1, 2 }; int N = arr.length; smallerNumbers(arr, N);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to count for each array# element, the number of elements# that are smaller than that elementdef smallerNumbers(arr, N): # Traverse the array for i in range(N): # Stores the count count = 0 # Traverse the array for j in range(N): # Increment count if (arr[j] < arr[i]): count += 1 # Print the count of smaller # elements for the current element print(count, end=" ")# Driver Codeif __name__ == "__main__": arr = [3, 4, 1, 1, 2] N = len(arr) smallerNumbers(arr, N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to count for each array // element, the number of elements // that are smaller than that element static void smallerNumbers(int[] arr, int N) { // Traverse the array for(int i = 0; i < N; i++) { // Stores the count int count = 0; // Traverse the array for(int j = 0; j < N; j++) { // Increment count if (arr[j] < arr[i]) { count++; } } // Print the count of smaller // elements for the current element Console.Write(count + " "); } } // Driver Code static public void Main() { int[] arr = { 3, 4, 1, 1, 2 }; int N = arr.Length; smallerNumbers(arr, N); }}// This code is contributed by sanjoy_62, |
Javascript
<script>// Javascript program for the above approach// Function to count for each array// element, the number of elements// that are smaller than that elementfunction smallerNumbers(arr, N){ var i; // Traverse the array for(i = 0; i < N; i++) { // Stores the count var count = 0; // Traverse the array for (j = 0; j < N; j++) { // Increment count if (arr[j] < arr[i]) { count += 1; } } // Print the count of smaller // elements for the current element document.write(count + " "); }}// Driver Code var arr = [3, 4, 1, 1, 2] var N = arr.length; smallerNumbers(arr, N);</script> |
Output:
3 4 0 0 2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using Hashing. Follow the steps below to solve the problem:
- Initialize an auxiliary array hash[] of size 105 and initialize all array elements with 0 to store the frequency of each array element.
- Traverse the given array arr[] and increment the frequency of arr[i] by 1 in the array hash[] as hash[arr[i]]++.
- Find the prefix sum of the array hash[].
- Again, traverse the given array and for each array element arr[], print the value of hash[arr[i] – 1] as the count of smaller elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count for each array// element, the number of elements// that are smaller than that elementvoid smallerNumbers(int arr[], int N){ // Stores the frequencies // of array elements int hash[100000] = { 0 }; // Traverse the array for (int i = 0; i < N; i++) // Update frequency of arr[i] hash[arr[i]]++; // Initialize sum with 0 int sum = 0; // Compute prefix sum of the array hash[] for (int i = 1; i < 100000; i++) { hash[i] += hash[i - 1]; } // Traverse the array arr[] for (int i = 0; i < N; i++) { // If current element is 0 if (arr[i] == 0) { cout << "0"; continue; } // Print the resultant count cout << hash[arr[i] - 1] << " "; }}// Driver Codeint main(){ int arr[] = { 3, 4, 1, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); smallerNumbers(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to count for each array// element, the number of elements// that are smaller than that elementstatic void smallerNumbers(int arr[], int N){ // Stores the frequencies // of array elements int hash[] = new int[100000]; // Traverse the array for(int i = 0; i < N; i++) // Update frequency of arr[i] hash[arr[i]]++; // Initialize sum with 0 int sum = 0; // Compute prefix sum of the array hash[] for(int i = 1; i < 100000; i++) { hash[i] += hash[i - 1]; } // Traverse the array arr[] for(int i = 0; i < N; i++) { // If current element is 0 if (arr[i] == 0) { System.out.println("0"); continue; } // Print the resultant count System.out.print(hash[arr[i] - 1] + " "); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 4, 1, 1, 2 }; int N = arr.length; smallerNumbers(arr, N);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to count for each array# element, the number of elements# that are smaller than that elementdef smallerNumbers(arr, N): # Stores the frequencies # of array elements hash = [0] * 100000 # Traverse the array for i in range(N): # Update frequency of arr[i] hash[arr[i]] += 1 # Initialize sum with 0 sum = 0 # Compute prefix sum of the array hash[] for i in range(1, 100000): hash[i] += hash[i - 1] # Traverse the array arr[] for i in range(N): # If current element is 0 if (arr[i] == 0): print("0") continue # Print the resultant count print(hash[arr[i] - 1], end = " ")# Driver Codeif __name__ == "__main__": arr = [ 3, 4, 1, 1, 2 ] N = len(arr) smallerNumbers(arr, N)# This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{// Function to count for each array// element, the number of elements// that are smaller than that elementstatic void smallerNumbers(int []arr, int N){ // Stores the frequencies // of array elements int []hash = new int[100000]; // Traverse the array for(int i = 0; i < N; i++) // Update frequency of arr[i] hash[arr[i]]++; // Initialize sum with 0 //int sum = 0; // Compute prefix sum of the array hash[] for(int i = 1; i < 100000; i++) { hash[i] += hash[i - 1]; } // Traverse the array arr[] for(int i = 0; i < N; i++) { // If current element is 0 if (arr[i] == 0) { Console.WriteLine("0"); continue; } // Print the resultant count Console.Write(hash[arr[i] - 1] + " "); }}// Driver Codepublic static void Main(string[] args){ int []arr = { 3, 4, 1, 1, 2 }; int N = arr.Length; smallerNumbers(arr, N);}}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach // Function to count for each array // element, the number of elements // that are smaller than that element function smallerNumbers(arr, N) { // Stores the frequencies // of array elements let hash = new Array(100000); hash.fill(0); // Traverse the array for(let i = 0; i < N; i++) // Update frequency of arr[i] hash[arr[i]]++; // Initialize sum with 0 let sum = 0; // Compute prefix sum of the array hash[] for(let i = 1; i < 100000; i++) { hash[i] += hash[i - 1]; } // Traverse the array arr[] for(let i = 0; i < N; i++) { // If current element is 0 if (arr[i] == 0) { document.write("0" + "</br>"); continue; } // Print the resultant count document.write(hash[arr[i] - 1] + " "); } } let arr = [ 3, 4, 1, 1, 2 ]; let N = arr.length; smallerNumbers(arr, N); </script> |
Output:
3 4 0 0 2
Time Complexity: O(N)
Auxiliary Space: O(N), where N is the maximum value of the array elements
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
