Maximum sum of pairs with specific difference

Problem Statement

Given an array of integers and a number k, find the maximum possible sum of disjoint pairs where the difference between elements of each pair is at most k. Each element can be part of at most one pair.

Example:

• Input: arr = [3, 5, 10, 15, 17, 12, 9], k = 4
• Output: 62 (Pairs: (3,5), (10,12), (15,17) → sum = 8 + 22 + 32 = 62)

Noob-Friendly Explanation

Imagine you have a group of kids and you want to pair them up for a three-legged race. The rule is that kids in a pair must have similar heights (differ by at most k). Each kid can only be in one pair. You want the total combined height of all paired kids to be as large as possible. Some kids might be left unpaired — that's fine!

Approach 1: Brute Force

Intuition

Try all possible ways to form pairs from the array. For each valid pairing (where the difference is at most k), compute the sum and track the maximum.

Algorithm

1. Sort the array.
2. Use recursion to try pairing or not pairing each element.
3. Track the maximum sum of all valid pairings.

class Solution {
    public static int maxSumBrute(int[] arr, int k) {
        java.util.Arrays.sort(arr);
        return solve(arr, arr.length - 1, k);
    }

    private static int solve(int[] arr, int index, int k) {
        if (index <= 0) return 0;

        // Don't pair arr[index]
        int skip = solve(arr, index - 1, k);

        // Pair arr[index] with arr[index-1] if difference <= k
        int pair = 0;
        if (arr[index] - arr[index - 1] <= k) {
            pair = arr[index] + arr[index - 1] + solve(arr, index - 2, k);
        }

        return Math.max(skip, pair);
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 10, 15, 17, 12, 9};
        int k = 4;
        System.out.println(maxSumBrute(arr, k)); // Output: 62
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - at each index we have two choices (pair or skip)
• Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

After sorting, adjacent elements have the smallest differences. We use DP where dp[i] is the maximum sum considering the first i elements. For each element, we either skip it or pair it with its neighbor.

Algorithm

1. Sort the array.
2. Create a dp array where dp[i] = max sum using elements from index 0 to i.
3. dp[0] = 0 (single element, no pair).
4. For i >= 1: if arr[i] - arr[i-1] <= k, then dp[i] = max(dp[i-1], (i >= 2 ? dp[i-2] : 0) + arr[i] + arr[i-1]). Otherwise dp[i] = dp[i-1].
5. Return dp[n-1].

class Solution {
    public static int maxSumPairs(int[] arr, int k) {
        int n = arr.length;
        java.util.Arrays.sort(arr);

        int[] dp = new int[n];
        dp[0] = 0; // Single element can't form a pair

        for (int i = 1; i < n; i++) {
            // Option 1: Don't pair arr[i]
            dp[i] = dp[i - 1];

            // Option 2: Pair arr[i] with arr[i-1] if difference <= k
            if (arr[i] - arr[i - 1] <= k) {
                int pairSum = arr[i] + arr[i - 1];
                if (i >= 2) {
                    pairSum += dp[i - 2];
                }
                dp[i] = Math.max(dp[i], pairSum);
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 10, 15, 17, 12, 9};
        int k = 4;
        System.out.println(maxSumPairs(arr, k)); // Output: 62
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - dominated by sorting; the DP loop is O(n)
• Space Complexity: O(n) - the dp array