For each element in 1st array count elements less than or equal to it in 2nd array
Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[].
Source: Amazon Interview Experience | Set 354 (For SDE-2)
Examples:
Input : arr1[] = [1, 2, 3, 4, 7, 9]
arr2[] = [0, 1, 2, 1, 1, 4]
Output : [4, 5, 5, 6, 6, 6]
So the number of elements less than or equal to
1 is 4, 2 is 5, 3 is 5, 4 is 6, 7 is 6 and 9 is 6.
Input : arr1[] = [5, 10, 2, 6, 1, 8, 6, 12]
arr2[] = [6, 5, 11, 4, 2, 3, 7]
Output : [4, 6, 1, 5, 0, 6, 5, 7]
So the number of elements less than or equal to
5 is 4, 10 is 6, 2 is 1, 6 is 5, 1 is 0, 8 is 6,
6 is 5 and 12 is 7
Naive Approach:
Approach: The idea is to use two loops, the outer loop for elements of array arr1[] and an inner loop for elements of array arr2[]. Then for each element of arr1[], count elements less than or equal to it in arr2[].
Algorithm :
- Traverse through the elements of the first array from start to end.
- For every element in the first array.
- Traverse through the elements in the second array and find the count of elements that are less than or equal to the element of the first array.
- Print the count for every index.
Implementation:
C++
// C++ code for the above algorithm #include <bits/stdc++.h> using namespace std; // Function to count for each // element in 1st array, // elements less than or equal // to it in 2nd array void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // Run two loops to count // First loop to traverse the first array // Second loop to traverse the second array for ( int i = 0; i < m; i++) { int count = 0; // Traverse through second array for ( int j = 0; j < n; j++) if (arr2[j] <= arr1[i]) count++; cout << count << " " ; } } // Driver program to test above int main() { int arr1[] = { 1, 2, 3, 4, 7, 9 }; int arr2[] = { 0, 1, 2, 1, 1, 4 }; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); countEleLessThanOrEqual(arr1, arr2, m, n); return 0; } |
Java
import java.util.Arrays; class GFG { // function to count for each // element in 1st array, // elements less than or equal // to it in 2nd array static int countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // Run two loops to count // First loop to traverse the first array // Second loop to traverse the second array for ( int i = 0 ; i < m; i++) { int count = 0 ; // Traverse through second array for ( int j = 0 ; j < n; j++) if (arr2[j] <= arr1[i]) count++; System.out.print(count + " " ); } return m; } // Driver method public static void main(String[] args) { int arr1[] = { 1 , 2 , 3 , 4 , 7 , 9 }; int arr2[] = { 0 , 1 , 2 , 1 , 1 , 4 }; countEleLessThanOrEqual( arr1, arr2, arr1.length, arr2.length); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 code for the above algorithm # function to count for each element in 1st array, # elements less than or equal to it in 2nd array def countEleLessThanOrEqual(arr1, arr2, m, n): # Run two loops to count # First loop to traverse the first array # Second loop to traverse the second array for i in range (m): count = 0 # Traverse through second array for j in range (n): if (arr2[j] < = arr1[i]): count + = 1 print (count, end = " " ) # Driver program to test above arr1 = [ 1 , 2 , 3 , 4 , 7 , 9 ] arr2 = [ 0 , 1 , 2 , 1 , 1 , 4 ] m = len (arr1) n = len (arr2) countEleLessThanOrEqual(arr1, arr2, m, n) # This code is contributed by shubhamsingh10 |
C#
// C# implementation of For each element using System; class GFG { // function to count for each element in 1st array, // elements less than or equal to it in 2nd array static void countEleLessThanOrEqual( int [] arr1, int [] arr2, int m, int n) { // Run two loops to count // First loop to traverse the first array // Second loop to traverse the second array for ( int i = 0; i < m; i++) { int count = 0; // Traverse through second array for ( int j = 0; j < n; j++) if (arr2[j] <= arr1[i]) count++; Console.Write((count) + " " ); } } // Driver method public static void Main() { int [] arr1 = { 1, 2, 3, 4, 7, 9 }; int [] arr2 = { 0, 1, 2, 1, 1, 4 }; countEleLessThanOrEqual(arr1, arr2, arr1.Length, arr2.Length); } } // This code is contributed by mohit kumar 29. |
Javascript
<script> // JavaScript code for the above algorithm // Function to count for each // element in 1st array, // elements less than or equal // to it in 2nd array function countEleLessThanOrEqual(arr1, arr2, m, n) { // Run two loops to count // First loop to traverse the first array // Second loop to traverse the second array for (let i = 0; i < m; i++) { let count = 0; // Traverse through second array for (let j = 0; j < n; j++) if (arr2[j] <= arr1[i]) count++; document.write(count + " " ); } } // Driver program to test above let arr1 = [ 1, 2, 3, 4, 7, 9 ]; let arr2 = [ 0, 1, 2, 1, 1, 4 ]; let m = arr1.length; let n = arr2.length; countEleLessThanOrEqual(arr1, arr2, m, n); // This code is contributed by Surbhi Tyagi. </script> |
4 5 5 6 6 6
Complexity Analysis:
- Time complexity: O(m * n).
Considering arr1[] and arr2[] are of sizes m and n respectively. - Space Complexity: O(1).
As no extra space is required
Efficient Solution:
Approach: Sort the elements of 2nd array, i.e., array arr2[]. Then perform a modified binary search on array arr2[]. For each element x of array arr1[], find the last index of the largest element smaller than or equal to x in sorted array arr2[]. The index of the largest element will give the count of elements.
Algorithm:
- Sort the second array.
- Traverse through the elements of the first array from start to end.
- For every element in the first array.
- Do a binary search on the second array and find the index of the largest element smaller than or equal to the element of the first array.
- The index of the largest element will give the count of elements. Print the count for every index.
C++
// C++ implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array #include <bits/stdc++.h> using namespace std; // function returns the index of largest element // smaller than equal to 'x' in 'arr'. For duplicates // it returns the last index of occurrence of required // element. If no such element exits then it returns -1. int binary_search( int arr[], int l, int h, int x) { while (l <= h) { int mid = (l + h) / 2; // if 'x' is greater than or equal to arr[mid], // then search in arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // required index return h; } // function to count for each element in 1st array, // elements less than or equal to it in 2nd array void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // sort the 2nd array sort(arr2, arr2 + n); // for each element of 1st array for ( int i = 0; i < m; i++) { // last index of largest element // smaller than or equal to x int index = binary_search( arr2, 0, n - 1, arr1[i]); // required count for the element arr1[i] cout << (index + 1) << " " ; } } // Driver program to test above int main() { int arr1[] = { 1, 2, 3, 4, 7, 9 }; int arr2[] = { 0, 1, 2, 1, 1, 4 }; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); countEleLessThanOrEqual(arr1, arr2, m, n); return 0; } |
Java
// Java implementation of For // each element in 1st // array count elements less // than or equal to it // in 2nd array import java.util.Arrays; class GFG { // method returns the index // of largest element // smaller than equal to 'x' // in 'arr'. For duplicates // it returns the last index // of occurrence of required // element. If no such element // exits then it returns -1. static int binary_search( int arr[], int l, int h, int x) { while (l <= h) { int mid = (l + h) / 2 ; // if 'x' is greater than or equal // to arr[mid], then search in // arr[mid+1...h] if (arr[mid] <= x) l = mid + 1 ; // else search in arr[l...mid-1] else h = mid - 1 ; } // Required index return h; } // Method to count for each // element in 1st array, // elements less than or equal // to it in 2nd array static void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // Sort the 2nd array Arrays.sort(arr2); // for each element of 1st array for ( int i = 0 ; i < m; i++) { // Last index of largest element // smaller than or equal to x int index = binary_search( arr2, 0 , n - 1 , arr1[i]); // Required count for the element arr1[i] System.out.print((index + 1 ) + " " ); } } // Driver method public static void main(String[] args) { int arr1[] = { 1 , 2 , 3 , 4 , 7 , 9 }; int arr2[] = { 0 , 1 , 2 , 1 , 1 , 4 }; countEleLessThanOrEqual( arr1, arr2, arr1.length, arr2.length); } } |
Python3
# python implementation of For each element in 1st # array count elements less than or equal to it # in 2nd array # function returns the index of largest element # smaller than equal to 'x' in 'arr'. For duplicates # it returns the last index of occurrence of required # element. If no such element exits then it returns -1 def bin_search(arr, n, x): l = 0 h = n - 1 while (l < = h): mid = int ((l + h) / / 2 ) # if 'x' is greater than or equal to arr[mid], # then search in arr[mid + 1...h] if (arr[mid] < = x): l = mid + 1 ; else : # else search in arr[l...mid-1] h = mid - 1 # required index return h # function to count for each element in 1st array, # elements less than or equal to it in 2nd array def countElements(arr1, arr2, m, n): # sort the 2nd array arr2.sort() # for each element in first array for i in range (m): # last index of largest element # smaller than or equal to x index = bin_search(arr2, n, arr1[i]) # required count for the element arr1[i] print (index + 1 ,end = " " ) # driver program to test above function arr1 = [ 1 , 2 , 3 , 4 , 7 , 9 ] arr2 = [ 0 , 1 , 2 , 1 , 1 , 4 ] m = len (arr1) n = len (arr2) countElements(arr1, arr2, m, n) # This code is contributed by Aditi Sharma |
C#
// C# implementation of For each element // in 1st array count elements less than // or equal to it in 2nd array using System; public class GFG { // method returns the index of // largest element smaller than // equal to 'x' in 'arr'. For // duplicates it returns the last // index of occurrence of required // element. If no such element // exits then it returns -1. static int binary_search( int [] arr, int l, int h, int x) { while (l <= h) { int mid = (l + h) / 2; // if 'x' is greater than or // equal to arr[mid], then // search in arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in // arr[l...mid-1] else h = mid - 1; } // required index return h; } // method to count for each element // in 1st array, elements less than // or equal to it in 2nd array static void countEleLessThanOrEqual( int [] arr1, int [] arr2, int m, int n) { // sort the 2nd array Array.Sort(arr2); // for each element of 1st array for ( int i = 0; i < m; i++) { // last index of largest // element smaller than or // equal to x int index = binary_search( arr2, 0, n - 1, arr1[i]); // required count for the // element arr1[i] Console.Write((index + 1) + " " ); } } // Driver method public static void Main() { int [] arr1 = { 1, 2, 3, 4, 7, 9 }; int [] arr2 = { 0, 1, 2, 1, 1, 4 }; countEleLessThanOrEqual(arr1, arr2, arr1.Length, arr2.Length); } } // This code is contributed by Sam007. |
Javascript
<script> // Javascript implementation of For // each element in 1st // array count elements less // than or equal to it // in 2nd array // method returns the index // of largest element // smaller than equal to 'x' // in 'arr'. For duplicates // it returns the last index // of occurrence of required // element. If no such element // exits then it returns -1. function binary_search(arr,l,h,x) { while (l <= h) { let mid = Math.floor((l + h) / 2); // if 'x' is greater than or equal // to arr[mid], then search in // arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // Required index return h; } // Method to count for each // element in 1st array, // elements less than or equal // to it in 2nd array function countEleLessThanOrEqual(arr1,arr2,m,n) { // Sort the 2nd array arr2.sort( function (a,b){ return a-b;}); // for each element of 1st array for (let i = 0; i < m; i++) { // Last index of largest element // smaller than or equal to x let index = binary_search( arr2, 0, n - 1, arr1[i]); // Required count for the element arr1[i] document.write((index + 1) + " " ); } } // Driver method let arr1=[1, 2, 3, 4, 7, 9 ]; let arr2=[0, 1, 2, 1, 1, 4]; countEleLessThanOrEqual( arr1, arr2, arr1.length, arr2.length); // This code is contributed by patel2127 </script> |
PHP
<?php // php implementation of For each element // in 1st array count elements less than // or equal to it in 2nd array // function returns the index of largest // element smaller than equal to 'x' in // 'arr'. For duplicates it returns the // last index of occurrence of required // element. If no such element exits then // it returns -1. function binary_search( $arr , $l , $h , $x ) { while ( $l <= $h ) { $mid = ( floor ( $l + $h ) / 2); // if 'x' is greater than or // equal to arr[mid], then // search in arr[mid+1...h] if ( $arr [ $mid ] <= $x ) $l = $mid + 1; // else search in arr[l...mid-1] else $h = $mid - 1; } // required index return $h ; } // function to count for each element // in 1st array, elements less than or // equal to it in 2nd array function countEleLessThanOrEqual( $arr1 , $arr2 , $m , $n ) { // sort the 2nd array sort( $arr2 ); sort( $arr2 , $n ); // for each element of 1st array for ( $i = 0; $i < $m ; $i ++) { // last index of largest element // smaller than or equal to x $index = binary_search( $arr2 , 0, $n -1, $arr1 [ $i ]); // required count for the // element arr1[i] echo ( $index +1), " " ; } } // Driver program to test above $arr1 = array (1, 2, 3, 4, 7, 9); $arr2 = array (0, 1, 2, 1, 1, 4); $m = sizeof( $arr1 ) / sizeof( $arr1 [0]); $n = sizeof( $arr2 ) / sizeof( $arr2 [0]); countEleLessThanOrEqual( $arr1 , $arr2 , $m , $n ); //This code is contributed by nitin mittal. ?> |
4 5 5 6 6 6
Complexity Analysis:
- Time Complexity: O(mlogn + nlogn).
Considering arr1[] and arr2[] of sizes m and n respectively. - Space Complexity: O(1).
As no extra space is required
Another way of solving the problem is to sort the second array and use the upper_bound() inbuilt function for each value of first array.
Implementation:
C++
// C++ implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array #include <bits/stdc++.h> using namespace std; // function to count for each element in 1st array, // elements less than or equal to it in 2nd array void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // sort the 2nd array sort(arr2, arr2 + n); // for each element of 1st array for ( int i = 0; i < m; i++) { int x = upper_bound(arr2, arr2 + n, arr1[i]) - arr2; cout << x << " " ; } } // Driver program to test above int main() { int arr1[] = { 1, 2, 3, 4, 7, 9 }; int arr2[] = { 0, 1, 2, 1, 1, 4 }; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); countEleLessThanOrEqual(arr1, arr2, m, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// JAVA implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array import java.util.*; class GFG { public static int upper_bound( int arr[], int key) { int upperBound = 0 ; while (upperBound < arr.length) { // If current value is lesser than or equal to // key if (arr[upperBound] <= key) upperBound++; // This value is just greater than key else { return upperBound; } } return upperBound; } // function to count for each element in 1st array, // elements less than or equal to it in 2nd array public static void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // sort the 2nd array Arrays.sort(arr2); // for each element of 1st array for ( int i = 0 ; i < m; i++) { int x = upper_bound(arr2, arr1[i]); System.out.print(x + " " ); } } // Driver program to test above public static void main(String[] args) { int arr1[] = { 1 , 2 , 3 , 4 , 7 , 9 }; int arr2[] = { 0 , 1 , 2 , 1 , 1 , 4 }; int m = arr1.length; int n = arr2.length; countEleLessThanOrEqual(arr1, arr2, m, n); } } // This code is contributed by Taranpreet |
Python3
# Python3 implementation of For each element in 1st # array count elements less than or equal to it # in 2nd array def upper_bound(arr, key): upperBound = 0 while (upperBound < len (arr)): # If current value is lesser than or equal to # key if (arr[upperBound] < = key): upperBound + = 1 # This value is just greater than key else : return upperBound return upperBound # function to count for each element in 1st array, # elements less than or equal to it in 2nd array def countEleLessThanOrEqual(arr1, arr2, m, n): # sort the 2nd array arr2.sort() # for each element of 1st array for i in range (m): x = upper_bound(arr2, arr1[i]) print (x, end = " " ) # Driver program to test above arr1 = [ 1 , 2 , 3 , 4 , 7 , 9 ] arr2 = [ 0 , 1 , 2 , 1 , 1 , 4 ] m = len (arr1) n = len (arr2) countEleLessThanOrEqual(arr1, arr2, m, n) # This code is contributed by Abhijeet Kumar(abhijeet19403) |
C#
// C# implementation of For each element in 1st array count // elements less than or equal to it in 2nd array using System; using System.Collections; public class GFG { public static int upper_bound( int [] arr, int key) { int upperBound = 0; while (upperBound < arr.Length) { // If current value is lesser than or equal to // key if (arr[upperBound] <= key) upperBound++; // This value is just greater than key else { return upperBound; } } return upperBound; } // function to count for each element in 1st array, // elements less than or equal to it in 2nd array public static void countEleLessThanOrEqual( int [] arr1, int [] arr2, int m, int n) { // sort the 2nd array Array.Sort(arr2); // for each element of 1st array for ( int i = 0; i < m; i++) { int x = upper_bound(arr2, arr1[i]); Console.Write(x + " " ); } } static public void Main() { // Code int [] arr1 = { 1, 2, 3, 4, 7, 9 }; int [] arr2 = { 0, 1, 2, 1, 1, 4 }; int m = arr1.Length; int n = arr2.Length; countEleLessThanOrEqual(arr1, arr2, m, n); } } // This code is contributed by lokeshmvs21. |
Javascript
function upper_bound(arr, key) { let upperBound = 0; while (upperBound < arr.length) { // If current value is lesser than or equal to // key if (arr[upperBound] <= key) upperBound++; // This value is just greater than key else { return upperBound; } } return upperBound; } // function to count for each element in 1st array, // elements less than or equal to it in 2nd array function countEleLessThanOrEqual(arr1, arr2, m, n) { // sort the 2nd array arr2.sort(); // for each element of 1st array for (let i = 0; i < m; i++) { let x = upper_bound(arr2, arr1[i]); console.log(x + " " ); } } // Driver program to test above let arr1 = [ 1, 2, 3, 4, 7, 9 ]; let arr2 = [ 0, 1, 2, 1, 1, 4 ]; let m = arr1.length; let n = arr2.length; countEleLessThanOrEqual(arr1, arr2, m, n); // This code is contributed by aadityaburujwale. |
4 5 5 6 6 6
Time Complexity: O(n logn + m log n), where m and n represents the size of the given two arrays.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Another Approach: We can also use two pointers to find our solution. first, sort both the arrays. after sorting put i pointer for arr1 and j pointer for arr2 at the beginning. we will traverse over the elements of arr1 by using i pointer & inside this loop, we will go over each element of arr2 by j pointer. wherever arr2[j] <= arr1[i] we will increase j . if the condition fails print j.
Note:- this will give answer in sorted manner
C++
// C++ implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array #include <bits/stdc++.h> using namespace std; void countEleLessThanOrEqual( int arr1[], int arr2[], int m, int n) { // sorting both the arrays sort(arr1, arr1 + m); sort(arr2, arr2 + n); // pointer for arr2 int j = 0; // traversing each element of 1st array for ( int i = 0; i < m; i++) { // checking the condition for each element while (j < n && arr2[j] <= arr1[i]) j++; cout << j << " " ; } } // Driver program to test above int main() { int arr1[] = {1, 2, 3, 4, 7, 9}; int arr2[] = {0, 1, 2, 1, 1, 4}; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); countEleLessThanOrEqual(arr1, arr2, m, n); return 0; } // This code is contributed by Naveen Shah |
Java
// Java implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array import java.io.*; import java.util.*; class GFG { static void countEleLessThanOrEqual( int [] arr1, int [] arr2, int m, int n) { Arrays.sort(arr1); Arrays.sort(arr2); // pointer for arr2 int j = 0 ; // traversing each element of 1st array for ( int i = 0 ; i < m; i++) { // checking the condition for each element while (j < n && arr2[j] <= arr1[i]) j++; System.out.print(j + " " ); } } public static void main(String[] args) { int [] arr1 = { 1 , 2 , 3 , 4 , 7 , 9 }; int [] arr2 = { 0 , 1 , 2 , 1 , 1 , 4 }; int m = arr1.length; int n = arr2.length; countEleLessThanOrEqual(arr1, arr2, m, n); } } // This code is contributed by lokeshmvs21. |
Python3
# implementation of For each element in 1st # array count elements less than or equal to it # in 2nd array def countEleLessThanOrEqual(arr1, arr2, m, n): # sorting both the arrays arr1.sort() arr2.sort() # pointer for arr2 j = 0 # traversing each element of 1st array for i in range (m): # checking the condition for each element while (j < n and arr2[j] < = arr1[i]): j + = 1 print (j, end = " " ) # Driver program to test above arr1 = [ 1 , 2 , 3 , 4 , 7 , 9 ] arr2 = [ 0 , 1 , 2 , 1 , 1 , 4 ] m = len (arr1) n = len (arr2) countEleLessThanOrEqual(arr1, arr2, m, n) " This code is contributed by rajatkumargla19" |
C#
// C# implementation of For each element // in 1st array count elements less than // or equal to it in 2nd array using System; public class GFG { // function to count for each element in 1st array, // elements less than or equal to it in 2nd array static void countEleLessThanOrEqual( int [] arr1, int [] arr2, int m, int n) { // sorting both of the array Array.Sort(arr1); Array.Sort(arr2); int j = 0; // traversing the array from 0 to m-1 index for ( int i = 0; i < m; i++) { while (j < n && arr2[j] <= arr1[i]) { j++; } // printing the value of j Console.Write(j + " " ); } } // Driver method public static void Main() { int [] arr1 = { 1, 2, 3, 4, 7, 9 }; int [] arr2 = { 0, 1, 2, 1, 1, 4 }; countEleLessThanOrEqual(arr1, arr2, arr1.Length, arr2.Length); } } // This code is contributed by rajatkumargla19... |
Javascript
// JavaScript implementation of For each element in 1st // array count elements less than or equal to it // in 2nd array function countEleLessThanOrEqual(arr1, arr2, m, n){ arr1.sort(); arr2.sort(); // pointer for arr2 let j = 0; // traversing each element of 1st array for (let i = 0; i < m; i++) { // checking the condition for each element while (j < n && arr2[j] <= arr1[i]) j++; console.log(j + " " ); } } let arr1 = [ 1, 2, 3, 4, 7, 9 ]; let arr2 = [ 0, 1, 2, 1, 1, 4 ]; let m = arr1.length; let n = arr2.length; countEleLessThanOrEqual(arr1, arr2, m, n); // This code is contributed by lokeshmvs21. |
4 5 5 6 6 6
Time Complexity: O(nlogn + mlogm)
Auxiliary Space: O(1)
Another Approach: prefix-sum technique and hashing
Follow the steps to implement the approach:
- Create a hash table to store the frequency of elements in arr2. Initialize the hash table with zeros.
- Iterate through arr2 and update the frequency of each element in the hash table.
- Create a prefix sum array prefixSum of size 100010 (maximum element value + 10). Initialize prefixSum[0] with the frequency of the first element in arr2.
- Calculate the prefix sum array by adding the current frequency with the previous prefix sum.
- Iterate through arr1. For each element arr1[i], access prefixSum[arr1[i]] to get the count of elements less than or equal to arr1[i] in arr2.
- Store the counts in a result array or directly print them.
Below is the implementation:
C++
#include <iostream> #include <vector> using namespace std; // Function to count elements less than or equal to each // element in arr1[] void countElements( int arr1[], int arr2[], int m, int n) { int result[m]; int frequency[100010] = { 0 }; // Hash table to store frequency of elements // Calculate frequency of elements in arr2 for ( int i = 0; i < n; ++i) { frequency[arr2[i]]++; } int prefixSum[100010]; prefixSum[0] = frequency[0]; // Calculate prefix sum array for ( int i = 1; i < 100010; ++i) { prefixSum[i] = prefixSum[i - 1] + frequency[i]; } // Count elements less than or equal to arr1[i] for ( int i = 0; i < m; ++i) { result[i] = prefixSum[arr1[i]]; } // print the counts for ( int i = 0; i < m; ++i) { cout << result[i] << " " ; } } // Driver Code int main() { int arr1[] = { 1, 2, 3, 4, 7, 9 }; int arr2[] = { 0, 1, 2, 1, 1, 4 }; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); // Function Called countElements(arr1, arr2, m, n); return 0; } // This code is contributed by Veerendra_Singh_Rajpoot |
Java
import java.util.Arrays; public class GFG { // Function to count elements less than or equal to each // element in arr1[] public static void countElements( int [] arr1, int [] arr2, int m, int n) { // Create an array to store the result int [] result = new int [m]; // Create an array to store the frequency of // elements in arr2 int [] frequency = new int [ 100010 ]; // Calculate the frequency of each element in arr2 for ( int i = 0 ; i < n; ++i) { frequency[arr2[i]]++; } // Calculate the prefix sum of the frequency array int [] prefixSum = new int [ 100010 ]; prefixSum[ 0 ] = frequency[ 0 ]; for ( int i = 1 ; i < 100010 ; ++i) { prefixSum[i] = prefixSum[i - 1 ] + frequency[i]; } // Calculate the count of elements in arr1 using the // prefix sum array for ( int i = 0 ; i < m; ++i) { result[i] = prefixSum[arr1[i]]; } // Print the count of elements in arr1 for ( int i = 0 ; i < m; ++i) { System.out.print(result[i] + " " ); } } // Driver Codea public static void main(String[] args) { int [] arr1 = { 1 , 2 , 3 , 4 , 7 , 9 }; int [] arr2 = { 0 , 1 , 2 , 1 , 1 , 4 }; int m = arr1.length; int n = arr2.length; // Call the countElements function countElements(arr1, arr2, m, n); } } // This code is contributed by Veerendra_Singh_Rajpoot |
Python3
# Function to count elements less than or equal to each # element in arr1[] def countElements(arr1, arr2, m, n): result = [ 0 ] * m frequency = [ 0 ] * 100010 # Hash table to store frequency of elements # Calculate frequency of elements in arr2 for i in range (n): frequency[arr2[i]] + = 1 prefixSum = [ 0 ] * 100010 prefixSum[ 0 ] = frequency[ 0 ] # Calculate prefix sum array for i in range ( 1 , 100010 ): prefixSum[i] = prefixSum[i - 1 ] + frequency[i] # Count elements less than or equal to arr1[i] for i in range (m): result[i] = prefixSum[arr1[i]] # Print the counts for i in range (m): print (result[i], end = " " ) print () # Driver Code if __name__ = = "__main__" : arr1 = [ 1 , 2 , 3 , 4 , 7 , 9 ] arr2 = [ 0 , 1 , 2 , 1 , 1 , 4 ] m = len (arr1) n = len (arr2) # Function Call countElements(arr1, arr2, m, n) # This code is contributed by akshitaguprzj3 |
C#
using System; public class GFG { // Function to count elements less than or equal to each // element in arr1[] public static void CountElements( int [] arr1, int [] arr2, int m, int n) { int [] result = new int [m]; int [] frequency = new int [100010]; // Hash table to store // frequency of elements // Calculate frequency of elements in arr2 for ( int i = 0; i < n; ++i) { frequency[arr2[i]]++; } int [] prefixSum = new int [100010]; prefixSum[0] = frequency[0]; // Calculate prefix sum array for ( int i = 1; i < 100010; ++i) { prefixSum[i] = prefixSum[i - 1] + frequency[i]; } // Count elements less than or equal to arr1[i] for ( int i = 0; i < m; ++i) { result[i] = prefixSum[arr1[i]]; } // print the counts for ( int i = 0; i < m; ++i) { Console.Write(result[i] + " " ); } } // Driver Code public static void Main( string [] args) { int [] arr1 = { 1, 2, 3, 4, 7, 9 }; int [] arr2 = { 0, 1, 2, 1, 1, 4 }; int m = arr1.Length; int n = arr2.Length; // Function Called CountElements(arr1, arr2, m, n); } } // This code is contributed by rambabuguphka |
Javascript
// Function to count elements less than or equal to each element in arr1[] function countElements(arr1, arr2, m, n) { let result = []; let frequency = new Array(100010).fill(0); // Hash table to store frequency of elements // Calculate frequency of elements in arr2 for (let i = 0; i < n; ++i) { frequency[arr2[i]]++; } let prefixSum = []; prefixSum[0] = frequency[0]; // Calculate prefix sum array for (let i = 1; i < 100010; ++i) { prefixSum[i] = prefixSum[i - 1] + frequency[i]; } // Count elements less than or equal to arr1[i] for (let i = 0; i < m; ++i) { result[i] = prefixSum[arr1[i]]; } // print the counts for (let i = 0; i < m; ++i) { console.log(result[i] + " " ); } } // Driver Code let arr1 = [1, 2, 3, 4, 7, 9]; let arr2 = [0, 1, 2, 1, 1, 4]; let m = arr1.length; let n = arr2.length; // Function Called countElements(arr1, arr2, m, n); |
4 5 5 6 6 6
Time Complexity: O(n + m)
Auxiliary Space: O(m)