Skip to main content
Talentd

Merge Sorted Array - Solution & Explanation

EasyArrayTwo PointersSorting19 min readAsked at: Amazon, Microsoft, Apple +34
Practice this problem

Problem Statement

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.

 

Constraints:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

 

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Approach Overview

Problem Overview: You receive two sorted integer arrays nums1 and nums2 with sizes m and n. The first array has enough trailing space to hold all elements from both arrays. Your task is to merge nums2 into nums1 so that the final array remains sorted.

Approach 1: Use Extra Space to Combine and Sort (Time: O((m+n) log(m+n)), Space: O(m+n))

The straightforward method copies the first m elements of nums1 and all n elements of nums2 into a temporary array. After combining the values, apply a standard sort operation. This approach relies on built-in sorting algorithms such as quicksort or mergesort. The implementation is simple and easy to reason about, but it ignores the fact that both input arrays are already sorted. Because sorting dominates the runtime, the total complexity becomes O((m+n) log(m+n)) with O(m+n) additional memory. It works as a quick baseline but is rarely the optimal choice in interviews.

Approach 2: Start from the End with Two Pointers (Time: O(m+n), Space: O(1))

The optimal strategy uses the fact that both arrays are already sorted. Instead of merging from the front, place three pointers at the end: one at m-1 in nums1, one at n-1 in nums2, and one at m+n-1 where the next largest element should be written. Compare the values from both arrays and write the larger one into the back of nums1. Move the corresponding pointer and repeat until all elements from nums2 are placed.

This works because the extra space at the end of nums1 allows safe overwriting without losing unprocessed values. Each element is visited once, giving O(m+n) time and O(1) additional space. The technique is a classic two pointers pattern applied to sorted data. Problems involving merging sorted structures frequently rely on similar logic.

Understanding how sorted properties reduce work is key here. Instead of re-sorting the entire dataset, you only perform comparisons and pointer moves. The idea also appears in merge steps of merge sort and other sorting algorithms. Because the arrays are sequential structures, the implementation naturally fits common array manipulation patterns.

Recommended for interviews: The two-pointer approach from the end is the expected solution. Interviewers want to see that you recognize the unused buffer in nums1 and avoid unnecessary sorting. Mentioning the extra-space baseline first shows understanding of simpler strategies, but implementing the O(m+n) in-place merge demonstrates stronger algorithmic thinking.

Approach 1: Start from the End with Two Pointers

The most efficient way to merge two sorted arrays without using extra space is by using a two-pointer approach from the end. You start comparing elements from the end of both arrays and fill `nums1` from the back. This way you avoid needing additional space for a temporary array and can overwrite existing data in `nums1`.

This C implementation uses a two-pointer technique starting from the back of the arrays `nums1` and `nums2`. It compares elements of both arrays from the end and places the larger element at the current end position in `nums1`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space.

Try this approach in the editor →

Approach 2: Use Extra Space to Combine and Sort

This is a less efficient approach that involves first combining the contents of `nums1` and `nums2` into a new array. Then, the new array is sorted, and its contents are copied back into `nums1`. Although straightforward, this approach involves extra memory allocation.

In C, we first append the elements of `nums2` onto `nums1`, and then employ the Quick Sort function `qsort` to sort the entire array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting.

Try this approach in the editor →

Approach 3: Two Pointers

We use two pointers i and j pointing to the end of two arrays, and a pointer k pointing to the end of the merged array.

Every time we compare the two elements at the end of the two arrays, and move the larger one to the end of the merged array. Then we move the pointer one step forward, and repeat this process until the two pointers reach the start of the arrays.

The time complexity is O(m + n), where m and n are the lengths of two arrays. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptPHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Start from the End with Two Pointers

Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space.

Use Extra Space to Combine and Sort

Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Combine then SortO((m+n) log(m+n))O(m+n)Quick baseline solution when simplicity matters more than efficiency
Two Pointers from the End (In-place Merge)O(m+n)O(1)Best choice when arrays are already sorted and memory must remain constant

Video Solution

Merge Sorted Array - Leetcode 88 - Python • NeetCode • 355,925 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Merge Sorted Array easy or hard?
Merge Sorted Array is classified as an Easy problem on LeetCode. The challenge comes from recognizing that merging should start from the end to avoid overwriting elements in nums1.
How to solve Merge Sorted Array in O(n)?
Place pointers at the end of nums1 and nums2 and another pointer at the final index of nums1. Compare elements from the back and insert the larger value into nums1[m+n-1]. Move pointers accordingly until nums2 is fully merged. This processes each element once for O(m+n) time.
What is the best approach for Merge Sorted Array?
The best approach uses two pointers starting from the end of both arrays. Compare the largest remaining elements and place the larger one at the back of nums1. This avoids overwriting values and merges the arrays in O(m+n) time with O(1) extra space.
What data structure is used in Merge Sorted Array?
The problem primarily uses arrays along with the two-pointer technique. Pointer indices track positions in nums1 and nums2 while iterating from the end to maintain sorted order during the merge.
What is the time complexity of Merge Sorted Array?
The optimal in-place merge runs in O(m+n) time because each element from both arrays is processed once. The space complexity is O(1) since the merge happens directly inside nums1 without additional memory.
Merge Sorted Array Python or Java solution available?
Implementations are commonly written in Python, Java, C++, JavaScript, and C#. The logic is identical across languages: maintain three indices and place the larger value at the end of nums1 during each iteration.
Is Merge Sorted Array asked at Google, Amazon, or Meta?
Merge Sorted Array is a common entry-level interview question used by companies like Amazon, Google, and Meta to test understanding of arrays and two-pointer techniques. It checks whether candidates can optimize using sorted properties instead of re-sorting data.

Ready to solve this problem?

Practice Merge Sorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Interval List Intersections

Next

Merge Two Sorted Lists