FastPrep
Problem · Array

Merge Two Sorted Arrays In Place

Learn this problem
● Hardinfosys logoinfosysNEW GRADONSITE INTERVIEW

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

drafts saved locally
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