FastPrep
Problem · Array

K Smallest Elements from Sorted Arrays

Learn this problem
● MediumeBay logoeBayFULLTIMEPHONE SCREEN

Problem statement

You are given an array of integer arrays arrays. Each inner array is sorted in nondecreasing order. Return the k smallest values across all inner arrays in nondecreasing order.

Duplicate values occupy separate positions and must be retained. An empty inner array contributes no values. When k is zero, return an empty array.

Do not insert every input value into a heap. Maintain at most one current candidate from each nonempty inner array.

Function

kSmallestElements(arrays: int[][], k: int) → int[]

Examples

Example 1

arrays = [[1,4,7],[2,5],[3,6,9]]k = 5return = [1,2,3,4,5]

The first five values in the merged order are 1, 2, 3, 4, 5.

Example 2

arrays = [[],[-3,-1,2],[-3,4]]k = 4return = [-3,-3,-1,2]

Both occurrences of -3 are retained, and the empty array is ignored.

Constraints

  • 1 <= arrays.length <= 10000
  • 0 <= arrays[i].length
  • The total number of values across all arrays is at most 200000.
  • Each inner array is sorted in nondecreasing order.
  • -2147483648 <= arrays[i][j] <= 2147483647
  • 0 <= k <= the total number of values.

More eBay problems

drafts saved locally
public int[] kSmallestElements(int[][] arrays, int k) {
    // Write your code here
}
arrays[[1,4,7],[2,5],[3,6,9]]
k5
expected[1,2,3,4,5]
checking account