Merge Sorted Array Solution - Leetcode

Understand Merge Sorted Array (88 Leetcode) with Solution

11 October 2025

This document presents the solution to the problem 88 - Merge Sorted Array - Leetcode.

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

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

 

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

The problem requires tracking the pointer to the current elements getting inserted to the nums1 array.
We will keep 2 pointers, pointing to the elements from the nums1 and nums2 array.
The element to be inserted into nums1 can be from either num1 or nums2. They are the source arrays.
Once the element is inserted at the correct position, the pointer from the source array will be updated.
Let’s use the following variables for developing the solution:
- nums1: [1, 2, 7, 9, 0, 0]
- nums2: [3, 8]
Pointers:
- The pointer i points to the last element of the nums1 array.
- The pointer j points to the last element of the nums2 array.
- The pointer k points to the position at which either nums[i] or nums[j] will be inserted.
Iterations:
- 1st Iteration: We compare the values pointed by i and j:
  - nums1[i] (9) is greater than nums2[j] (8), nums1[k] will be updated with nums1[i].
  - nums1[i] becomes 0.
  - i will be decremented so that it points to the next largest element from nums1[i].
  - j will not be decremented.
  - k will be decremented. It will point to the new location at which next element will be placed.
- 2nd Iteration: nums1[i] now points to 7 and nums2[j] now points to 8:
  - nums2[j] is greater than nums1[i].
  - nums1[k] will be updated to nums2[j] value.
  - i will not be decremented.
  - j will be decremented. We can skip setting nums2[j] to 0 as this index will never be accessed again in the program.
  - k will be decremented.
- 3rd Iteration: nums1[i] points to 7 and nums2[j] now points to 3:
  - State after the updates based on the current values.
- 4th Iteration: nums1[i] now points to 2 and nums2[j] points to 3:
  - State after the updates based on the current values.
- With the previous iteration, we’ve covered all the elements from the nums[2] array, i.e., j < 0. Iteration breaks here.
Edge Case: All the remaining elements from nums1 are greater than the largest elements of the nums2
- nums1: [3, 4, 5, 6, 0, 0]
- nums2: [1, 2]
- Since 2 is smaller than all the values that nums1[i] will point to, the zeros in nums1 will be shifted to the left.
- The loop shall end because i < 0.
- Since j >= 0, as not all the elements were traversed in the loop, we will have to copy the values from nums2 to nums1.

Please do provide some comments if you find the explanation a bit lacking.

// Approach
//
// - Set pointers i = m - 1, j = n - 1 and k = len(a) -1
// - if nums1[i] > nums2[j]
//   - move num1[i] to nums1[k], i-- and k--
//   - nums1[i] before decrement contains 0
// - if nums1[i] < nums2[j]
//   - set nums1[k] = nums2[j], j-- and k--
// - if i < 0 and j >= 0
//   - This means, all the elements left in nums2 are lower than current head of nums1.
//   - copy all the element from nums2 0 to j to nums1 from 0 to j
func merge(nums1 []int, m int, nums2 []int, n int) {
	k := len(nums1) - 1
	i := m - 1
	j := n - 1

	for {
		if j < 0 || i < 0 {
			break
		}
		if nums2[j] < nums1[i] {
			nums1[k] = nums1[i]
			nums1[i] = 0
			k--
			i--
		} else {
			nums1[k] = nums2[j]
			k--
			j--
		}

	}

	if j < 0 {
		return
	}

	for j >= 0 {
		nums1[j] = nums2[j]
		j--
	}
}

Loading Comments... Disqus Loader

Merge Sorted Array Solution - Leetcode

Understand Merge Sorted Array (88 Leetcode) with Solution

Related Pages: