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
nums1[] = {1,2,3,0,0,0}
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.
4.) Place the remaining elements from the array on the kth pointer and decrement the value of both pointers.
Complexity Analysis:
Let us analyze the problem for its time and space complexity.
Time Complexity: O(N)
Where N = length of the input string. As we traverse every element of both arrays for one time, the time complexity is O(N).
Space Complexity: O(1)
As we have created No extra space, the space complexity is O(1).
Complete Code:
We hope that this article was helpful. Join our community on Discord.
Doubts, suggestions, and feedback are always welcomed. Keep practicing more and more problems daily. Meditate enough on each step of each problem.
“Don’t let the fear of losing be greater than the excitement of winning.” -Robert Kiyosaki.
All the best for an exciting future! Happy Coding!
Contributed by: Parth Mathur
Regards,
The Daily Code Team.
Thats a great approach @Ravi.
Have fun :)
Typically adding elements to the front may lead to shuffling and extra copies. Great question!