Counting elements in two arrays

JavaView on GFG

Intuition

For each element in array A, count elements in array B that are less than or equal to it.

Algorithm

1Sort B. For each element in A: binary search upper_bound in B gives count.

Common Pitfalls

•Sort B once, then O(log n) per query. Total O((m+n) log n). Output count array.

Counting elements in two arrays.java

Java

// Approach: Sort array B. For each element in A, binary search in B to count elements <= that value.
// Time: O((n+m) log m) Space: O(m)
import java.util.*;

class Solution {
    public static ArrayList<Integer> countLessEq(int a[], int b[]) {
        ArrayList<Integer> ans = new ArrayList<>();
        Arrays.sort(b);
        for (int i = 0; i < a.length; i++) {
            int num = a[i];
            int small = binarySearch(num, b);
            ans.add(small);
        }
        return ans;
    }

    private static int binarySearch(int target, int[] b) {
        int n = b.length;
        int start = 0;
        int end = n - 1;
        int ans = 0;

        while (start <= end) {

            int mid = start + (end - start) / 2;
            if (b[mid] <= target) {
                ans = Math.max(ans, mid + 1);
                start = mid + 1;
            } else
                end = mid - 1;
        }
        return ans;
    }
}

Was this solution helpful?