Number of pairs

JavaView on GFG

Intuition

Count pairs (i,j) where i < j. If array values can repeat, count using arithmetic or hashmap.

Algorithm

1For distinct pairs: n*(n-1)/2. For pairs with constraint (like arr[i] < arr[j]): sort + binary search or BIT.

Common Pitfalls

•Problem-specific. For all pairs i<j: n*(n-1)/2. For pairs with value constraint: count inversions or use BIT.

Number of pairs.java

Java

// Approach: Sort. For each element use binary search to count valid partners satisfying the constraint.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    // Function to count number of pairs such that x^y is greater than y^x.
    public long countPairs(int x[], int y[], int m, int n) {
        int zeros = 0, one = 0, three = 0, four = 0, two = 0;
        Arrays.sort(x);
        Arrays.sort(y);

        for (int i = 0; i < n; i++) {
            if (y[i] == 0)
                zeros++;
            if (y[i] == 1)
                one++;
            if (y[i] == 3)
                three++;
            if (y[i] == 4)
                four++;
            if (y[i] == 2)
                two++;
        }

        // traversing x elements
        long ans = 0;
        for (int i = 0; i < m; i++) {
            if (x[i] == 0) {
                continue;
            } else if (x[i] == 1) {
                ans += zeros;
            } else if (x[i] == 2) {
                int index = getIndex(y, n, 2);
                if (index != -1) {
                    ans += n - index;
                }
                ans -= three;
                ans -= four;
                ans += one + zeros;
            } else {
                int index = getIndex(y, n, x[i]);
                if (index != -1) {
                    ans += n - index;
                }
                ans += one + zeros;
                if (x[i] == 3) {
                    ans += two;
                }
            }
        }
        return ans;
    }

    int getIndex(int y[], int n, int ele) {

        int low = 0;
        int high = n - 1;
        int ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (y[mid] > ele) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}

Was this solution helpful?