Dominant Pairs — Sorting and Two-Pointer Approach in Java

1. Problem Statement

Given an even-sized integer array, divide it into two equal halves.

A pair of indices (i, j) is called a dominant pair if:

i belongs to the first half.
j belongs to the second half.
arr[i] >= 5 * arr[j]

We need to count the total number of dominant pairs.

Example

arr = [10, 2, 2, 1]

The array is divided into:

First half:  [10, 2]
Second half: [2, 1]

Now check the possible pairs:

10 >= 5 * 2
10 >= 5 * 1

So there are 2 dominant pairs.

Therefore:

Output = 2

2. Understanding the Important Observation

Suppose we have:

First half:  [10, 8, 2]
Second half: [1, 1, 2]

We need to count pairs satisfying:

firstElement >= 5 * secondElement

A brute-force solution would compare every element from the first half with every element from the second half.

For n elements, each half contains n/2 elements.

Therefore, brute force takes:

O(n²)

But the expected complexity is:

O(n log n)

So we need something better.

The key idea is:

Sort both halves and use two pointers.

3. Why Sorting Helps

Consider:

First half:  [10, 8, 2]
Second half: [1, 1, 2]

Sort both halves:

First half:  [2, 8, 10]
Second half: [1, 1, 2]

Now consider 8.

We need:

8 >= 5 * secondElement

Therefore:

secondElement <= 8 / 5

The elements 1 and 1 satisfy the condition.

So 8 gives us 2 dominant pairs.

Now consider 10:

10 >= 5 * 1
10 >= 5 * 1
10 >= 5 * 2

All three elements satisfy the condition.

So 10 gives us 3 pairs.

Total:

2 + 3 = 5

4. Two-Pointer Technique

After sorting:

First half:  [2, 8, 10]
Second half: [1, 1, 2]

We maintain a pointer j for the second half.

Initially:

j = half

For every element in the first half, move j while:

arr[i] >= 5 * arr[j]

Every element before j is a valid partner.

For example, when:

arr[i] = 8

we check:

8 >= 5 * 1   → true
8 >= 5 * 1   → true
8 >= 5 * 2   → false

Therefore, there are:

valid elements in the second half.

5. Why Doesn't j Move Backward?

This is the most important part of the solution.

Both halves are sorted.

Suppose 8 can form dominant pairs with:

1, 1

Now we move to 10.

Because:

10 >= 8

anything that was valid for 8 will also be valid for 10.

Therefore, there is no need to move j backward.

This makes the two-pointer approach efficient.

6. Java Implementation

import java.util.*;

class Solution {
    public int dominantPairs(int[] arr) {
        int n = arr.length;
        int half = n / 2;

        // Sort the first half
        Arrays.sort(arr, 0, half);

        // Sort the second half
        Arrays.sort(arr, half, n);

        int j = half;
        int count = 0;

        // Process every element of the first half
        for (int i = 0; i < half; i++) {

            // Find all valid elements in the second half
            while (j < n && (long) arr[i] >= 5L * arr[j]) {
                j++;
            }

            // All elements from half to j-1 are valid
            count += j - half;
        }

        return count;
    }
}

7. Code Explanation

Step 1: Find the middle

int n = arr.length;
int half = n / 2;

For:

arr = [10, 8, 2, 1, 1, 2]

we have:

n = 6
half = 3

So:

First half  → indices 0, 1, 2
Second half → indices 3, 4, 5

Step 2: Sort Both Halves

Arrays.sort(arr, 0, half);
Arrays.sort(arr, half, n);

This sorts each half independently.

For example:

Before:

[10, 8, 2, 1, 1, 2]

After:

[2, 8, 10, 1, 1, 2]

Notice that we do not sort the entire array.

We only sort:

[0, half)

and:

[half, n)

because the first and second halves must remain separate.

8. Initialize the Second Pointer

int j = half;

j starts at the beginning of the second half.

For:

[2, 8, 10, 1, 1, 2]

we have:

         j
         ↓
[2, 8, 10, 1, 1, 2]
          ↑
        half

9. Process the First Half

for (int i = 0; i < half; i++) {

We examine every element from the first half.

For every arr[i], we want to find how many elements in the second half satisfy:

arr[i] >= 5 * arr[j]

10. Move the Second Pointer

while (j < n && (long) arr[i] >= 5L * arr[j]) {
    j++;
}

This is the core of the algorithm.

Suppose:

arr[i] = 10

and the second half is:

[1, 1, 2]

We check:

10 >= 5 * 1  → true
10 >= 5 * 1  → true
10 >= 5 * 2  → true

So j moves past all three elements.

11. Count Valid Pairs

After the while loop:

count += j - half;

Why?

Because the second half starts at index half.

If:

half = 3
j = 5

then valid elements are:

indices 3 and 4

Number of elements:

5 - 3 = 2

Therefore, the current arr[i] creates 2 dominant pairs.

12. Complete Dry Run

Consider:

arr = [10, 8, 2, 1, 1, 2]

After sorting each half:

First half:  [2, 8, 10]
Second half: [1, 1, 2]

`i = 0`

arr[i] = 2

Check:

2 >= 5 * 1
2 >= 5

False.

So:

j = 3
count = 0

`i = 1`

arr[i] = 8

Check:

8 >= 5 * 1 → true
8 >= 5 * 1 → true
8 >= 5 * 2 → false

So:

j = 5

Number of valid elements:

5 - 3 = 2

Therefore:

count = 2

`i = 2`

arr[i] = 10

Now j is already at index 5.

Check:

10 >= 5 * 2
10 >= 10

True.

Move j:

j = 6

Now:

count += 6 - 3
count += 3

Therefore:

count = 5

Final answer:

13. Why Do We Use long?

The condition is:

arr[i] >= 5 * arr[j]

It is safer to write:

(long) arr[i] >= 5L * arr[j]

This makes the multiplication happen using long.

So our comparison becomes:

(long) arr[i] >= 5L * arr[j]

This is a good habit whenever multiplication could potentially cause integer overflow.

14. Why Is the Algorithm O(n log n)?

We sort the two halves.

Sorting takes:

O(n log n)

Then the two-pointer traversal takes:

O(n)

Why is the traversal only O(n)?

Because:

moves from left to right once, and:

also only moves from left to right.

j never moves backward.

Therefore:

O(n log n) + O(n)

becomes:

O(n log n)

15. Auxiliary Space

The algorithm uses only a few variables:

int n;
int half;
int i;
int j;
int count;

Arrays.sort() for primitive int[] uses an in-place sorting algorithm, so the algorithm does not create another array for the two halves.

Thus the auxiliary space is effectively:

O(1)

apart from the sorting implementation's internal stack requirements.

16. Brute Force vs Two Pointers

Brute Force

We could write:

for (int i = 0; i < half; i++) {
    for (int j = half; j < n; j++) {
        if (arr[i] >= 5 * arr[j]) {
            count++;
        }
    }
}

This is easy to understand, but its complexity is:

O(n²)

For n = 10,000, that can mean roughly 25 million cross-half comparisons.

Optimized Approach

Sort both halves and use two pointers:

O(n log n)

This is much more efficient for the given constraints.

17. Important Pattern to Remember

This problem teaches a useful general pattern:

When you need to count pairs satisfying an inequality, consider sorting and using two pointers.

Typical conditions include:

A[i] >= k * B[j]
A[i] + B[j] <= target
A[i] - B[j] > target
A[i] <= B[j]

Sorting can turn a nested-loop pair-counting problem into a linear two-pointer traversal.

18. Final Takeaway

The solution has three main steps:

1. Split the array into two halves.
2. Sort both halves independently.
3. Use two pointers to count valid pairs.

The most important insight is that sorting lets us reuse the position of the second pointer instead of checking every possible pair.

Final complexity:

Time:  O(n log n)
Space: O(1) auxiliary

And the Java solution is:

import java.util.*;

class Solution {
    public int dominantPairs(int[] arr) {
        int n = arr.length;
        int half = n / 2;

        Arrays.sort(arr, 0, half);
        Arrays.sort(arr, half, n);

        int j = half;
        int count = 0;

        for (int i = 0; i < half; i++) {
            while (j < n && (long) arr[i] >= 5L * arr[j]) {
                j++;
            }

            count += j - half;
        }

        return count;
    }
}