Katkat
Back

Merge Sorted Arrays

Fora TravelSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates competency in implementing and generalizing merge operations on sorted arrays, exercising algorithmic problem-solving, array manipulation, handling of edge cases (empty arrays, negative numbers, duplicates), and analysis of time and space complexity.

You are given two related tasks about sorted integer arrays.

  1. Implement a function that takes two arrays sorted in nondecreasing order and returns a new sorted array containing all elements from both inputs.
  2. Generalize the solution to merge K arrays, where each array is sorted in nondecreasing order, and return one sorted array containing all elements.

Requirements:

  • Preserve duplicates.
  • Handle empty arrays, negative numbers, and arrays of different lengths.
  • Return a new array rather than mutating the inputs.
  • Discuss the time and space complexity of your approach.