Hello readers, we come with another very interesting problem. I would suggest you give it a shot. The problem link is above.

**Important Links : Problem Link, Solution Video**

Merge Two Sorted Arrays

Support the American dream and make coding available to Everyone!!

~Snoop Dogg

Merge Two Sorted Arrays

Hello readers, we come with another very interesting problem. I would suggest you give it a shot. The problem link is above.

**Important Links : Problem Link, Solution Video**

Problem Discussion :

- You are given two sorted arrays(a,b) of integers.
- You have to merge them and form one sorted array.
- You have to do it in linear time complexity.

You might come up with a naive approach of just appending the second array after the first array and sort the new array. If array 1 has length n1 and array 2 has length n2 then for appending you will take n2 operations and for sorting, it will take at least **nlogn**. So this is not a very good approach.

Can you see anything that we can take advantage of? Yes. The arrays are already sorted. We can use that to our advantage and it will help optimize our approach.

Approach :

A very basic overview of the approach would be that we will keep two pointers which will point to the smallest number in both arrays i.e. the first element. And we will choose the one which is comparatively smaller and increment that pointer.

**So let's take an example:**

arr1[] = 2 5 12 18 20

arr2[] = 7 9 11 15 25 28 30 35

Now, arr1.length = 5 and arr2.length = 8. So the merged array will be of size 5+8 = 13.

Let's have three-pointers,

i: point to arr1's element.

j: point to arr2's element.

k: point to the currently merged array position.

Clearly, we have i pointing to 2 and j pointing to 7. Now 2<7, so final[k] = 2, and since we considered 2 we will increment i and also k. k will always be incremented.

Now we compare 5 and 7. Again 5 is smaller so final[k] = final[1] = 5. And i and k will be incremented.

This time between 12 and 7. 7 is smaller. So final[k] = final[2] = 7. And since an element of arr2 was chosen we will increment j. k will always be incremented as we mentioned before.

This time between 12 and 9. 9 is smaller. So final[k] = final[3] = 9. And since an element of arr2 was chosen we will increment j. k will always be incremented as always.

You can clearly see we are slowly moving across the arrays and building a new merged array which is also in sorted order by making greedy decisions at every point of choosing the smaller value.

Try to do the same for the rest of the elements. If you stuck at any point watch the video.

If you have understood so far, take a try at coding this. If you are stuck you can take a look at the code below.

import java.io.*;
import java.util.*;
public class Main {
public static int[] mergeTwoSortedArrays(int[] a, int[] b) {
// write your code here
int alen = a.length;
int blen = b.length;
int[] res = new int[alen + blen];
int i = 0;
int j = 0;
int k = 0;
// when there are elements in both the array
while (i < alen && j < blen) {
if (a[i] < b[j]) {
res[k] = a[i];
i++;
} else {
res[k] = b[j];
j++;
}
k++;
}
while (i < alen) {
res[k] = a[i];
i++;
k++;
}
while (j < blen) {
res[k] = b[j];
j++;
k++;
}
return res;
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scn.nextInt();
}
int m = scn.nextInt();
int[] b = new int[m];
for (int i = 0; i < m; i++) {
b[i] = scn.nextInt();
}
int[] mergedArray = mergeTwoSortedArrays(a, b);
print(mergedArray);
}
}

java; true";

If you look at it carefully, we have 3 while loops. When the first while loop ends it means either a[] or b[] is fully iterated. But there are still some elements in the other one. So we will run two single loops where we will simply insert the remaining elements.

Analysis

Time Complexity :

** O(n)**

Time complexity will be O(n) where n = a.length + b.length because if we look at i it will move from 0 to a.length only once. And j will move from 0 to b.length only once. So total iterations is a.length + b.length. If you are still not impressed, look at k. k will loop throughout the result array only once. Hence from here also we can say that the time complexity will be a.length + b.length i.e linear O(n).

SPACE COMPLEXITY :

**O(n)**

Here we are actually using a temporary array of size a.length + b.length to store the merged array. So our space complexity is **O(n)** i.e Linear.

Hopefully, you have understood the Algorithm. You will need this algorithm in merge sort in the future. If you haven't understood properly I suggest you watch the full video and dry run the code by hand. That way you will understand the intuition behind this beautiful algorithm. All the best and keep learning!!