Merge Sorted Arrays Leetcode Solution

In the problem “Merge Sorted Arrays”, we are given two arrays sorted in non-descending order. The first array is not fully filled and has enough space to accommodate all elements of the second array as well. We have to merge the two arrays, such that the first array contains elements of both the arrays and is sorted in non-descending order.

Example

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}

1 2 2 3 6 7

{1 , 1 , 1 ,  - , -}
{2 , 4}

1 1 1 2 4

Approach(Sorting)

We can transfer all the elements of the second array to the first one. We can then sort the first array to get the required result.

Algorithm

1. For i = 0 to i = N, assign
   1. a[i + m] = b[i], a =first array, b = second array
2. Sort the first array
3. Print the required result

Implementation of Merge Sorted Arrays Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

Java Program

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}

1 2 2 3 6 7

Complexity Analysis of Merge Sorted Arrays Leetcode Solution

Time Complexity

O(KlogK), where K = N + M. N = size of the first array, M = size of the second array. As we sort the first array after it has stored all N + M elements.

Space Complexity

O(1) as constant memory is used for variables.

Approach(Two Pointers)

We can use two-pointer technique to merge the two sorted arrays, into a new array. But, the creation of this new array will cost extra space. We can try to avoid this extra array especially when the first array has enough space to hold all the elements of both the arrays. We can use two pointers and start merging the elements in the back of the first array.

This will cut the problem of “extra array memory” as we keep fixing the elements in the void space.

Algorithm

1. Initialize two variables i and j storing indices of the last element of the first and second array respectively.
   • i = M – 1 , j = N – 1
2. Initialize a variable idx, storing the last index of the first array, that is:
   • idx = N + M – 1
3. Now, do the following until either of i or j becomes zero
   • If a[i] >= b[j]
     • Assign a[idx] = a[i], decrement i
   • Else
     • Assign a[idx] = b[j], decrement j
   • Decrement idx
4. Either of i or j is not zero, which means some elements are yet to be merged. As they would already be in a sorted manner, we simply append them to the first array in the front.
5. While i does not become zero,
   1. Assign a[idx] = a[i]
   2. Decrement idx and i
6. While j does not become zero,
   1. Assign a[idx] = b[j]
   2. Decrement idx and j
7. Now first array has all the elements in the required sorted order.

Implementation of Merge Sorted Arrays Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

Java Program

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}

1 2 2 3 6 7

Complexity Analysis of Merge Sorted Arrays Leetcode Solution

Time Complexity

O(N + M). N = size of the first array, M = size of the second array. As we traverse both the arrays once.

Space Complexity

O(1), as we store all the elements in the first array. So, the algorithm is in-place.