Problem

Given two unsorted arrays arr1[] and arr2[], which may contain duplicates, count the number of elements in arr2 that are less than or equal to each element in arr1.

Examples

Example 1:

Input: arr1 = [4, 2, 8], arr2 = [5, 1, 3, 7, 9, 2]
Output: [3, 2, 5]
Explanation: 
For arr1[0] = 4, there are 3 elements in arr2 less than or equal to 4 (i.e., 1, 3, 2).
For arr1[1] = 2, there are 2 elements in arr2 less than or equal to 2 (i.e., 1, 2).
For arr1[2] = 8, there are 5 elements in arr2 less than or equal to 8 (i.e., 5, 1, 3, 7, 2).

Example 2:

Input: arr1 = [10, 5], arr2 = [6, 3, 8, 10, 15]
Output: [4, 2]
Explanation: 
For arr1[0] = 10, there are 4 elements in arr2 less than or equal to 10 (i.e., 6, 3, 8, 10).
For arr1[1] = 5, there are 2 elements in arr2 less than or equal to 5 (i.e., 3, 5).

Solution

Method 1 - Naive

Utilize two nested loops: the outer loop iterates over the elements of arr1[] and the inner loop iterates over the elements of arr2[]. For each element in arr1[], count the number of elements in arr2[] that are less than or equal to it. The time complexity of this approach is (O(m * n)), where arr1[] and arr2[] have sizes m and n, respectively.

Method 2 - Binary Search

Here is the approach:

  1. Sort arr2: Start by sorting arr2 to use an efficient searching algorithm.
  2. Binary Search: For each element in arr1, use binary search to find the number of elements in arr2 that are less than or equal to it.
  3. Count Elements: The position found by the binary search gives the count of the elements less than or equal to the current element.

Code

Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<Integer> countElements(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        List<Integer> result = new ArrayList<>();

        for (int num : arr1) {
            int count = findCount(arr2, num);
            result.add(count);
        }

        return result;
    }

    private int findCount(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}
Python
import bisect

def count_elements(arr1, arr2):
    arr2.sort()
    result = []
    for num in arr1:
        count = bisect.bisect_right(arr2, num)
        result.append(count)
    return result


# Example usage:
arr1 = [4, 2, 8]
arr2 = [5, 1, 3, 7, 9, 2]
print(count_elements(arr1, arr2))  # Output: [3, 2, 5]

arr1_2 = [10, 5]
arr2_2 = [6, 3, 8, 10, 15]
print(count_elements(arr1_2, arr2_2))  # Output: [4, 2]

Complexity

  • ⏰ Time complexity: O(m log m + n log m)
    • Sorting arr2 takes O(m log m), where (m) is the length of arr2.
    • For each element in arr1, performing a binary search takes O(log m), resulting in O(n log m) for all elements ((n) being the length of arr1).
  • 🧺 Space complexity: O(1)