FastPrepMerge Two Sorted Arrays In Place

Merge Two Sorted Arrays In Place

Infosys logoInfosys● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

You are given two nonempty integer arrays, first and second, each sorted in nondecreasing order.

Rearrange their existing elements using O(1) auxiliary storage so that both arrays remain sorted and every element of first is less than or equal to every element of second. Do not call a built-in sorting function.

Return the two mutated arrays as [first, second]. The returned outer array is only the judging container and does not relax the constant-extra-space requirement for the rearrangement.

Function

mergeSortedArrays(first: int[], second: int[]) → int[][]

Examples

Example 1

first = [1,4,7,8,10]second = [2,3,9]return = [[1,2,3,4,7],[8,9,10]]

The eight values in global sorted order are [1, 2, 3, 4, 7, 8, 9, 10]. The first five remain in first and the final three remain in second.

Example 2

first = [1,2,2]second = [2,3]return = [[1,2,2],[2,3]]

Equal values may appear on both sides of the final boundary.

Constraints

  • 1 <= first.length <= 200000
  • 1 <= second.length <= 200000
  • Both arrays are initially sorted in nondecreasing order.
  • Every value fits in a signed 32-bit integer.
  • Duplicate values are allowed.
  • Use O(1) auxiliary storage and do not call a built-in sorting function.

More Infosys problems

See Infosys hiring insights
public int[][] mergeSortedArrays(int[] first, int[] second) {
  // write your code here
}
first[1,4,7,8,10]
second[2,3,9]
expected[[1,2,3,4,7],[8,9,10]]
Checking account…