Coding

Merge two sorted arrays without extra space

Asked at

Goldman Sachs

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given two integer arrays **nums1 **and nums2. Both arrays are sorted in non-decreasing order.

Merge **both **the arrays into a **single **array **sorted **in non-decreasing order.

The **final **sorted array should be stored inside the array **nums1 **and it should be done in-place.
nums1 has a length of m + n, where the first m elements denote the elements of nums1 and rest are 0s.
**nums2 **has a length of n.

Input: nums1 = [-5, -2, 4, 5], nums2 = [-3, 1, 8] Output: [-5, -3, -2, 1, 4, 5, 8] Explanation: The merged array is: [-5, -3, -2, 1, 4, 5, 8], where [-5, -2, 4, 5] are from nums1 and [-3, 1, 8] are from nums2

Input: nums1 = [0, 2, 7, 8], nums2 = [-7, -3, -1] Output: [-7, -3, -1, 0, 2, 7, 8] Explanation: The merged array is: [-7, -3, -1, 0, 2, 7, 8], where [0, 2, 7, 8] are from nums1 and [-7, -3, -1] are from nums2

Input: nums1 = [1, 3, 5], nums2 = [2, 4, 6, 7]

n == nums2.length.
m + n == nums1.length.
0 <= n, m <= 1000
-104 <= nums1[i], nums2[i] <= 104
Both nums1 and nums2 are sorted in non-decreasing order.

cpp

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
    }
};

java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    }
}

python

class Solution:
    def merge(self, nums1, m, nums2, n):

javascript

class Solution {
    merge(nums1, m, nums2, n) {

    }
}

csharp

public class Solution
{
    public void Merge(IList<int> nums1, int m, IList<int> nums2, int n)
    {
        
    }
}

func merge(nums1 []int, m int, nums2 []int, n int) {

}

Stuck? Show a way to structure it+

01Set pointers at the last valid elements of both arrays and at nums1's final slot.
02Compare from the back and write the larger value into the write pointer.
03Move the corresponding pointer backward.
04Copy any remaining nums2 prefix; remaining nums1 values are already placed.

Reference answer

Because nums1 has spare capacity at its end, merge from right to left. Let i=m-1, j=n-1, and write=m+n-1. Put the larger of nums1[i] and nums2[j] at nums1[write], then decrement the chosen input pointer and write. Once j is exhausted, the untouched prefix of nums1 is already correct. If i is exhausted first, copy the rest of nums2. This takes O(m+n) time and O(1) extra space. Merging from the front overwrites unprocessed nums1 values; also distinguish the logical length m from the physical buffer length.

Then expect these follow-ups

How would you merge two arrays when neither has spare capacity?
Tests: space trade-offs
How would you merge k sorted arrays?
Tests: heap design

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question