Merge two sorted arrays in-place

Q: Merge two sorted arrays in-place

This question evaluates proficiency in array manipulation, in-place merging concepts, and understanding of time and space complexity when combining sorted sequences. Commonly asked in the coding and algorithms domain (arrays/sorting), it tests practical implementation skills and the ability to produce efficient, low-memory solutions while handling ordering constraints and edge cases.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two integer arrays sorted in non-decreasing order, and two integers m and n:

nums1 has length m + n . The first m elements of nums1 contain valid numbers in sorted order. The last n elements of nums1 are placeholders (you can assume they are set to any values and should be ignored).
nums2 has length n , and all n elements are valid and sorted in non-decreasing order.

Write an algorithm that merges the elements of nums2 into nums1 so that nums1 becomes a single sorted array containing all m + n elements, in-place (i.e., without using an additional array of size m + n).

Return value is not required; modify nums1 directly.

Example

Input:

nums1 = [1, 3, 5, 0, 0, 0] , m = 3
nums2 = [2, 4, 6] , n = 3

After calling your function, nums1 should become:

nums1 = [1, 2, 3, 4, 5, 6]

Constraints

0 <= m, n <= 10^5
len(nums1) = m + n
len(nums2) = n
Arrays are already sorted in non-decreasing order.

Describe the algorithm and then implement it in the language of the interviewer's choice.

Merge two sorted arrays in-place

Overview

Example

Constraints

Comments (0)