Finding kth smallest number from n sorted arrays

Question

So, you have n sorted arrays (not necessarily of equal length), and you are to return the kth smallest element in the combined array (i.e the combined array formed by merging all the n sorted arrays)

I have been trying it and its other variants for quite a while now, and till now I only feel comfortable in the case where there are two arrays of equal length, both sorted and one has to return the median of these two. This has logarithmic time complexity.

After this I tried to generalize it to finding kth smallest among two sorted arrays. Here is the question on SO. Even here the solution given is not obvious to me. But even if I somehow manage to convince myself of this solution, I am still curious as to how to solve the absolute general case (which is my question)

Can somebody explain me a step by step solution (which again in my opinion should take logarithmic time i.e O( log(n₁) + log(n₂) ... + log(n_N) where n₁, n₂...n_N are the lengths of the n arrays) which starts from the more specific cases and moves on to the more general one?

I know similar questions for more specific cases are there all over the internet, but I haven't found a convincing and clear answer.

Here is a link to a question (and its answer) on SO which deals with 5 sorted arrays and finding the median of the combined array. The answer just gets too complicated for me to able to generalize it.

Even clean approaches for the more specific cases (as I mentioned during the post) are welcome.

PS: Do you think this can be further generalized to the case of unsorted arrays?

PPS: It's not a homework problem, I am just preparing for interviews.

Answer 1

This doesn't generalize the links, but does solve the problem:

1. Go through all the arrays and if any have length > k, truncate to length k (this is silly, but we'll mess with k later, so do it anyway)
2. Identify the largest remaining array A. If more than one, pick one.
3. Pick the middle element M of the largest array A.
4. Use a binary search on the remaining arrays to find the same element (or the largest element <= M).
5. Based on the indexes of the various elements, calculate the total number of elements <= M and > M. This should give you two numbers: L, the number <= M and G, the number > M
6. If k < L, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the bottom halves).
7. If k > L, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the top halves, and search for element (k-L).

When you get to the point where you only have one element per array (or 0), make a new array of size n with those data, sort, and pick the kth element.

Because you're always guaranteed to remove at least half of one array, in N iterations, you'll get rid of half the elements. That means there are N log k iterations. Each iteration is of order N log k (due to the binary searches), so the whole thing is N^2 (log k)^2 That's all, of course, worst case, based on the assumption that you only get rid of half of the largest array, not of the other arrays. In practice, I imagine the typical performance would be quite a bit better than the worst case.

Answer 2

It can not be done in less than O(n) time. Proof Sketch If it did, it would have to completely not look at at least one array. Obviously, one array can arbitrarily change the value of the kth element.

I have a relatively simple O(n*log(n)*log(m)) where m is the length of the longest array. I'm sure it is possible to be slightly faster, but not a lot faster.

Consider the simple case where you have n arrays each of length 1. Obviously, this is isomorphic to finding the kth element in an unsorted list of length n. It is possible to find this in O(n), see Median of Medians algorithm, originally by Blum, Floyd, Pratt, Rivest and Tarjan, and no (asymptotically) faster algorithms are possible.

Now the problem is how to expand this to longer sorted arrays. Here is the algorithm: Find the median of each array. Sort the list of tuples (median,length of array/2) and sort it by median. Walk through keeping a sum of the lengths, until you reach a sum greater than k. You now have a pair of medians, such that you know the kth element is between them. Now for each median, we know if the kth is greater or less than it, so we can throw away half of each array. Repeat. Once the arrays are all one element long (or less), we use the selection algorithm.

Implementing this will reveal additional complexities and edge conditions, but nothing that increases the asymptotic complexity. Each step

1. Finds the medians or the arrays, O(1) each, so O(n) total
2. Sorts the medians O(n log n)
3. Walks through the sorted list O(n)
4. Slices the arrays O(1) each so, O(n) total

that is O(n) + O(n log n) + O(n) + O(n) = O(n log n). And, we must perform this untill the longest array is length 1, which will take log m steps for a total of O(n*log(n)*log(m))

---

You ask if this can be generalized to the case of unsorted arrays. Sadly, the answer is no. Consider the case where we only have one array, then the best algorithm will have to compare at least once with each element for a total of O(m). If there were a faster solution for n unsorted arrays, then we could implement selection by splitting our single array into n parts. Since we just proved selection is O(m), we are stuck.

Answer 3

There exist an generalization that solves the problem in O(N log k) time, see the question here.

Answer 4

Old question, but none of the answers were good enough. So I am posting the solution using sliding window technique and heap:

class Node {

    int elementIndex;
    int arrayIndex;

    public Node(int elementIndex, int arrayIndex) {
        super();
        this.elementIndex = elementIndex;
        this.arrayIndex = arrayIndex;
    }

}

public class KthSmallestInMSortedArrays {

    public int findKthSmallest(List<Integer[]> lists, int k) {

        int ans = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> {
            return lists.get(a.arrayIndex)[a.elementIndex] -
                   lists.get(b.arrayIndex)[b.elementIndex];
        });

        for (int i = 0; i < lists.size(); i++) {
            Integer[] arr = lists.get(i);
            if (arr != null) {
                Node n = new Node(0, i);
                pq.add(n);
            }
        }

        int count = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            ans = lists.get(curr.arrayIndex)[curr.elementIndex];
            if (++count == k) {
                break;
            }

            curr.elementIndex++;
            pq.offer(curr);
        }

        return ans;
    }
}

The maximum number of elements that we need to access here is O(K) and there are M arrays. So the effective time complexity will be O(K*log(M)).

Answer 5

This would be the code. O(k*log(m))

public int findKSmallest(int[][] A, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(x -> A[x[0]][x[1]]));
        for (int i = 0; i < A.length; i++)
            queue.offer(new int[] { i, 0 });

        int ans = 0;
        while (!queue.isEmpty() && --k >= 0) {
            int[] el = queue.poll();
            ans = A[el[0]][el[1]];
            if (el[1] < A[el[0]].length - 1) {
                el[1]++;
                queue.offer(el);
            }
        }

        return ans;
    }

Answer 6

You could look at my recent answer on the related question here. The same idea can be generalized to multiple arrays instead of 2. In each iteration you could reject the second half of the array with the largest middle element if k is less than sum of mid indexes of all arrays. Alternately, you could reject the first half of the array with the smallest middle element if k is greater than sum of mid indexes of all arrays, adjust k. Keep doing this until you have all but one array reduced to 0 in length. The answer is kth element of the last array which wasn't stripped to 0 elements.

Run-time analysis:

You get rid of half of one array in each iteration. But to determine which array is going to be reduced, you spend time linear to the number of arrays. Assume each array is of the same length, the run time is going to be cclog(n), where c is the number of arrays and n is the length of each array.

Answer 7

It can be done by doing binary search in each array, while calculating the number of smaller elements.

I used the bisect_left and bisect_right to make it work for non-unique numbers as well,

from bisect import bisect_left
from bisect import bisect_right

def kthOfPiles(givenPiles, k, count):
    '''
    Perform binary search for kth element in  multiple sorted list

    parameters
    ==========
    givenPiles  are list of sorted list
    count   is the total number of
    k       is the target index in range [0..count-1]
    '''
    begins = [0 for pile in givenPiles]
    ends = [len(pile) for pile in givenPiles]
    #print('finding k=', k, 'count=', count)
    
    for pileidx,pivotpile in enumerate(givenPiles):
        
        while begins[pileidx] < ends[pileidx]:
            mid = (begins[pileidx]+ends[pileidx])>>1
            midval = pivotpile[mid]
            
            smaller_count = 0
            smaller_right_count = 0
            for pile in givenPiles:
                smaller_count += bisect_left(pile,midval)
                smaller_right_count += bisect_right(pile,midval)
                
            #print('check midval', midval,smaller_count,k,smaller_right_count)
            if smaller_count <= k and k < smaller_right_count:
                return midval
            elif smaller_count > k:
                ends[pileidx] = mid
            else:
                begins[pileidx] = mid+1
            
    return -1

Answer 8

If the k is not that huge, we can maintain a priority min queue. then loop for every head of the sorted array to get the smallest element and en-queue. when the size of the queue is k. we get the first k smallest .

maybe we can regard the n sorted array as buckets then try the bucket sort method.

Answer 9

This could be considered the second half of a merge sort. We could simply merge all the sorted lists into a single list...but only keep k elements in the combined lists from merge to merge. This has the advantage of only using O(k) space, but something slightly better than merge sort's O(n log n) complexity. That is, it should in practice operate slightly faster than a merge sort. Choosing the kth smallest from the final combined list is O(1). This is kind of complexity is not so bad.

Answer 10

Please find the below C# code to Find the k-th Smallest Element in the Union of Two Sorted Arrays. Time Complexity : O(logk)

public int findKthElement(int k, int[] array1, int start1, int end1, int[] array2, int start2, int end2)
    {
        // if (k>m+n) exception
        if (k == 0)
        {
            return Math.Min(array1[start1], array2[start2]);
        }
        if (start1 == end1)
        {
            return array2[k];
        }
        if (start2 == end2)
        {
            return array1[k];
        }
        int mid = k / 2;
        int sub1 = Math.Min(mid, end1 - start1);
        int sub2 = Math.Min(mid, end2 - start2);
        if (array1[start1 + sub1] < array2[start2 + sub2])
        {
            return findKthElement(k - mid, array1, start1 + sub1, end1, array2, start2, end2);
        }
        else
        {
            return findKthElement(k - mid, array1, start1, end1, array2, start2 + sub2, end2);
        }
    }