Merge Two Sorted Arrays Editorial

Practice Problem Link: Merge Two Sorted Arrays | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two sorted arrays A and B, find the merged sorted array C by merging A and B.

Naive Approach

Take a third array C of size equal to the sum size of given arrays, A and B. Insert all the elements of A and B in the array C, and sort array C.

Analysis

• Time Complexity: O((m + n) * log (m + n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<int> mergeSortedArrays(vector<int> A, vector<int> B) {
   vector<int> C(A.size() + B.size());
   for (int i = 0; i < A.size(); i++) {
       C[i] = A[i];
   }
   for (int i = 0; i < B.size(); i++) {
       C[A.size() + i] = B[i];
   }
   sort(C.begin(), C.end());
   return C;
}

Java

class Solution {
   int[] mergeSortedArrays(int[] A, int[] B) {
       int C[] = new int[A.length + B.length];
       for (int i = 0; i < A.length; i++) {
           C[i] = A[i];
       }
       for (int i = 0; i < B.length; i++) {
           C[A.length + i] = B[i];
       }
       Arrays.sort(C);
       return C;
   }
}

Optimal Approach

We will solve this problem in linear time by merging the arrays in a way, similar to the “merge” function of merge sort. We will simultaneously traverse array A and B, pick the smaller of current elements and push it in array C, and move that pointer ahead by one. Finally, if there are remaining elements in either of the arrays, push them into array C.

Analysis

• Time Complexity: O(m + n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<int> mergeSortedArrays(vector<int> A, vector<int> B) {
   vector<int> C(A.size() + B.size());
   int i = 0, j = 0, k = 0;
   while (i < A.size() && j < B.size()) {
       if(A[i] < B[j]) {
           C[k] = A[i];
           k++;
           i++;
       }
       else {
           C[k] = B[j];
           k++;
           j++;
       }
   }
   while (i < A.size()) {
       C[k] = A[i];
       k++;
       i++;
   }
   while (j < B.size()) {
       C[k] = B[j];
       k++;
       j++;
   }
   return C;
}

Java

class Solution {
   int[] mergeSortedArrays(int[] A, int[] B) {
       int C[] = new int[A.length + B.length];
       int i = 0, j = 0, k = 0;
       while (i < A.length && j < B.length) {
           if(A[i] < B[j]) {
               C[k] = A[i];
               k++;
               i++;
           } else {
               C[k] = B[j];
               k++;
               j++;
           }
       }
       while (i < A.length) {
           C[k] = A[i];
           k++;
           i++;
       }
       while(j < B.length) {
           C[k] = B[j];
           k++;
           j++;
       }
       return C;
   }
}