Merge Sorted Array — O(m+n) In-Place from End [Meta Top Question]
Sanjeev SharmaAdvertisement
Problem Statement
You are given two integer arrays
nums1andnums2, sorted in non-decreasing order, and two integersmandn, representing the number of elements innums1andnums2respectively. Mergenums2intonums1in-place.nums1has extra space at the end to holdnums2.
Example:
Input: nums1 = [1,2,3,0,0,0], m=3 nums2 = [2,5,6], n=3
Output: [1,2,2,3,5,6]
Intuition
Fill from the end: Instead of inserting and shifting (O(m·n)), place the largest elements at the back of nums1 first. Use three pointers: p1 = m-1, p2 = n-1, write = m+n-1.
p1 = m-1, p2 = n-1, write = m+n-1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]; p1--
else:
nums1[write] = nums2[p2]; p2--
write--
# Copy remaining nums2 (if any)
while p2 >= 0:
nums1[write--] = nums2[p2--]
Why does this work? We always place the globally largest remaining element, and we never overwrite an element of nums1 that hasn't been considered yet.
Solutions in All 5 Languages
C
void merge(int* nums1, int m, int* nums2, int n) {
int p1 = m - 1, p2 = n - 1, write = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2])
nums1[write--] = nums1[p1--];
else
nums1[write--] = nums2[p2--];
}
while (p2 >= 0) nums1[write--] = nums2[p2--];
}
C++
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m-1, p2 = n-1, write = m+n-1;
while (p1 >= 0 && p2 >= 0) {
nums1[write--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0) nums1[write--] = nums2[p2--];
}
};
Java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m-1, p2 = n-1, write = m+n-1;
while (p1 >= 0 && p2 >= 0) {
nums1[write--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0) nums1[write--] = nums2[p2--];
}
}
JavaScript
function merge(nums1, m, nums2, n) {
let p1 = m-1, p2 = n-1, write = m+n-1;
while (p1 >= 0 && p2 >= 0) {
nums1[write--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0) nums1[write--] = nums2[p2--];
}
Python
from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
p1, p2, write = m-1, n-1, m+n-1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]; p1 -= 1
else:
nums1[write] = nums2[p2]; p2 -= 1
write -= 1
while p2 >= 0:
nums1[write] = nums2[p2]; p2 -= 1; write -= 1
Complexity: O(m+n) time, O(1) space
Advertisement
