Merge Sorted Arrays

Problem Link

88. Merge Sorted Array – LeetCode

Problem: Merge Two Sorted Arrays In-Place

Problem Statement

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order, and two integers m and n, which represent the number of elements in nums1 and nums2 respectively.

You have to merge nums2 into nums1 in-place, so that nums1 becomes a single sorted array of size m + n.

Note:

• nums1.length == m + n

• The first m elements in nums1 are the elements to merge.

• The last n elements in nums1 are zeros, reserved for the merge.

• nums2.length == n

Examples

Example 1
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Example 3
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

Constraints

• nums1.length == m + n

• nums2.length == n

• 0 <= m, n <= 200

• 1 <= m + n <= 200

• -10⁹ <= nums1[i], nums2[j] <= 10⁹

Intuition

We are merging two sorted arrays, and we want to keep the result in nums1 without using extra space beyond what's already given. A straightforward approach is to merge from the end to avoid overwriting elements in nums1.

However, the provided code first creates a copy of the m elements of nums1 and then merges using the standard two-pointer technique.

Approach

1. Copy the first m elements of nums1 into a temporary array nums1C.

2. Use three pointers:

   • i to iterate nums1C

   • j to iterate nums2

   • k to fill up nums1

3. Compare elements from nums1C and nums2, place the smaller into nums1[k], and increment pointers accordingly.

4. If one array is exhausted, copy the remaining elements of the other array.

Code (Java)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1C = new int[m];
        for (int i = 0; i < m; i++) {
            nums1C[i] = nums1[i];
        }

        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1C[i] < nums2[j]) {
                nums1[k++] = nums1C[i++];
            } else {
                nums1[k++] = nums2[j++];
            }
        }

        while (i < m) {
            nums1[k++] = nums1C[i++];
        }

        while (j < n) {
            nums1[k++] = nums2[j++];
        }
    }
}

Time and Space Complexity

• Time Complexity: O(m + n)
  Each element from both arrays is processed exactly once.

• Space Complexity: O(m)
  Because a copy of the first m elements of nums1 is stored in an auxiliary array.

Dry Run

Input:

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

Step-by-Step:

• Copy nums1C = [1,2,3]

• Initialize: i = 0, j = 0, k = 0

Iteration 1:
nums1C[0] = 1 < 2 = nums2[0]
→ nums1[0] = 1
→ i = 1, k = 1

Iteration 2:
nums1C[1] = 2 == 2 = nums2[0]
→ nums1[1] = 2 (choose nums2 first)
→ j = 1, k = 2

Iteration 3:
nums1C[1] = 2 < 5 = nums2[1]
→ nums1[2] = 2
→ i = 2, k = 3

Iteration 4:
nums1C[2] = 3 < 5 = nums2[1]
→ nums1[3] = 3
→ i = 3, k = 4

Copy remaining nums2:
nums1[4] = 5, nums1[5] = 6

Final Output:

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

Alternate Approach (Optimized, No Extra Space)

Start merging from the end of both arrays:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
    }
}

• Time Complexity: O(m + n)

• Space Complexity: O(1) (in-place)

Conclusion

This problem reinforces array manipulation skills, particularly in-place modification. While the two-pointer method using a temporary array is easy to understand, the in-place reverse merging strategy is preferred for space optimization.