Merge Sorted Array – LeetCode (Top Interview 150)

Problem Link: LeetCode - Merge Sorted Array

Problem Statement

You are given two sorted integer arrays, nums1 and nums2, and two integers m and n representing the number of elements in nums1 and nums2 respectively.

Merge nums2 into nums1 as one sorted array in-place.

Intuition

Instead of merging from the start (which would require shifting elements and extra space), we merge from the end since nums1 already has extra space to hold nums2. This way, we avoid overwriting useful elements and efficiently place the largest numbers first.

Approach

Example:

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

• Start pointers from the end of both arrays.

• Compare the elements and insert the larger one at the rightmost position in nums1.

• Decrement the pointer and continue until nums2 is exhausted.

Step-by-Step Walkthrough

Iteration Visualization:

Initial:
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]

Compare 3 and 6 → Place 6 at the end:
[1,2,3,0,0,6]

Compare 3 and 5 → Place 5:
[1,2,3,0,5,6]

Compare 3 and 2 → Place 3:
[1,2,3,3,5,6]

Compare 2 and 2 → Place 2 (nums2):
[1,2,2,3,5,6]

✅ Final Result: [1,2,2,3,5,6]

Code Implementation (Optimal Solution – O(m+n) Time, O(1) Space)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        midx = m - 1
        nidx = n - 1 
        right = m + n - 1

        while nidx >= 0:
            if midx >= 0 and nums1[midx] > nums2[nidx]:
                nums1[right] = nums1[midx]
                midx -= 1
            else:
                nums1[right] = nums2[nidx]
                nidx -= 1
            right -= 1

Alternative Approach (Simpler but Less Efficient – O((m+n)log(m+n)))

If simplicity is preferred, append nums2 into nums1 and sort.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2
        nums1.sort()

Complexity Analysis

✅ Time Complexity:

• Optimal: O(m+n) (Single pass from the end)

• Simpler: O((m+n)log(m+n)) (Sorting after merging)

✅ Space Complexity:

• Optimal: O(1) (In-place merge)

• Simpler: Depends on sorting algorithm.

Solution Video (Credits to niits YouTube Channel)

🎥 Watch Solution Video

Key Points

• Always iterate from the end when merging sorted arrays in-place.

• Stop only when all elements from nums2 are merged.

• If nums2 is exhausted early, no extra steps are needed for nums1.

✅ This approach is commonly used in coding interviews and is part of LeetCode's Top Interview 150.