Finding kth smallest number from n sorted arrays

by

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.

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. Algorithm for all subsets of Array
  3. How to sort in-place using the merge sort algorithm?
  4. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  5. Finding three elements in an array whose sum is closest to a given number
  6. Given an array of numbers, return array of products of all other numbers (no division)
  7. Array versus linked-list
  8. How to find the kth smallest element in the union of two sorted arrays?
  9. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  10. Can min/max of moving window achieve in O(N)?
  11. Print two-dimensional array in spiral order
  12. Find the Smallest Integer Not in a List
  13. Find the majority element in array
  14. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  15. Algorithm to determine if array contains n…n+m?
  16. Find all subsets of length k in an array
  17. Grouping arrays in PHP
  18. Maximum single-sell profit
  19. A data structure supporting O(1) random access and worst-case O(1) append?
  20. In-place array reordering?
  21. find pair of numbers in array that add to given sum
  22. Regarding in-place merge in an array
  23. Interview question: three arrays and O(N*N)
  24. How to find repeating sequence of characters in a given array?
  25. Algorithm for merging two max heaps?
  26. Maximum sum of non consecutive elements
  27. calculating the number of “inversions” in a permutation
  28. How do I Merge two Arrays in VBA?
  29. jq: recursively merge objects and concatenate arrays
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment