Maximum sum of pairs with specific difference

The problem, simply

You get a list of numbers and a number K. Two numbers may form a pair if their difference is strictly less than K. Each number can be in at most one pair, and some numbers may stay alone.

Give back the biggest possible sum of all numbers that end up in pairs.

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort the list. Then from the biggest number down, each number either stays alone or pairs with its left neighbor.

1. f(i) is the best sum using sorted numbers 0 to i.
2. Skip number i: f(i - 1).
3. If a[i] - a[i - 1] < K, pair them: a[i] + a[i - 1] + f(i - 2).
4. f(0) and below are 0.

Why only the left neighbor? After sorting, the left neighbor is the closest smaller number. Any pair that reaches further back can swap partners with the neighbor and stay valid with the same or a bigger sum.

import java.util.Arrays;

class Solution {
    public int maxSumPairs(int[] arr, int k) {
        int[] a = arr.clone();
        Arrays.sort(a);                                     // partners stand side by side
        return best(a, a.length - 1, k);
    }

    private int best(int[] a, int i, int k) {
        if (i <= 0) return 0;                               // zero or one number left
        int skip = best(a, i - 1, k);
        int pair = 0;
        if (a[i] - a[i - 1] < k) {
            pair = a[i] + a[i - 1] + best(a, i - 2, k);    // pair with the left neighbor
        }
        return Math.max(skip, pair);
    }
}

How long it takes: up to two branches per call, O(2^n) (it grows like the Fibonacci numbers). Extra room: the waiting calls, O(n).

Way 2: the clever way

Remember each f(i) in an array dp and fill it from left to right.

1. Sort. Set dp[0] = 0.
2. For i from 1: dp[i] = dp[i - 1] (skip).
3. If a[i] - a[i - 1] < K, also try a[i] + a[i - 1] + dp[i - 2] (with dp[-1] = 0).
4. The answer is dp[n - 1].

import java.util.Arrays;

class Solution {
    public int maxSumPairs(int[] arr, int k) {
        int n = arr.length;
        if (n < 2) return 0;
        int[] a = arr.clone();
        Arrays.sort(a);
        int[] dp = new int[n];                              // dp[0] = 0: one number cannot pair
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1];                              // leave a[i] alone
            if (a[i] - a[i - 1] < k) {
                int before = i >= 2 ? dp[i - 2] : 0;
                dp[i] = Math.max(dp[i], before + a[i] + a[i - 1]);   // pair the neighbors
            }
        }
        return dp[n - 1];
    }
}

How long it takes: sorting is O(n log n), the fill is O(n). Extra room: the dp array and the sorted copy, O(n).

Way 3: greedy from the top

Since we want a big sum, the biggest numbers matter most. Walk the sorted list from the right. If the biggest remaining number can pair with its left neighbor, pair them and jump two steps. Otherwise drop it and step once.

This is safe because the top number, if it can pair at all, gains the most from pairing now, and its neighbor is its best partner.

import java.util.Arrays;

class Solution {
    public int maxSumPairs(int[] arr, int k) {
        int[] a = arr.clone();
        Arrays.sort(a);
        int sum = 0;
        int i = a.length - 1;
        while (i > 0) {
            if (a[i] - a[i - 1] < k) {      // the two biggest left can pair
                sum += a[i] + a[i - 1];
                i -= 2;
            } else {
                i -= 1;                     // a[i] has no partner
            }
        }
        return sum;
    }
}

Same O(n log n) time, but only O(1) extra room besides the sort. It works because all numbers are added, never subtracted. With negative numbers you would want the DP, because pairing two negatives lowers the sum.

Watch out for

• Forgetting to sort. Without sorting, good partners are not neighbors and the DP misses them.
• Sorting the caller's array in place. Clone first if the input must not change.
• dp[i - 2] when i = 1 goes out of bounds. Treat it as 0.

What interviewers ask next

• Count the most pairs instead of the biggest sum? Same sort, then greedy from the left: pair neighbors whenever they fit.
• What if numbers can be negative? Use the DP and allow "skip" even when a pair fits. The greedy can fail.
• Why are we allowed to sort? The answer only depends on which numbers end up together, not on where they stood, so any order is fine.
• Return the pairs. Walk dp backwards and see whether each dp[i] came from skipping or pairing.

Remember this

Grown-up words: lining up kids is sorting, partners are disjoint pairs, the note at each spot is dp[i], swapping partners is an exchange argument, and Way 3 is a greedy that only works because every value is positive.