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!
L

lejafilip

· 2 years ago

Fix that

Show 1 reply
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 2 replies
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)
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
Nitin Varun

Nitin Varun

· 3 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
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
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
B

Biruk

· 4 years ago

This solution giving incorrect result on its respective leetcode problem.

Show 4 replies

Reading Progress

0%

Vote for new content