Find the pair across 2 arrays with kth largest sum

by

That can be easily done in O(k*logk). I’ll only assume arrays are sorted in descending order, to simplify notation.

The idea is simple. We’ll find 1st, 2nd, .., k-th maximum values one by one. But to even consider pair (i, j) we need to have both (i-1, j) and (i, j-1) already selected, because they both are greater or equal than (i, j).

It’s much like if we push all n*m pairs into the heap and then remove max k times. Only we don’t need all n*m pairs.

heap.add(pair(0, 0));  // biggest pair

// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
    // get max and remove it from the heap
    max = heap.popMax();

    // add next candidates
    heap.add(pair(max.i + 1, max.j));
    heap.add(pair(max.i, max.j + 1));
}

// get k-th maximum element
max = heap.popMax();
maxVal = a[max.i] + b[max.j];

Some things to consider.

  • Duplicated pairs can be added to the heap, this can be prevented with hash.
  • Indexes need to be validated, e.g. that max.i + 1 < a.length.

More Related Contents:

  1. C++ Sorting Algorithms [closed]
  2. Priority scoring algorithm [closed]
  3. What should be the algorithm of the below statement?
  4. Efficient way to add element to sorted datastructure [closed]
  5. What is stability in sorting algorithms and why is it important?
  6. Fastest sort of fixed length 6 int array
  7. Why is quicksort better than mergesort?
  8. Which sort algorithm works best on mostly sorted data? [closed]
  9. Merge Sort a Linked List
  10. Quicksort: Choosing the pivot
  11. What’s the fastest algorithm for sorting a linked list?
  12. Natural Sorting algorithm
  13. Compute the minimal number of swaps to order a sequence
  14. Which parallel sorting algorithm has the best average case performance?
  15. Fast algorithm implementation to sort very small list
  16. Sorting in linear time? [closed]
  17. median of three values strategy
  18. Sorting an array with minimal number of comparisons
  19. Quicksort vs heapsort
  20. What is a bubble sort good for? [closed]
  21. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  22. Faster version of find for sorted vectors (MATLAB)
  23. Quicksort superiority over Heap Sort
  24. Can an array be grouped more efficiently than sorted?
  25. Search a sorted 2D matrix [duplicate]
  26. When is each sorting algorithm used? [closed]
  27. Comparison-based ranking algorithm
  28. Why is bubble sort O(n^2)?
  29. Stable separation for two classes of elements in an array
  30. Find the k largest elements in order

Leave a Comment