FastPrep
Problem · Heap

Merge Multiple Sorted Streams

Learn this problem
● MediumNvidia logoNvidiaFULLTIMEPHONE SCREEN

Problem statement

You are given streams, where each inner array is an independently sorted stream of integers in nondecreasing order. Merge every value from every stream into one nondecreasing array.

Preserve every occurrence, including duplicates. Empty streams are valid. Process the inputs as independent ordered streams rather than concatenating and sorting all values again.

Function

mergeSortedStreams(streams: int[][]) → int[]

Examples

Example 1

streams = [[1,4,7],[2,2,9],[3,8]]return = [1,2,2,3,4,7,8,9]

The next smallest available head is selected until every stream is exhausted. Both copies of 2 remain in the result.

Example 2

streams = [[],[-5,0,6],[1],[1,10]]return = [-5,0,1,1,6,10]

Empty streams contribute nothing, and equal values from different streams are both preserved.

Example 3

streams = []return = []

With no streams, the merged result is empty.

Constraints

  • 0 <= streams.length <= 100
  • 0 <= streams[i].length
  • The total number of values across all streams is at most 100000.
  • -1000000000 <= streams[i][j] <= 1000000000
  • Every inner array is sorted in nondecreasing order.

More Nvidia problems

drafts saved locally
public int[] mergeSortedStreams(int[][] streams) {
    // Write your solution here
}
streams[[1,4,7],[2,2,9],[3,8]]
expected[1,2,2,3,4,7,8,9]
checking account