Pairs with certain difference

Intuition

Since each value can be used at most once, pairing larger numbers first is beneficial when valid. After sorting, if two adjacent large numbers differ by less than k, taking that pair greedily is optimal because skipping it cannot produce a better contribution from those elements later.

Algorithm

1Sort the array in non-decreasing order.
2Traverse from right to left with index i = n-1.
3If i-1 exists and arr[i] - arr[i-1] < k, include this pair in sum and decrement i by 2.
4Otherwise, decrement i by 1 and continue.
5Return the accumulated sum of chosen pair elements.

Example Walkthrough

Input: arr = [3, 5, 10, 15, 17, 12, 9], k = 4

1.Sort -> [3, 5, 9, 10, 12, 15, 17].
2.Check (17,15): diff=2<4, take sum += 32.
3.Check (12,10): diff=2<4, take sum += 22.
4.Check (9,5): diff=4 not <4, skip 9.
5.Check (5,3): diff=2<4, take sum += 8.

Output: 62

Common Pitfalls

•Condition is strictly less than k, not less than or equal to k.
•Without sorting, greedy adjacency pairing is invalid.
•After taking a pair, move two steps left so elements are not reused.

Pairs with certain difference.java

Java


import java.util.*;

// Approach: Greedy after sorting. Pair adjacent elements from right to left when their difference is less than k.
// Taking the largest valid pair first is optimal, because each element can be used at most once and larger values contribute more to the sum.
// Time: O(n log n) Space: O(1) extra (ignoring sort stack)

class Solution {

    public int sumDiffPairs(int[] arr, int k) {
        Arrays.sort(arr);
        int n = arr.length;

        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {

            if (i - 1 >= 0 && arr[i] - arr[i - 1] < k) {
                sum += (arr[i] + arr[i - 1]);
                i--;
            }
        }
        return sum;
    }
}

Was this solution helpful?