Pairs with Less Than K Diff

Problem Overview

Count pairs of indices whose values differ by strictly less than k.

Intuition

Count pairs of indices whose values differ by strictly less than k. After sorting, larger values sit to the right, so for each right endpoint the valid left partners form a contiguous prefix of the window ending at right. Maintain the leftmost index still within distance k-1 of arr[right] and add how many indices sit between left and right.

Algorithm

1If n < 2 return 0. Sort arr ascending.
2left = 0. For right = 1..n-1:
3 while arr[right] - arr[left] >= k: left++.
4 count += right - left.
5Return count.

Example Walkthrough

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

1. Sorted: [1, 2, 4, 10].
2. Pairs with diff < 3: (1,2) and (2,4). (1,4)=3 is not less than 3.
3. Two-pointer total is 2.

Output: 2

Common Pitfalls

• Difference must be strictly less than k - equality does not count.
• left only moves forward, so the scan after sorting is O(n).
• Count index pairs; after sorting this is value pairs at distinct positions.
• Return 0 immediately when fewer than two elements exist.

Pairs with Less Than K Diff.java

Java

// Approach: Count unordered index pairs whose values differ by less than k.
// Sort, then two pointers: for each right, advance left while
// arr[right] - arr[left] >= k. Every index in [left, right) forms a valid pair
// with right, so add (right - left).
// Time: O(n log n) Space: O(1) extra (ignoring sort)
import java.util.*;

class Solution {

    public static int countPairs(int arr[], int k) {
        int n = arr.length;
        if (n < 2) {
            return 0;
        }

        Arrays.sort(arr);
        int count = 0;
        int left = 0;

        for (int right = 1; right < n; right++) {
            while (arr[right] - arr[left] >= k) {
                left++;
            }
            count += (right - left);
        }

        return count;
    }
}

Was this solution helpful?