Domain 1EasyCORE

Merge Sorted Array

The problem requires merging two sorted integer arrays, `nums1` and `nums2`, into one sorted array. The key points are: - `nums1` has enough space at the end to accommodate all elements from `nums2`. - The number of initialized elements in `nums1` is `m`, and in `nums2` is `n`. - We need to merge `nums2` into `nums1` in-place.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Two Pointers

88. Merge Sorted Array

Model: qwen2.5-coder:14b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 40.9%


Problem Breakdown

The problem requires merging two sorted integer arrays, nums1 and nums2, into one sorted array. The key points are:

  • nums1 has enough space at the end to accommodate all elements from nums2.
  • The number of initialized elements in nums1 is m, and in nums2 is n.
  • We need to merge nums2 into nums1 in-place.

Inputs:

  • nums1: A list of integers with length m + n, where the last n elements are zeros.
  • m: An integer representing the number of initialized elements in nums1.
  • nums2: A list of integers with length n.
  • n: An integer representing the number of elements in nums2.

Outputs:

  • The merged sorted array, which is stored in nums1.

Implicit constraints or edge cases:

  • If m is 0, then nums1 should be replaced entirely by nums2.
  • If n is 0, then nums1 remains unchanged.
  • Both arrays can contain negative numbers and duplicates.

Intuition

A brute-force approach would involve copying the elements of nums1 into a temporary array, then merging both arrays back into nums1. This approach has a time complexity of O(m + n) but requires additional space for the temporary array, which is not ideal since we want to perform the merge in-place.

The key insight is to start from the end of both arrays and work backwards. Since nums1 has extra space at the end, we can use it to store the merged elements without overwriting any unprocessed elements from nums2. This approach allows us to merge the arrays in O(m + n) time complexity with O(1) additional space.

Approach

  1. Initialize three pointers:

    • i pointing to the last element of the initialized part of nums1 (index m - 1).
    • j pointing to the last element of nums2 (index n - 1).
    • k pointing to the last position of nums1 (index m + n - 1).
  2. Iterate while both i and j are non-negative:

    • Compare the elements at nums1[i] and nums2[j].
    • Place the larger element at nums1[k] and decrement the corresponding pointer (i or j) and k.
  3. If there are remaining elements in nums2 (i.e., j >= 0), copy them into nums1. This step is necessary because if there are remaining elements in nums1, they are already in place.

  4. The final nums1 will be the merged sorted array.

Complexity Analysis

  • Time complexity: O(m + n). We iterate through both arrays once.
  • Space complexity: O(1). We use only a constant amount of extra space for pointers.

Solution

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # If there are remaining elements in nums2, copy them
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

# Example usage:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 2, 3, 5, 6]

Edge Cases Handled

  • If m is 0, the entire nums1 will be replaced by nums2.
  • If n is 0, nums1 remains unchanged.
  • The code handles arrays with negative numbers and duplicates correctly.