Given two sorted arrays A and B and an integer number k, return the first k pair

Question

Given two sorted arrays A and B and an integer number k, return the first k pairs from the set A x B ordered by the sum of the elements.

A x B - cartesian product, i.e. if A = {a1, ..., an} and B = {b1, b2, ..., bn}, A x B = {(a1, b1), (a1, b2), ..., (a1, bn), ..., ..., (an, bn)} - the set of A.length * B.length pairs.

Testcase:

input: A = {1, 2, 5}, B = {2, 4}, k = 4

output: {(1, 2), (2, 2), (1, 4), (2, 4)}

Provide the solution (pseudocode or just a description of the method). Please, note that if A.length is large (say 1000) and B.length is large (say 1000), an implementation of your algorithm should still be able to handle the problem.

*Use a heap data structure

Explanation / Answer

2) Yield the appropriate element from each list (in this case the first).

3) Increase the last index by one.

4) If the last index equals the length of the last list, reset it to zero and carry one. Repeat this until there is no carry.

5) Go back to step 2 until the indexes wrap back to [0,0,0,0,0,0]

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.