Find the pair(s) with the max sum with given constraints

Question

I was recently asked in a job interview to find the max sum across two arrays with given constraints. The question was phrased differently, but it boiled down to what I said above. Nothing was said about the elements being distinct, or the arrays being sorted.

Example:

A = [2000, 3000, 4000, 5000]
B = [6000, 5000, 4000, 1000]
Constraint: A[i] + B[j] <= 7000
Expected Result: (A[0], B[1]), (A[1], B[2])

Note that this isn't the same question as Find the pair across 2 arrays with kth largest sum because of the constraint.

A brute force solution is to take the cartesian product of the 2 arrays, calculate the sum of each pair, filter out the ones greater than 7000, sort, and take the top values that are equal. The time complexity is O(n²). Can we do better?

score 3 · Answer 1 · answered Aug 03 '18 at 09:21

3

In the beginning, you should sort two arrays. Then you can use this iteration:

for every number in A:
    perform binary search to find biggest element in B lower than 7000-A

Number you found in binary search is the best number for pairing for current number in array A. You can take maximum of these values(for all iteration on array A).

Binary search runs in O(logN) time so this iteration runs in O(NlogN) time, and sort also runs in O(NlogN) time. You can change 7000 with a variable.

answered Aug 03 '18 at 09:21

Burak Buğrul

74
4

Sorting destroys the given order. Can you show how you'd come to the answer in my example? – Abhijit Sarkar Aug 03 '18 at 19:52
You can use another array or set like data structures. – Burak Buğrul Aug 05 '18 at 22:35

score 0 · Accepted Answer · answered Aug 08 '18 at 02:05

Answering my own question, the following is a working solution:

public List<Map.Entry> max(int[] a, int[] b, int sum) {
    NavigableMap<Integer, Integer> distMap = new TreeMap<>();
    SortedMap<Integer, List<Map.Entry>> indicesMap = new TreeMap<>();

    for (int i = 0; i < a.length; i++) {
        distMap.put(a[i], i);
    }

    for (int i = 0; i < b.length; i++) {
        int diff = sum - b[i];
        Map.Entry<Integer, Integer> floorEntry = distMap.floorEntry(diff);
        if (Objects.nonNull(floorEntry)) {
            int tmp = b[i] + floorEntry.getKey();
            int j = i;
            indicesMap.merge(
                    tmp,
                    new ArrayList<Map.Entry>() {{
                        add(new AbstractMap.SimpleImmutableEntry<>(floorEntry.getValue(), j));
                    }},
                    (l1, l2) -> {
                        l1.addAll(l2);
                        return l1;
                    }
            );
        }
    }
    return indicesMap.get(indicesMap.lastKey());
}

Time complexity: O(n) for put + O(nlogn) for floorEntry, overall O(nlogn). Space complexity O(n).

Find the pair(s) with the max sum with given constraints

2 Answers2