5

I was asked this question in an interview. I was able to do it in O(n) time obviously, but I fail to think about a way to solve in in O(logn). It sounds like using some divide-and-conquer algorithms but I'm not sure.

Gábor Bakos
  • 8,982
  • 52
  • 35
  • 52
user3342802
  • 61
  • 3
  • Can you provide how you went about it in O(n)? Where you jumping back and forth between the two? – ChiefTwoPencils Feb 23 '14 at 08:35
  • 2
    Frankly, I don't see how it could be less than O(k): you compare the last elements of both arrays, and decrement the index associated with the array of the biggest of the two items. Do that k times, and you have your kth biggest element. – JB Nizet Feb 23 '14 at 08:38

1 Answers1

8

Truncate both to size k. If necessary, have the program imagine enough infinities at the end of one or both arrays to bring them up to size k; this will not affect the asymptotic runtime. (In a real implementation, we would probably do something more efficient.)

Then, compare the k/2'th elements of each array. If the elements compared equal, we've found the k'th element; otherwise, let the array with the lower k/2'th element be A and the other be B. Throw away the bottom half of A and the top half of B, then recursively find the k/2'th element of what remains. Stop when we hit k=1.

On every step, the bottom half of A is guaranteed to be too small, and the top half of B is guaranteed to be too big. The k/2'th element of what remains is guaranteed to be bigger than the bottom half of A, so it's guaranteed to be the k'th element of the original.

Proof of concept, in Python:

def kth(array1, array2, k):
    # Basic proof of concept. This doesn't handle a bunch of edge cases
    # that a real implementation should handle.
    # Limitations:
    #   Requires numpy arrays for efficient slicing.
    #   Requires k to be a power of 2
    #   Requires array1 and array2 to be of length exactly k
    if k == 1:
        return min(array1[0], array2[0])
    mid = k//2 - 1
    if array1[mid] > array2[mid]:
        array1, array2 = array2, array1
    return kth(array1[k//2:], array2[:k//2], k//2)

I have tested this, but not much.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • That sounds like it. +1. – JB Nizet Feb 23 '14 at 08:45
  • 1
    *if the elements compared equal, pick arbitrarily*: haven't you found the kth biggest element if both are equal? – JB Nizet Feb 23 '14 at 09:10
  • @JBNizet: I think you're right. – user2357112 Feb 23 '14 at 09:11
  • I am trying to implement this algorithm but I seem to have found a case for which this algorithm fails. Consider array `A = {1}` and `B = {2, 3}` and you try to find the second largest element (which should be 2). When you make A size two `A = {1, ∞}`, divide it in the center {1 | ∞} then remove the right half of A and the left half of B you are left with `A = {1}` and `B = {3}` whose min gives the answer as 1. – 1110101001 Oct 10 '14 at 04:50
  • 1
    @user2612743: Might be an indexing-from-0 vs indexing-from-1 issue. My description seems to index from 1. You should be removing the left half of A and the right half of B, rather than the other way around. – user2357112 Oct 10 '14 at 04:56