Dominant Pairs

Problem Overview

A dominant pair mixes one value from the left half with one from the right half so the left value is at least five times the right.

Intuition

A dominant pair mixes one value from the left half with one from the right half so the left value is at least five times the right. After sorting each half, larger left values only unlock more right partners, so a single advancing pointer counts them all.

Algorithm

1Let mid = n / 2 and sort arr[0..mid) and arr[mid..n) ascending.
2Start right at mid.
3For each left index from 0 to mid-1, advance right while arr[left] >= 5 * arr[right].
4Add (right - mid) to the answer; those right positions all work with the current left.
5Return the total count.

Example Walkthrough

Input: arr = [10, 5, 2, 1] so halves [10,5] and [2,1]

1. After sorting halves stay [5,10] and [1,2].
2. left = 5 reaches both rights because 5 >= 5*1 and 5 >= 5*2 is false only for 2 after 1 counts.
3. left = 10 covers both rights, adding the running total of valid partners.

Output: 3

Common Pitfalls

• Only cross-half pairs count; indices must keep i < n/2 and j >= n/2.
• Multiply with 64-bit values so 5 * arr[j] does not overflow.
• Sorting each half separately is fine because relative order inside a half does not matter for the count.
• The right pointer never moves backward; restarting it would waste work.

Dominant Pairs.java

Java

// Approach: Count pairs (i, j) with i in [0, n/2), j in [n/2, n) and
// arr[i] >= 5 * arr[j]. Sort each half ascending, then two pointers: as left
// grows, right only advances, so each second-half index is visited once.
// Complexity: O(n log n) time, O(1) extra space (in-place half sorts).
import java.util.*;

class Solution {
    public int dominantPairs(int[] arr) {
        int n = arr.length;
        int mid = n / 2;
        Arrays.sort(arr, 0, mid);
        Arrays.sort(arr, mid, n);

        int count = 0;
        int right = mid;
        for (int left = 0; left < mid; left++) {
            while (right < n && (long) arr[left] >= 5L * arr[right])
                right++;
            count += right - mid;
        }
        return count;
    }
}

Was this solution helpful?