Merge Two Sorted Arrays in-place

By | October 6, 2021

Problem

Two integer arrays nums1 and nums2 are sorted in non-decreasing order, and two integers m and n are supplied representing the number of integers in nums1 and nums2 correspondingly.

In a single pass, merge nums1 and nums2 into a single array.

Vamware

The final classified array should be kept inside the array nums1 rather than returned by the function. To do this, nums1 has a length of m + n where the elements of the first m indicate the items of nums1. The length of nums2 is n.

Brute force approach

We can copy all the elements of nums2 into nums1 and then sort the entire array. This is an easy yet inefficient solution as this is not in-place and takes O((m+n)log(m+n)) time.

Efficient Approach

We can follow a 3 pointers approach. We place one pointer at the ending element of the first array and the second pointer at the ending element of the second array. Let’s say pointers are one and two respectively. The third pointer tells the next available index to place the element. This is initialized to the (size of nums1-1). Let’s call this variable as finish.
We then compare these two elements. If nums1[one] >= nums2[two], we  place this element at the last index of nums1 and decrease finish and vice versa.

We do this until all the pointers are greater than or equal to 0.  

This is an in-place solution and takes O(m+n) time.

C++

#include <iostream>
#include <algorithm>
using namespace std;
 void solve(int a[], int b[], int m, int n)
{

    for (int i = 0; i < m; i++)
    {

        if (a[i] > b[0])
        {
            swap(a[i], b[0]);
            int first = b[0];
 
            int k;
            for (k = 1; k < n && b[k] < first; k++) {
                b[k - 1] = b[k];
            }
 
            b[k - 1] = first;
        }
    }
}
 
int main()
{
    int a[] = { 1, 3, 4, 5 };
    int b[] = { 2, 3, 10 };
 
    int m = sizeof(a) / sizeof(a[0]);
    int n = sizeof(b) / sizeof(b[0]);
 
    solve(a, b, m, n);
 
for(int i=0;i<m;i++) cout<<a[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<b[i]<<" ";
 
    return 0;
}

Python

def solve(a, b):
 
    m = len(a)
    n = len(b)
    for i in range(m):
 
        if a[i] > b[0]:
            temp = a[i]
            a[i] = b[0]
            b[0] = temp
 
            first = b[0]
            k = 1
            while k < n and b[k] < first:
                b[k - 1] = b[k]
                k = k + 1
 
            b[k - 1] = first
 
a = [1, 4, 7, 8, 10]
b = [2, 3, 9]
 
solve(a, b)
 
print(a)
print(b)

C

void solve(int a[], int b[], int m, int n)
{

    for (int i = 0; i < m; i++)
    {

        if (a[i] > b[0])
        {
            int temp = a[i];
            a[i]=b[0];
            b[0]=temp;
            int first = b[0];
 

            int k;
            for (k = 1; k < n && b[k] < first; k++) {
                b[k - 1] = b[k];
            }
 
            b[k - 1] = first;
        }
    }
}
 
int main()
{
    int a[] = { 1, 3, 4, 5 };
    int b[] = { 2, 3, 10 };
 
    int m = sizeof(a)/sizeof(a[0]);
    int n = sizeof(b)/sizeof(b[0]);
 
    solve(a, b, m, n);
 
for(int i=0;i<m;i++) printf("%d ",a[i]);
printf("\n");
for(int i=0;i<n;i++) printf("%d ",b[i]);
 
    return 0;
}

Output

[1, 2, 3, 4, 7]
[8, 9, 10]

People are also reading:

Leave a Reply

Your email address will not be published. Required fields are marked *