This content originally appeared on DEV Community and was authored by sachin26
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.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation : The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1
Solution 1
sort the num1 array by swapping num2 array elements, while swapping keep sorting num2, then add all num2 elements to num1 array.
lets understand this approach step by step.
step-1 Initialise two varible pointer1 = 0 & pointer2 = 0.
step-2 if n == 0 , then return.
step-3 run a loop from i=1 to m,then
if
num1[pointer1] > num2[pointer2],then1. swap(num1[pointer1],num2[pointer2]).
2. sort thenum2array.
3. incrementpointer1++else increment
pointer1++
step-4 again run a loop from i=1 to n,then
1.
num1[pointer1] = num2[pointer2]
2. increment thepointer2++.
step-5 end.
Java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int pointer1=0, pointer2=0;
if(n==0) return;
for(int i=0; i<m;i++){
if(nums1[pointer1] > nums2[pointer2]){
int temp = nums1[pointer1];
nums1[pointer1] = nums2[pointer2];
nums2[pointer2] = temp;
Arrays.sort(nums2);
pointer1++;
}else
pointer1++;
}
for(int i=1;i<=n;i++){
nums1[pointer1] = nums2[pointer2];
pointer1++;
pointer2++;
}
}
}
Solution 2
by reverse sorting, this problem can be solved in linear time complexity.
step-1 initialise variables i=m-1, j=n-1, arr1Len=nums1.length-1.
step-2 run a loop if i>=0 and j>=0, then
if nums1[i] > nums2[j], then
update the value from the last index.
nums1[arr1Len] = nums[i];
i--
arr1Len--
else
nums1[arr1Len] = nums[j]
j--
arr1Len--
srep-3 run a loop if j >=0, then
nums1[arr1Len] = nums[j]
arr1Len--
j--
step-4 end.
Java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i=m-1,j=n-1,arr1Len=nums1.length-1;
while(i>=0 && j>=0){
if(nums1[i] > nums2[j]){
nums1[arr1Len] = nums1[i];
i--;
arr1Len--;
}else{
nums1[arr1Len] = nums2[j];
j--;
arr1Len--;
}
}
while(j>=0){
nums1[arr1Len] = nums2[j];
j--;
arr1Len--;
}
}
}
Time Complexity : O(m+n)
Space Complexity : O(1)
Thank you for reading this article. if you find something wrong, let me know in the comment section.
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2021-12-30T12:09:01+00:00) Striver’s SDE Sheet Journey – #9 Merge two sorted Arrays. Retrieved from https://www.scien.cx/2021/12/30/strivers-sde-sheet-journey-9-merge-two-sorted-arrays/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.