Arrays: Merge Sorted Arrays

Day 1/300

Sep 06, 2022

Welcome Reader!

Welcome to Day 1 with The Daily Code. We hope that you are doing great. This article will discuss the problem based on “Arrays,” i.e., “Merge Sorted Arrays.” Before you move any further, it is advised that you give this problem a fair try. Let us begin with the problem statement first.

Problem Statement:

You are given two integer arrays, nums1, and nums2, sorted in non-decreasing order, and two integers, m, and n, representing the number of elements in nums1 and nums2, respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The function should not return the final sorted array but instead be stored inside the arraynums1. To accommodate this, nums1 has a length of m+n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

For example:

Sample Input -> nums1 = [1,2,3,0,0,0], m=3 , nums2 = [2,5,6], n=3

Sample Output -> [1,2,2,3,5,6]

Approach:

Create two pointer variables, i & j, to traverse all elements from both arrays.
Create a k pointer to store values in nums1 from the end.
Traverse both arrays from the end towards the starting of the array.
Compare elements from both arrays; whichever element is greater is kept on the k pointer position.
At last, fill nums1 with the left elements in either array.

Let's take an example -:

Let’s take an example where
1. nums1[] = {1,2,3,0,0,0}
2. nums2[]= {2,5,6}
Create three-pointers, place i on the end of the nums1 (excluding 0), place j on the end of nums2 and place k at the literal end of the nums1 array.

Compare value of i & j pointer,

If i is greater than j, place the value of i at k and decrement i by 1.
If j is greater than i, place the value of j at k and decrement j by 1.
Also, Decrement k in both cases.

In this case, j is greater than i. Therefore, we will place the value of j at the kth position and decrement both by 1.

In this case, i is greater than j. Therefore, we will place the value of i at the kth position and decrement both by 1.

In this case, i is equal to j. Therefore, we will place the value of i at the kth position and decrement both by 1.

Now, j is at the null position. Therefore we will place all remaining values in the nums1 array.

Code Solution

Let’s try to code this!

1.) Create three variables, I, j & k. Initialize i with a length of nums1 array, j with a length of nums2 array, and k with adding lengths of both the arrays.

2.) Traverse both pointers till the 0th element of the array.

3.) Compare elements from both arrays; whichever element is greater, we place that particular element by the greater element and decrement value of the particular pointer and k by 1.