Merge Sorted Arrays Without Extra Space | 2 Optimal Solution

We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.

You can follow me across social media, all my handles are below:

0:00 Introduction of Course
00:40 Problem Statement
01:55 Brute force approach
04:43 Code
08:52 Complexity
09:53 Optimal - 1
12:50 Code
13:51 Complexity
15:37 Optimal - 2
15:52 Gap Method
24:40 Code
30:59 Complexity

[takeUforward]

Do give us a like, it won't cost you anything :), but it will motivate me to make more and more.

[Manishgupta]

The first optimal is very easy to understand compare to second optimal aproach. Both way are totally understable. Thankyou

[utkarshpatil]

It's really good to see how much teaching skills you have improved. Thanks!

[babbupatidar]

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i=0; i<n; i++){
nums1[m+i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};

[lazyemperor]

This is probably my 10th time here and I still always forget the intuition and trick to the besr optimzd approach to this problem, it's a tough problem

[the_avii_]

Another Approach:
TC: O(m*n)

Explanation:
1. Iterate over the first array (nums1) and compare every element with nums2 first element (nums2[0]). (Here we are trying to find which element in nums1 array is greater than num2 first element)

2. The point you find that element (in nums1 array), store it temporary and the replace the original value with the first element of nums2 (nums2[0]).

3. Now place the temp stored element at the right place in num2 array.

// rest steps you will understand when you dry run.

// program.java

public static void mergeBrute(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

for (int i = 0; i < m; i++) {

if (nums1[i] > nums2[0]) {
// Step 2
int temp = nums1[i];
nums1[i] = nums2[0];

boolean placeAtLast = true;

// Step 3
for (int k = 1; k < n; k++) {
if (temp > nums2[k]) {
nums2[k - 1] = nums2[k];
} else if (temp <= nums2[k]) {
nums2[k - 1] = temp;
placeAtLast = false;
break;
}
}

if (placeAtLast) {
nums2[n - 1] = temp;
}
}
}
}

[SydMohan]

So far the clearest explanation I could find for the gap method. Thanks a lot!!

[prajnasbhat]

Thank you Striver for providing detailed videos on DSA. Really appreciate your work!

[tonystark-oqmm]

What an Explanation Striver Bro! The Gap method is really amazing.

[tanmaychaudhary]

Thank you bhaiya for providing quality content....I am from tier 3 and I want to work with reputed companies like Google, Amazon, uber, Microsoft etc... within 2 years .... currently I am about to complete 3rd year BTech CSE.

[hemendiranbaskaran]

my simple approach is
1. merge two arrays
2. sort once the final array - to get answer

[mehulthuletiya]

00:40 Problem Statement
01:55 Brute force approach
04:43 Code
08:52 Complexity
09:53 Optimal - 1
12:50 Code
13:51 Complexity
15:37 Optimal - 2
15:52 Gap Method
24:40 Code
30:59 Complexity

[HKClasher]

//Two line solution for(int i=0;i<n;i++) nums1[i+m] = nums2[i];
sort(nums1.begin(), nums1.end());

[MayankSingh-diow]

As per the leetcode problem where zeroes are given in array-1

Another Approach: Fill from behind, when zeroes are exhausted, start filling from front.
then reverse arr[0 to m] and arr[0 to m+n]

void nums1, int m, vector<int>& nums2, int n) {
if(n==0) return;

int i=0, j=0, k=(n+m-1);
while(i<m && j<n)
{
if(nums1[i]<=nums2[j])
{
nums1[k]=nums1[i];
i++;
}
else
{
nums1[k]=nums2[j];
j++;
}
if(k>=m) {
k--;
if(k==m-1) k=0;
}
else k++;
}

while(i<m)
{
nums1[k]=nums1[i];
i++;
if(k>=m)
{
k--;
if(k==m-1) k=0;
}
else
{
k++;
}
}
while(j<n)
{
nums1[k]=nums2[j];
j++;
if(k>=m)
{
k--;
if(k==m-1) k=0;
}
else
{
k++;
}
}

reverse(nums1.begin(), nums1.begin()+m);
reverse(nums1.begin(), nums1.end());
return;
}

[MohammadAyanKhan-usvf]

your quality of teaching, frameworks and style of teaching all are superb sir💯

[priyotoshsahaThePowerOf]

class Solution {
public:
void swapIfGreater(vector<int>&nums1, vector<int>&nums2, int ind1, int ind2)
{
if(nums1[ind1] > nums2[ind2])
swap(nums1[ind1], nums2[ind2]);
}
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int len = (m+n);
int gap= (len/2) + (len%2);

while(gap>0)
{
int left=0 ;
int right=left+gap;

while(right < len) // not out of bound
{
// arr1, arr2
if(left<n && right>=n)
{
swapIfGreater(nums1, nums2, left, right-n);
}
// arr2, arr2
else if(left>=n)
{
swapIfGreater(nums2, nums2, left-n, right-n);
}

else
{
swapIfGreater(nums1, nums1, left, right);
}
left++, right++;
}
if(gap==1) // for reamining iterations
break;
gap=(gap/2)+(gap%2);

}

}
};

what is the problem in this code .. test cases not passing???

[crazybro]

Optimal solution 2 was really good and your teaching skills made it easier and interesting

[aryanikale]

Lets take a moment to appreciate striver and the person who created this shell sort or gap method

[ashishbm]

bhai aap genius ho!!.. real inspiration and best teacher to me...

[Shivi]

LeetCode solution: class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int r=n-1;
for(int i=m;i<m+n;i++){
nums1[i]=nums2[r];
r--;
}
Arrays.sort(nums1);

}
}