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:

We need to count the total number of dominant pairs.

Example

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

The array is divided into:

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

Now check the possible pairs:

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

So there are 2 dominant pairs.

Therefore:

Code
Output = 2
2. Understanding the Important Observation

Suppose we have:

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

We need to count pairs satisfying:

Code
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:

Code
O(n²)

But the expected complexity is:

Code
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:

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

Sort both halves:

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

Now consider 8.

We need:

Code
8 >= 5 * secondElement

Therefore:

Code
secondElement <= 8 / 5

The elements 1 and 1 satisfy the condition.

So 8 gives us 2 dominant pairs.

Now consider 10:

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

All three elements satisfy the condition.

So 10 gives us 3 pairs.

Total:

Code
2 + 3 = 5
4. Two-Pointer Technique

After sorting:

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

We maintain a pointer j for the second half.

Initially:

Code
j = half

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

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

Every element before j is a valid partner.

For example, when:

Code
arr[i] = 8

we check:

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

Therefore, there are:

Code
2

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:

Code
1, 1

Now we move to 10.

Because:

Code
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
Java
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

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

For:

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

we have:

Code
n = 6
half = 3

So:

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

Step 2: Sort Both Halves

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

This sorts each half independently.

For example:

Code
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:

Code
[0, half)

and:

Code
[half, n)

because the first and second halves must remain separate.

8. Initialize the Second Pointer
Java
int j = half;

j starts at the beginning of the second half.

For:

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

we have:

Code
         j
         ↓
[2, 8, 10, 1, 1, 2]
          ↑
        half
9. Process the First Half
Java
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:

Code
arr[i] >= 5 * arr[j]
10. Move the Second Pointer
Java
while (j < n && (long) arr[i] >= 5L * arr[j]) {
    j++;
}

This is the core of the algorithm.

Suppose:

Code
arr[i] = 10

and the second half is:

Code
[1, 1, 2]

We check:

Code
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:

Java
count += j - half;

Why?

Because the second half starts at index half.

If:

Code
half = 3
j = 5

then valid elements are:

Code
indices 3 and 4

Number of elements:

Code
5 - 3 = 2

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

12. Complete Dry Run

Consider:

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

After sorting each half:

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

i = 0

Code
arr[i] = 2

Check:

Code
2 >= 5 * 1
2 >= 5

False.

So:

Code
j = 3
count = 0

i = 1

Code
arr[i] = 8

Check:

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

So:

Code
j = 5

Number of valid elements:

Code
5 - 3 = 2

Therefore:

Code
count = 2

i = 2

Code
arr[i] = 10

Now j is already at index 5.

Check:

Code
10 >= 5 * 2
10 >= 10

True.

Move j:

Code
j = 6

Now:

Code
count += 6 - 3
count += 3

Therefore:

Code
count = 5

Final answer:

Code
5
13. Why Do We Use long?

The condition is:

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

It is safer to write:

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

This makes the multiplication happen using long.

So our comparison becomes:

Java
(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:

Code
O(n log n)

Then the two-pointer traversal takes:

Code
O(n)

Why is the traversal only O(n)?

Because:

Code
i

moves from left to right once, and:

Code
j

also only moves from left to right.

j never moves backward.

Therefore:

Code
O(n log n) + O(n)

becomes:

Code
O(n log n)
15. Auxiliary Space

The algorithm uses only a few variables:

Java
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:

Code
O(1)

apart from the sorting implementation's internal stack requirements.

16. Brute Force vs Two Pointers

Brute Force

We could write:

Java
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:

Code
O(n²)

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

Optimized Approach

Sort both halves and use two pointers:

Code
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:

Code
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:

Code
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:

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

And the Java solution is:

Java
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;
    }
}