-1

Suppose we have n (1<=n<=10^3) sorted arrays of sizes A1, A2, .... An. (1<=Ai<=10^3). We need to kind the kth smallest integer from the unique combination these arrays. Is there an efficient method to do this with complexity less than O(A1 + A2.. + An)?

Can be be solved something similar to binary search?

PS: I have a similar problem here, but could not understand how to extend it for unique elements.

EDIT 1: I think some of you misunderstood the question. Let us take an example: N = 3,

A1 = 1, 1, 2, 3

A2 = 6, 7, 9

A3 = 1, 6, 8

The unique combination of above arrays is {1, 2, 3, 6, 7, 8, 9}. Now suppose I want the 2nd element it should return 2 and for 4th element it should return 6.

Community
  • 1
  • 1
likecs
  • 353
  • 2
  • 13
  • I am not sure what it means kth smallest unique integer, it cannot repeat in multiple arrays? Do non uniques count for "smaller"? What will be the output for example of [1,2,3,4,5], [2,3] k=3? – amit May 27 '16 at 07:38
  • look for quickselect algorithm for unsorted entries. For sorted arrays, try looking for min/max heap – user2290820 May 27 '16 at 08:31
  • In which range are the numbers? – MrSmith42 May 27 '16 at 08:54
  • Numbers are in the range 0 to 10^9 but they can be coordinate compressed as well. – likecs May 27 '16 at 09:16

2 Answers2

1

It is possible in O(k n log n):

  • Make a min-heap with the minimal element from each array.
  • Repeat k times:
    • Look at the minimum element q in the min-heap and remember it
    • Extract from min-heap while minimum equals to q.
    • For each extracted element, put the first element larger than q from the corresponding array
  • Answer is the minimum element in min-heap

Python code:

import heapq
import bisect

def kth(A, k):
    h = []

    for idx,a in enumerate(A):
        if len(a) > 0:
            heapq.heappush(h, (a[0], idx))

    for i in xrange(k):
        if len(h) == 0:
            return None

        val, _ = h[0]

        while (len(h) > 0) and (h[0][0] == val):
            _, idx = heapq.heappop(h)
            nxt = bisect.bisect_right(A[idx], val)
            if nxt < len(A[idx]):
                heapq.heappush(h, (A[idx][nxt], idx))

    if len(h) > 0:
        return h[0][0]
    return None
0

Is there a space requirement, or can the numbers in the arrays be duplicated?

If not, you could create 2 sorted sets: uniques and nonUniques. When adding an array, you loop over the array and add its numbers to the 2 sorted sets like this:

  • If a new number exists in nonUniques, skip it
  • If a number exists in uniques, remove it from uniques and add it to nonUniques
  • Otherwise add the nww number to uniques

Then you can immediately look up the k-th smallest number in the sorted uniques set.

Bartez
  • 172
  • 8