Pairs with Less Than K Difference – Java Solution Explained

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

Final Answer:

2

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.