Practice/Microsoft/Leetcode 88. Merge Sorted Array

Leetcode 88. Merge Sorted Array

CodingMust

Problem

You are given two arrays that contain integers in sorted (non-decreasing) order:

• nums1 has a total length of m + n. The first m positions contain valid sorted elements, and the remaining n positions are filled with zeros as placeholders.
• nums2 has a length of n and contains valid sorted elements.

Your task is to merge all elements from nums2 into nums1 so that nums1 becomes a single sorted array containing all m + n elements. You must perform this operation in-place, modifying nums1 directly without allocating a new array.

Requirements

1. Modify nums1 in-place to contain all elements from both arrays in sorted order
2. Do not return anything; the function should modify nums1 directly
3. Achieve O(m + n) time complexity
4. Use O(1) extra space (excluding the input arrays)

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 ≤ m, n ≤ 200
• 1 ≤ m + n ≤ 200
• -109 ≤ nums1[i], nums2[j] ≤ 109
• The first m elements of nums1 and all elements of nums2 are in non-decreasing order

Examples

Example 1:

Input: nums1 = [1, 3, 5, 0, 0, 0], m = 3, nums2 = [2, 4, 6], n = 3 Output: nums1 = [1, 2, 3, 4, 5, 6] Explanation: We merge [1, 3, 5] and [2, 4, 6] to get [1, 2, 3, 4, 5, 6]

Example 2:

Input: nums1 = [1, 2, 3], m = 3, nums2 = [], n = 0 Output: nums1 = [1, 2, 3] Explanation: When nums2 is empty, nums1 stays as is

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: nums1 = [1] Explanation: nums1 initially has no valid elements, so we just copy nums2