Katkat
Back

Combine Many Sorted Integer Arrays into One Non-Decreasing Array

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

A coding question asking you to merge many integer arrays, each already sorted in non-decreasing order, into a single sorted array that keeps every duplicate value. It tests multi-way merging, efficiency as the number of input arrays grows, and edge cases such as empty inputs and arrays of different lengths.

You are given a collection of integer arrays, each already sorted in non-decreasing order. Combine them into one array that contains every element of every input array, sorted in non-decreasing order.

Function Signature

def merge_sorted_arrays(lists: list[list[int]]) -> list[int]:

Rules

  • Keep duplicates: a value appears in the output exactly as many times as it appears across all input arrays combined.
  • The output is in non-decreasing order, so the answer is unique.
  • lists may be empty, and any input array may be empty. If there are no elements at all, return [].
  • The input arrays may have different lengths.

Constraints

  • 0 <= len(lists) <= 10^4
  • 0 <= len(lists[i]) <= 500
  • The total number of elements across all arrays is at most 10^4.
  • -10^4 <= lists[i][j] <= 10^4
  • Each lists[i] is sorted in non-decreasing order.

Examples

Example 1

Input: lists = [[2, 5, 9], [1, 5], [3, 8, 10]]
Output: [1, 2, 3, 5, 5, 8, 9, 10]

Both copies of 5 are kept.

Example 2

Input: lists = []
Output: []

Example 3

Input: lists = [[], [-3, -3, 0], [-5]]
Output: [-5, -3, -3, 0]

The empty array contributes nothing; the other two are interleaved.