Merge Sorted Array solution and explanation
Google
Infosys
9 more videos on this problem
Merge Sorted Array - Leetcode 88 - PythonNeetCode · 10:18 · 355K views
Merge Sorted Array | Leetcode 88 | Top 150 interview question seriesTechnosage · 11:36 · 125K views
Merge Sorted Array | Live Coding with Explanation | Leetcode - 88Algorithms Made Easy · 4:50 · 112K views
Merge Sorted Array LeetCode 88 - Intuitive Guide + CodeCodingNinja · 11:54 · 52K views
Merge Sorted Array - Leetcode 88 - Arrays & Strings (Python)Greg Hogg · 6:08 · 25K views
LEETCODE 88 (JAVASCRIPT) | MERGE SORTED ARRAYAndy Gala · 9:43 · 16K views
Merge Sorted Array - LeetCode 88 - JavaLeetCode University · 11:40 · 16K views
Merge Sorted Array | LeetCode 88 | Coding Interview TutorialTerrible Whiteboard · 10:53 · 15K views
Merge Sorted Array LeetCode Java (#leetcode 88)Engineering Digest · 9:33 · 13K views
LeetCode 88: Merge Sorted Array | C# Solution | Two Pointer Technique |Code Scribbler · 8:16 · 398 views
The problem
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 + nnums2.length == n0 <= m, n <= 2001 <= 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`.
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
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
merge(nums1, 3, nums2, 3)
print(nums1)import java.util.Arrays;
public class MergeSortedArray {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = {2, 5, 6};
merge(nums1, 3, nums2, 3);
System.out.println(Arrays.toString(nums1));
}
}#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums1, int m, vector<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--];
}
}
int main() {
vector<int> nums1 = {1, 2, 3, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
merge(nums1, 3, nums2, 3);
for (int num : nums1) {
cout << num << " ";
}
return 0;
}function merge(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
let nums1 = [1, 2, 3, 0, 0, 0];
let nums2 = [2, 5, 6];
merge(nums1, 3, nums2, 3);
console.log(nums1);#include <stdio.h>
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--];
}
}
int main() {
int nums1[] = {1, 2, 3, 0, 0, 0};
int nums2[] = {2, 5, 6};
merge(nums1, 3, nums2, 3);
for (int i = 0; i < 6; i++) {
printf("%d ", nums1[i]);
}
return 0;
}using System;
public class MergeSortedArray {
public static void Merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
public static void Main() {
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = {2, 5, 6};
Merge(nums1, 3, nums2, 3);
Console.WriteLine(string.Join(", ", nums1));
}
}This Python solution also uses the two-pointer approach to place each element. The list's end ensures no interference with unsorted elements during the process.
Time Complexity: O(m + n); Space Complexity: O(1), as it modifies `nums1` in place without needing extra space.
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.
def merge(nums1, m, nums2, n):
nums1[m:] = nums2
nums1.sort()
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
merge(nums1, 3, nums2, 3)
print(nums1)import java.util.Arrays;
public class MergeSortedArray {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = {2, 5, 6};
merge(nums1, 3, nums2, 3);
System.out.println(Arrays.toString(nums1));
}
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
copy(nums2.begin(), nums2.end(), nums1.begin() + m);
sort(nums1.begin(), nums1.begin() + m + n);
}
int main() {
vector<int> nums1 = {1, 2, 3, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
merge(nums1, 3, nums2, 3);
for (int num : nums1) {
cout << num << " ";
}
return 0;
}function merge(nums1, m, nums2, n) {
nums1.splice(m, n, ...nums2);
nums1.sort((a, b) => a - b);
}
let nums1 = [1, 2, 3, 0, 0, 0];
let nums2 = [2, 5, 6];
merge(nums1, 3, nums2, 3);
console.log(nums1);#include <stdio.h>
#include <stdlib.h>
int compare (const void * a, const void * b) {
return (*(int*)a - *(int*)b);
}
void merge(int* nums1, int m, int* nums2, int n) {
int totalLength = m + n;
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
qsort(nums1, totalLength, sizeof(int), compare);
}
int main() {
int nums1[] = {1, 2, 3, 0, 0, 0};
int nums2[] = {2, 5, 6};
merge(nums1, 3, nums2, 3);
for (int i = 0; i < 6; i++) {
printf("%d ", nums1[i]);
}
return 0;
}using System;
public class MergeSortedArray {
public static void Merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
Array.Sort(nums1);
}
public static void Main() {
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = {2, 5, 6};
Merge(nums1, 3, nums2, 3);
Console.WriteLine(string.Join(", ", nums1));
}
}This straightforward Python method merges `nums2` directly into `nums1` and sorts the combined array utilizing Python's built-in sort capabilities.
Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) in-place sorting beyond `nums1` content change.
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).
/**
Do not return anything, modify nums1 in-place instead.
*/
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
for (let i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}func merge(nums1 []int, m int, nums2 []int, n int) {
for i, j, k := m-1, n-1, m+n-1; j >= 0; k-- {
if i >= 0 && nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
}
}impl Solution {
pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
let mut k = (m + n - 1) as usize;
let mut i = (m - 1) as isize;
let mut j = (n - 1) as isize;
while j >= 0 {
if i >= 0 && nums1[i as usize] > nums2[j as usize] {
nums1[k] = nums1[i as usize];
i -= 1;
} else {
nums1[k] = nums2[j as usize];
j -= 1;
}
k -= 1;
}
}
}class Solution {
/**
* @param Integer[] $nums1
* @param Integer $m
* @param Integer[] $nums2
* @param Integer $n
* @return NULL
*/
function merge(&$nums1, $m, $nums2, $n) {
while (count($nums1) > $m) {
array_pop($nums1);
}
for ($i = 0; $i < $n; $i++) {
array_push($nums1, $nums2[$i]);
}
asort($nums1);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Start from the End with Two Pointers | Time Complexity: O(m + n); Space Complexity: O(1), as it modifies `nums1` in place without needing extra space. |
| Use Extra Space to Combine and Sort | Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) in-place sorting beyond `nums1` content change. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Combine then Sort | O((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 |
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.