Pairs with Less Than K Difference – Java Solution Explained

Sandhiya Priya
5h
79
0
0

Article

Problem Statement

Given an array of positive integers arr[] and an integer k, count the total number of pairs whose absolute difference is strictly less than k.

Note

(i, j) and (j, i) are considered the same pair.
Count each pair only once.

Example 1

Input

arr = [1, 10, 4, 2]
k = 3

Output

Explanation

Possible pairs:

Pair	Difference	Valid?
(1, 10)	9	NO
(1, 4)	3	NO (must be less than 3)
(1, 2)	1	YES
(10, 4)	6	NO
(10, 2)	8	NO
(4, 2)	2	YES

Total valid pairs = 2

Example 2

Input

arr = [2, 3, 4]
k = 5

Output

Explanation

Valid pairs:

(2, 3)
(2, 4)
(3, 4)

Answer = 3

Brute Force Approach

The simplest approach is to check every pair.

int count = 0;

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (Math.abs(arr[i] - arr[j]) < k) {
            count++;
        }
    }
}

Time Complexity

O(n²)

If:

n = 100000

this approach becomes extremely slow.

Therefore, we need a better solution.

Optimized Approach

We use:

Sorting
Two Pointers (Sliding Window)

Why Sorting?

Suppose the array is:

1 10 4 2

After sorting:

1 2 4 10

Now the numbers are arranged in increasing order.

This gives an important property:

arr[right] - arr[left]

is always the absolute difference because:

arr[right] >= arr[left]

So we no longer need Math.abs().

Idea Behind Two Pointers

Suppose the sorted array is:

1 2 4 10

Initially:

Difference:

2 - 1 = 1

1 < 3

This pair is valid.

Since the array is sorted, there are:

right - left

1 - 0 = 1

new valid pair.

Move the right pointer.

Now:

Difference:

4 - 1 = 3

Not less than 3.

Move the left pointer.

Difference:

4 - 2 = 2

Valid.

Now:

right - left

2 - 1 = 1

One more pair.

Move the right pointer.

Now:

Difference:

10 - 2 = 8

Too large.

Move the left pointer repeatedly until the difference becomes smaller.

Eventually, the loop ends.

Total valid pairs = 2.

Visualization

Sorted Array

1   2   4   10

L
R

Valid

↓

L
    R

Invalid

↓

    L
    R

Valid

↓

    L
         R

Invalid

↓

End

Complete Code

import java.util.Arrays;

class Solution {

    public static int countPairs(int arr[], int k) {

        Arrays.sort(arr);

        int n = arr.length;

        int left = 0;
        int right = 1;

        int count = 0;

        while (right < n) {

            if (arr[right] - arr[left] < k) {

                count += (right - left);

                right++;
            }
            else {

                left++;

                if (left == right)
                    right++;
            }
        }

        return count;
    }
}

Code Explanation (Line by Line)

Step 1

Arrays.sort(arr);

Sort the array.

Example:

Before:

1 10 4 2

After:

1 2 4 10

Time Complexity:

O(n log n)

Step 2

int n = arr.length;

Store the array size.

Step 3

int left = 0;
int right = 1;

Initialize the two pointers.

L R

1 2 4 10

Step 4

int count = 0;

Stores the total valid pairs.

Step 5

while (right < n)

Keep checking until the right pointer reaches the end of the array.

Step 6

if (arr[right] - arr[left] < k)

Check whether the current difference is valid.

Example:

2 - 1 = 1

1 < 3

Valid

Step 7

count += (right - left);

This is the most important part of the algorithm.

Why?

Suppose the sorted array is:

1 2 3 4

Pointers:

L      R

1 2 3 4

Here:

4 - 1 = 3

If this difference is less than k, then all elements between left and right also satisfy the condition because the array is sorted.

The following pairs are also valid:

(2, 4)
(3, 4)

So instead of checking each pair individually, we directly add:

right - left

This counts all new valid pairs ending at right.

Example

left = 1
right = 4

Indices:

0 1 2 3 4

right - left

4 - 1

= 3

Three new pairs are counted.

This optimization avoids nested loops and makes the algorithm efficient.

Step 8

right++;

Expand the window to consider the next element.

Step 9

else

If the difference is too large, shrink the window.

Step 10

left++;

Move the left pointer forward to reduce the difference.

Step 11

if (left == right)
    right++;

Ensure the two pointers never point to the same element.

This prevents comparing an element with itself.

Step 12

return count;

Return the total number of valid pairs.

Dry Run

Input

arr = [1, 10, 4, 2]

k = 3

Sorted array:

1 2 4 10

Left	Right	Difference	Count Added	Total
0	1	1	1	1
0	2	3	0 (move left)	1
1	2	2	1	2
1	3	8	0 (move left)	2
2	3	6	0 (move left)	2
3	3	—	End	2

Final Answer:

Complexity Analysis

Time Complexity

Sorting: O(n log n)
Two-pointer traversal: O(n)

Overall:

O(n log n)

Space Complexity

Only a few variables are used:

left
right
count
n

Auxiliary Space:

O(1)

Key Takeaways

A brute-force solution checks every pair and takes O(n²) time.
Sorting allows us to compare differences directly without using Math.abs().
The two-pointer technique scans the array only once after sorting.
The expression count += (right - left) counts multiple valid pairs at once, making the solution efficient.

Summary

By sorting the array and applying the two-pointer technique, we can efficiently count all pairs whose absolute difference is strictly less than k. Sorting ensures that arr[right] - arr[left] represents the absolute difference, while the expression count += (right - left) counts multiple valid pairs in a single step. This approach reduces the overall complexity from O(n²) to O(n log n), making it suitable for large input sizes.