Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 1: K Pairs with Largest Sum

Problem Statement

Given two sorted arrays in descending order, find ‘K’ pairs with the largest sum where each pair consists of numbers from both the arrays.

Example 1:

Input: nums1=[9, 8, 2], nums2=[6, 3, 1], K=3
Output: [9, 3], [9, 6], [8, 6] 
Explanation: These 3 pairs have the largest sum. No other pair has a sum larger than any of these.

Example 2:

Input: nums1=[5, 2, 1], nums2=[2, -1], K=3
Output: [5, 2], [5, -1], [2, 2]

Constraints:

  • 1 <= nums1.length, nums2.length <= 10<sup>5</sup>
  • -10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup>
  • `nums1

.....

.....

.....

Like the course? Get enrolled and start learning!
Nitin Varun

Nitin Varun

· 2 years ago

Hi Team, Please validate if test cases used for accepting solution is correct or not. For example, In below particular test case.

[5,3] -> 8 and [5,2] -> 7 must be one of acceptable solution because both produces top 2 max sum pair.

Expected Output also produces top 2 max pair sum which is 8 and 7.

Please help in adding more valid test case scenario for accepting the solution.

————————————————-

L1 = [5, 4, 3]

L2 = [3, 2, 1]

K = 2

Output[[5,3],[5,2]]

Expected[[5,3],[4,3]]

—————————————————-

Show 3 replies
Manas Sambare

Manas Sambare

· 2 years ago

There is a Test Case:

Your Input:
[10, 8, 6]
[9, 7, 5]
2
Expected: [[8,9],[10,9]]

While this Test Case is correct, there is an alternate solution:

Your Input:
[10, 8, 6]
[9, 7, 5]
2
Output: [[10,7],[10,9]]

Both solutions should be correct as:

[10, 7] and [8, 9] add up to 17
[10, 9] adds up to 19

Either this test case should be removed/altered to have only one solution or the question should mention how to prioritize the options.

Show 1 reply
W

Will

· 4 years ago

There exists an O(KLogK) solution using a heap, but requires some non-obvious insight to come up with it. See Leetcode question 373.

Show 3 replies
L

lejafilip

· 2 years ago

Fix that

B

Biruk

· 4 years ago

This solution giving incorrect result on its respective leetcode problem.

Show 4 replies
B

Baraa Attabbaa

· 3 years ago

    result = []
    h = []

    heappush(h, (-(nums1[0]+nums2[0]), 0, 0))

    for i in range(k):
      if not h: break

      v, i1, i2 = heappop(h)
      result.append([nums1[i1], nums2[i2]])

      if i2 < len(nums2) - 1:
        heappush(h, (-(nums1[i1]+nums2[i2+1]), i1, i2+1))

      if i1 < len(nums1) - 1:
        heappush(h, (-(nums1[i1+1]+nums2[i2]), i1+1, i2))

    # TODO: Write your code here
    return result
Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

Since the arrays are sorted the this implies that we are interested in the max value of one of the arrays and some value form another array

e.g:

A = [5, 2, 1]

B = [31, 4, 2]

meaning we are comparing the sum [5 + 31] vs [5 + 4] vs [5 + 2] from A

AND

[31 + 2] vs [31 + 1] from B

 def findKLargestPairs(self, nums1, nums2, k):
    result = []
    
    max1 = nums1[0]
    max2 = nums2[0]
    
    max_heap = []

    for i in range(0, len(nums1)):
      heappush(max_heap, (-(max2 + nums1[i]), [max2, nums1[i]]))
    
    for i in range(1, len(nums2)): # starting from 1 we dont want repeat the value of [max1, max2]
      heappush(max_heap, (-(max1 + nums2[i]), [max1, nums2[i]]))

    for _ in range(k):
      add, array = heappop(max_heap)
      result.append(array)
P

Pete Stenger

· 2 years ago

from heapq import *
class Solution:
  def findKLargestPairs(self, nums1, nums2, k):

    heap = [(-nums1[0] - nums2[0], 0, 0)]
    result = []
    # every iteration, we add two elements and remove one.
    # we do k iterations.
    # thus the size of the heap is at most O(k)
    # Thus, this runtime is O(k log k)
    for _ in range(k):
      _,idx1, idx2 = heappop(heap)
      result.append([nums1[idx1], nums2[idx2]])
      if idx2 + 1 < len(nums2):
        heappush(heap, (-nums1[idx1] - nums2[idx2 + 1], idx1, idx2 + 1))
      if idx1 + 1 < len(nums1):
        heappush(heap, (-nums1[idx1 + 1] - nums2[idx2], idx1 + 1, idx2))

    return result
Show 1 reply