← Back to Index

📚 K Maximum Sum Combinations From Two Arrays – Java Cheat Sheet

📌 What Is It?

The K Maximum Sum Combinations From Two Arrays problem involves finding the top K largest sums that can be formed by picking one element from each of two arrays.

This problem can be solved using a max-heap to track the largest sums.

🧱 Pattern Template

class Solution {
    public List<Integer> kMaxSumCombinations(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        for (int i = nums1.length - 1; i >= 0; i--) {
            maxHeap.offer(new int[]{nums1[i] + nums2[nums2.length - 1], i, nums2.length - 1});
        }

        List<Integer> result = new ArrayList<>();
        while (k > 0 && !maxHeap.isEmpty()) {
            int[] top = maxHeap.poll();
            result.add(top[0]);
            k--;

            int i = top[1], j = top[2];
            if (j > 0) {
                maxHeap.offer(new int[]{nums1[i] + nums2[j - 1], i, j - 1});
            }
        }

        return result;
    }
}

📊 Time Complexity

• Sorting Arrays: O(N log N + M log M) – Sorting both arrays.
• Heap Operations: O(K log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log N + M log M + K log K).

✅ Use Cases

• Finding the largest sums from combinations of two datasets
• Applications in optimization problems
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 373. Find K Pairs with Smallest Sums [Medium] Heap

🧪 Example: K Maximum Sum Combinations From Two Arrays

Input: nums1 = [1, 4, 2], nums2 = [3, 5], k = 3
Output: [9, 8, 7]

Explanation:
- The top 3 sums are [9, 8, 7].

▶️ View Animation

💡 Pro Tips

• Sort both arrays to efficiently find the largest sums.
• Use a max-heap to track the largest sums.
• Edge cases: arrays with duplicate elements, arrays of unequal lengths.