Coding

Maximum Sum Combination

Asked at

Paytm

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given two integer arrays **nums1 **and **nums2 **and an integer k, return the maximum k valid sum combinations from all possible sum combinations using the elements of **nums1 **and nums2.

A **valid sum combination **is made by adding one element from **nums1 **and one element from nums2. Return the answer in non-increasing order.

Input: nums1 = [7, 3], nums2 = [1, 6], k = 2 Output: [13, 9] Explanation: The 2 maximum combinations are made by: nums1[0] + nums2[1] = 13 nums1[1] + nums2[1] = 9

Input: nums1 = [3, 4, 5], nums2 = [2, 6, 3], k = 2 Output: [11, 10] Explanation: The 2 maximum combinations are made by: nums1[2] + nums2[1] = 11 nums1[1] + nums2[1] = 10

Input: nums1 = [2, 2], nums2 = [5, 5], k = 2

n == size of nums1 & nums2
1 <= n <= 105
1 <= Each element of nums1 & nums2 <= 104
1 <= k <= n * n

cpp

class Solution {
public:
  vector<int> maxSumCombinations(vector<int> &nums1, vector<int> &nums2, int k) {

  }
};

java

class Solution {
    public int[] maxSumCombinations(int[] nums1, int[] nums2, int k) {

    }
}

python

class Solution:
    def maxSumCombinations(self, nums1, nums2, k):

javascript

class Solution {
    maxSumCombinations(nums1, nums2, k) {

    }
}

csharp

public class Solution {

    public List<int> MaxSumCombinations(List<int> nums1, List<int> nums2, int k) {
        //your code goes here
    }
}

func maxSumCombinations(nums1 []int, nums2 []int, k int) []int {
}

Stuck? Show a way to structure it+

01Sort both arrays descending
02Push the largest pair and mark it visited
03Pop the best sum and add valid unseen neighbor pairs
04Repeat k times or until heap empty

Reference answer

Start by restating the input contract for Maximum Sum Combination and testing the smallest boundary case before choosing the algorithm. For two arrays, sort both descending and use a max-heap of index pairs. Begin with (0,0); when popping (i,j), push unseen neighbors (i+1,j) and (i,j+1). A visited set prevents duplicate pairs while the heap yields combinations in decreasing sum order. Explain the invariant while coding, then show how each update preserves it. For arrays of length n and k requested sums, sorting plus heap work is O(n log n + k log k) time and O(k) auxiliary space after sorting. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Why are only two neighbors sufficient?
Tests: correctness reasoning
How would you return the chosen elements too?
Tests: implementation extension

Hiring now

Paytm has 128 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer – Backend (Travel)
Bangalore, Karnataka
Junior Marketing Manager
Luxembourg
Collection Manager- North- Business- Lending Collections
Aligarh, Uttar Pradesh

Or practice this question first

Next question