Find Two Pairs Such That a + b = c + d

Given an array of distinct integers, find two pairs (a, b) and (c, d) such that a + b = c + d, where a, b, c, and d are four different elements. Return any such two pairs, or Optional.empty() if there aren't any. Optional is a container that holds either one value or nothing; here it holds an int[] {a, b, c, d}.

Example 1

Text

Input:  [3, 4, 7, 1, 12, 9]
Output: (4, 12) and (7, 9)    both sum to 16
        (3, 7) and (1, 9), both summing to 10, is also valid

Example 2

Text

Input:  [1, 2, 4]
Output: empty  (the sums are 3, 5, and 6: all different)

Brute force: try every four indices

Choose i < j for the first pair and k < l for the second, make sure all four indices are different, and compare the sums.

Java

import java.util.Optional;

public class Main {
    static Optional<int[]> findPairs(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = i + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        if (k != j && l != j && nums[i] + nums[j] == nums[k] + nums[l]) {
                            return Optional.of(new int[]{nums[i], nums[j], nums[k], nums[l]});
                        }
                    }
                }
            }
        }
        return Optional.empty();
    }

    static String show(Optional<int[]> r) {
        return r.map(x -> "((" + x[0] + ", " + x[1] + "), (" + x[2] + ", " + x[3] + "))").orElse("none");
    }

    public static void main(String[] args) {
        System.out.println(show(findPairs(new int[]{3, 4, 7, 1, 12, 9})));
        System.out.println(show(findPairs(new int[]{1, 2, 4})));
    }
}

Output

((3, 7), (1, 9))
none

Time: O(n⁴). Space: O(1).

Starting k at i + 1 keeps the first pair's smallest index i below both indices of the second pair, so each combination is checked only once.

Optimal: a HashMap from each sum to a pair

Enumerate all pairs (i, j) once and compute their sums. Store sum → (i, j) in a HashMap. If a sum is already in the map, the stored pair and the current pair have the same sum.

The two pairs can't share an element: if a + b = a + d, then b = d, and all values are distinct. So a repeated sum always gives four different elements.

Walkthrough with [3, 4, 7, 1, 12, 9]:

pair (values)	sum	sum already in map?
(3, 4)	7	no, store
(3, 7)	10	no, store
(3, 1)	4	no, store
(3, 12)	15	no, store
(3, 9)	12	no, store
(4, 7)	11	no, store
(4, 1)	5	no, store
(4, 12)	16	no, store
(4, 9)	13	no, store
(7, 1)	8	no, store
(7, 12)	19	no, store
(7, 9)	16	yes: (4, 12) → return (4, 12), (7, 9)

The map value is an int[] {i, j} holding the two indices.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

public class Main {
    static Optional<int[]> findPairs(int[] nums) {
        Map<Integer, int[]> bySum = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                int[] earlier = bySum.get(sum);
                if (earlier != null) {
                    return Optional.of(new int[]{nums[earlier[0]], nums[earlier[1]], nums[i], nums[j]});
                }
                bySum.put(sum, new int[]{i, j});
            }
        }
        return Optional.empty();
    }

    static String show(Optional<int[]> r) {
        return r.map(x -> "((" + x[0] + ", " + x[1] + "), (" + x[2] + ", " + x[3] + "))").orElse("none");
    }

    public static void main(String[] args) {
        System.out.println(show(findPairs(new int[]{3, 4, 7, 1, 12, 9})));
        System.out.println(show(findPairs(new int[]{1, 2, 4})));
        System.out.println(show(findPairs(new int[]{})));
    }
}

Output

((4, 12), (7, 9))
none
none

Time: O(n²): there are n(n-1)/2 pairs, each with an O(1) map operation. Space: O(n²) for the map in the worst case.

The two solutions return different answers because they enumerate the combinations in a different order. Both answers are valid.

The map stores indices, not values. With duplicate values allowed, you'd need them to check that the four positions are different, for example k != i && k != j && l != i && l != j.

Edge cases

Fewer than 4 elements: no answer is possible.
Overflow: nums[i] + nums[j] wraps around silently in int arithmetic for large values. Compute sums as long (with Map<Long, int[]>) if the range requires it.