Big O of get largest Numbers

Question

Got this question recently:

Write a function which takes an array of arrays (each of which contains numbers sorted from largest to smallest), and a number (n). Return the n largest numbers.

For example:

findLargest([ [10, 5, 3, 1], [9, 8, 7, 6], [11, 2, 1, 0] ], 5) => [11, 10, 9, 8, 7]

findLargest([ [15, 5, 3, 1], [10, 8, 7, 6]], 3) => [ 15, 10, 8 ]

Do this without copying or modifying the arrays (just read from them). Optimize for time complexity.

I came up with this, but am not that happy with my solution:

function findLargest(numberArrays, n ) {
  var results = [];
  var pointers = [];

  for (var x = 0; x < numberArrays.length; x++) {
    pointers.push(0);
  }

  while (results.length < n) {
    var subMaxes = [];
    for (var i = 0; i < pointers.length; i++) {
      var point = pointers[i];
      subMaxes.push(numberArrays[i][point]);
    }
    var max = Math.max.apply(null, subMaxes);
    var indexOfMax = subMaxes.indexOf(max);
    pointers[indexOfMax]++;
    results.push(max);  
  }
  return results;
}

I think it is O(n^2).... is there anyway to do it in O(n)?

Answer 1

The question can be formalised (and slightly tweaked) as, Given a 2D array of dimension n x n, where each row is sorted in a decreasing order, find the largest k elements

For the largest n elements, the time complexity will be O(nlogn). The procedure for k largest elements is explained below:

• Build a max heap of the first element from each row: Time complexity is O(n)

• Extract the largest element from the heap, and insert an element into the heap from the row to which the extracted element belongs. Time Complexity is O(logn)

• Repeat under desired number of elements is extracted.

So an iteration to extract the largest number requires O(logn) time, with a pre-processing O(n) cost.

To extract k elements, the time complexity of the above algorithm is O(klogn)