LeetCode 1885: Count Pairs in Two Arrays Solution

Master LeetCode problem 1885 (Count Pairs in Two Arrays), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1885. Count Pairs in Two Arrays

Medium

Array Two Pointers Binary Search Sorting

Problem Explanation

Explanation:

Given two arrays nums1 and nums2, we need to count the number of pairs (i, j) such that nums1[i] > nums2[j] for all 0 <= i < nums1.length and 0 <= j < nums2.length.

Algorithmic Idea:

Sort both arrays nums1 and nums2.
For each element num in nums1, find the index idx in nums2 such that nums2[idx] > num.
The count of pairs for this num will be nums2.length - idx.
Sum up the counts for all elements in nums1.

Time Complexity:

The time complexity of this approach is O(N log N + M log M), where N is the size of nums1 and M is the size of nums2.

Space Complexity:

The space complexity is O(1) as we are not using any extra space other than a few variables.

: :

Solution Code

import java.util.Arrays;

class Solution {
    public int countPairs(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int count = 0;
        for (int num : nums1) {
            int idx = binarySearch(nums2, num);
            count += nums2.length - idx;
        }
        
        return count;
    }
    
    private int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1885 (Count Pairs in Two Arrays)?

This page provides optimized solutions for LeetCode problem 1885 (Count Pairs in Two Arrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1885 (Count Pairs in Two Arrays)?

The time complexity for LeetCode 1885 (Count Pairs in Two Arrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1885 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1885 in Java, C++, or Python.

Back to LeetCode Solutions