Hi striver, I have a doubt on optimal solutions that besides having higher time complexities than brute force how can they be optimal? Also memory is cheaper these days and time is considered most valuable. Please tell me how to respond if the interviewer asks me this question?
The standard Shell sort performs insertion sort at different interval values. However, in the second optimal solution to this problem, for each interval, we just swap the adjacent values (separated by interval), which isn't exactly the same as doing insertion sort. The optimal solution, however, still works well. I understand that intuitively this works because the two individual arrays are already sorted. However, I couldn't really find a proof that this approach always yields the correct solution. Any pointers are much appreciated, Thanks.
@@FooBar-lb5wf The method used in this video is comb sort not shell sort. In comb sort we perform bubble sort with gaps. In shell sort we perform insertion sort with gaps.
@@iamnoob7593 dont skip it learn what was the though process behind that algorithm .. it would increase your problem solving and logic building approach
bro i am trying to sort an array using Shell sort can you tell what problem does this code have class Solution { public: vector sortArray(vector& nums) { int n=nums.size(); int gap=(n/2)+(n%2); while(gap>0){ int left=0; int right=0+gap; while(rightnums[right])swap(nums[left],nums[right]); left++;right++; }
I don't know about c++,but in java once an array is created its size can't be altered since it is static in size. so its leading to creation of new array which is not the case we required for this question.
if problem is given in such way that nums1 length is upto n+m but it contains m elements then this solution will work: int p1 = m-1; int p2 = n-1; int p = n+m-1; while(p1>=0 && p2>=0){ if(nums1[p1]>nums2[p2]){ nums1[p] = nums1[p1]; p1--; } else{ nums1[p] = nums2[p2]; p2--; } p--; } while(p2>=0){ nums1[p] = nums2[p2]; p2--; p--; } here it comes with time complexity of O(n+m) since no sorting is required in this approach.
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
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 found 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
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.
Done on 7 Jan 2025 at 19:04 Place : Home Leaving for college(train in 2 hours) The next time i come to my home town , I hope i would have cracked an internship
00:06 Merge two sorted arrays without extra space 04:09 The problem with the approach is using an extra array. 08:21 Implementing a Brute Force solution to sort two arrays in the correct order 12:31 Sorting arrays using a two-pointer approach 16:52 Comparison algorithm for moving pointers based on a decreasing Gap 20:58 Implement the Gap method to arrange elements in ascending order. 24:56 Implement swap function to ensure left is always at array 1 29:13 Understanding the code for adjusting 'left' and 'right' in an array
Hi Raj, How come the 1st optimal solution be optimal solution at all, when sorting method itself takes O(log n) of extra space? And, because of this the TC of 1st optimal solution is worse than Brute Force solution but the SC is better.
A small correction in the video - when you consider gap=3, while comparing 7 with 6, you're missing to swap the elements. Can you please check that once? Thanks for the video!
Maybe i am wrong but -> The swap method assumed that every comparison involved elements from two different arrays (a and b). This caused problems when both indices were from the same array, leading to incorrect swaps and an unsorted result. So to overcome this Create another method which will take the single array in which the swapping has to be done. if both indices are in arr1 then pass arr1 along with indices and if both indices are in arr2 pass arr2 along with indices.
@takeUforward shouldn't the time complexity of the brute force solution be O(m) as for traversal of both the arrays simultaneously, it would be O(n) and O(m-n) for traversal of the remaining larger array, so overall TC would be O(n)+O(m-n)=O(m). Please clarify, it would be of great help @striver
no look at the worst case:- for eg:- arr1=[1,2,3] arr2=[4,5,6,7] in this case you will first traverse through entire arr1 then afterwards you traverse through entire arr2 so TC=O(m+n)
i guess there are more optimal appraoches like this one void merges_sorted_arrays_optimal2(vector &a, vector &b){ for (int i = 0; i < b.size(); i++) { a.push_back(b[i]); } b.clear(); sort(a.begin(),a.end()); }
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 merge_fillFromBehind(vector& nums1, int m, vector& nums2, int n) { if(n==0) return;
I think more easier approach would be to take three pointers as: i points to the last valid element in nums1 (at index m-1). j points to the last element in nums2 (at index n-1). k points to the last position in nums1 (at index m + n - 1). Compare the elements at i and j and place the larger one at index k. Then move the corresponding pointer (i or j) and k backward. After finishing the loop, if any elements are left in nums2, copy them into nums1. This happens because nums1 might already be sorted and have smaller elements at the beginning. while (i >= 0 && j >= 0) { if (nums1[i] > nums2[j]) { nums1[k] = nums1[i]; i--; } else { nums1[k] = nums2[j]; j--; } k--; } // If there are still elements left in nums2, copy them while (j >= 0) { nums1[k] = nums2[j]; j--; k--; } Happy Coding
there is a more optimal and easier soln for this problem .. though process -- 1--> since nums1 is of m+n size .. there are m elements and n zeroes present in the array .. we can use these zeroes as an extra space 2-->we need to keep in mind to not to distrupt m elements of nums1 as replacing any element with nums2 elements would lead to data loss 3--> as the arrays are sorted the best method which should come to mind will be 2 pointers.. 4-->take a random exmaple.. if we start from the first elements of both array then it would lead to loss of m elements of nums[1].. even if we use that extra space which are 0 elements also it would still make things very complicated 5--> now if things seem complicated from front .. change point of view to backward direction and choose last element and try to put it in its correct position .. as we know last elements willl be largest in both array .. if we put last element in its corrects position which is nums[m+n-1](we keep a third pointer here) there would be two possibility if last element belongs to nums1 or nums2 .. if it belongs to nums1 .. then its a win as we can now distrupt its position and put other element in its earlier position.. if last element belong to num2 still it occupies that extra space and would not distrupt position of nums1 element which is again a win .. we an now apply two pointer approach in backward direction starting from the largest element from both arrays (its just like the two pointer u applied in forward direction)..just here we use an extra pointer for keeping elements starting from last and move in bacckward direction .. so its kinda 3 pointer solution try out an example to get a good understanding i wont write the code as now u can make the code .. time complexity worst case--0(m+n).. like if it helps
you can't apply optimal 1 to leetcode problem because they give nums1 of m + n size , so when you sort zeroes would come first and after merging actual nums1 data will be erased.
The sorting could take extra space depending on the programming language being used. I use Python and Python uses Timsort which uses extra space for sorting.
i have a question regarding first optimal solution its total space complexity is O(1) but why it is O(1) in our solution we performed sorting of both the arrays but in context of java when use Arrays.sort() it internally uses tim sort which is derives from insertion sort and merge sort which has a time complexity of O(n) so why we are including this space in our solution.
If shell sort has worst case complexity O(n^2) then how does the optimal2 solution complexity is nlogn it is also just basically sorting the imaginary combined array right?
Answer: Time complexity of shell sort depends on how you choose the gaps apparently so it"s not a fixed algorithm it can be of O(nlogn) too if you choose gaps this way I think there is a rule as to how youre supposed to choose gaps but that is not required I think as shell sort is not that important it seems
Thinks so found a new optimal approach: Time complexity: O(m+n) Code: class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1[m:] = [] i = 0 j = 0 while i < m and j < n: if nums1[i] > nums2[j]: nums1.insert(i, nums2[j]) j += 1 m += 1 else: i += 1 while j < n: nums1.append(nums2[j]) j += 1
Why would we do so much if we can just put everything on the second array in the first one and apply the sort function ? The time complexity will be the same : O(n+m) * log(n+m) The better solution with O(n+m) time complexity is void merge(vector& nums1, int m, vector& nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1;
while (j >= 0) { if (i >= 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } }
But the thing is If we go for the optimal 2 approach Its more like giving us NLogN time complexity which is same as any other sorting mechanisms Which is we are using the sorted arrays as advantage but couldn't replicate that in complexity wise just for saving spaces - we did over engineering i suppose on this aspect
If using the gap technique is optimal, then why don't we use it in the mergeSort algorithm where 2 sorted subarrays need to be merged. If we do that, we will be able to bring down the space complexity of mergeSort() from O(N) to O(1).
class Solution { public: void merge(vector& nums1, int m, vector& nums2, int n) { int i = m - 1; // Pointer for nums1 int j = n - 1; // Pointer for nums2 int k = m + n - 1; // Pointer for the end of nums1 // Merge in reverse order while(i>=0 && j>=0) { if(nums1[i] > nums2[j]){ nums1[k--] = nums1[i--]; } else{ nums1[k--] = nums2[j--]; } } // remaining elements in nums2 while ( j >=0){ nums1[k--] = nums2[j--]; } } };
Please watch our new video on the same topic: ua-cam.com/video/n7uwj04E0I4/v-deo.html
😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊
this is the same video
Do give us a like, it won't cost you anything :), but it will motivate me to make more and more.
Hi striver, I have a doubt on optimal solutions that besides having higher time complexities than brute force how can they be optimal? Also memory is cheaper these days and time is considered most valuable. Please tell me how to respond if the interviewer asks me this question?
Thank you striver bhaiya for providing quality content in UA-cam
hi striver in the 2nd optimal approach i.e. when left and right are in same array does our swap function will work properly ???
The standard Shell sort performs insertion sort at different interval values. However, in the second optimal solution to this problem, for each interval, we just swap the adjacent values (separated by interval), which isn't exactly the same as doing insertion sort. The optimal solution, however, still works well. I understand that intuitively this works because the two individual arrays are already sorted. However, I couldn't really find a proof that this approach always yields the correct solution. Any pointers are much appreciated, Thanks.
@@FooBar-lb5wf The method used in this video is comb sort not shell sort. In comb sort we perform bubble sort with gaps. In shell sort we perform insertion sort with gaps.
The first optimal is very easy to understand compare to second optimal aproach. Both way are totally understable. Thankyou
thanks i am skipping opt 2
@@iamnoob7593 dont skip it learn what was the though process behind that algorithm .. it would increase your problem solving and logic building approach
It's really good to see how much teaching skills you have improved. Thanks!
So far the clearest explanation I could find for the gap method. Thanks a lot!!
What an Explanation Striver Bro! The Gap method is really amazing.
bro i am trying to sort an array using Shell sort
can you tell what problem does this code have
class Solution {
public:
vector sortArray(vector& nums) {
int n=nums.size();
int gap=(n/2)+(n%2);
while(gap>0){
int left=0;
int right=0+gap;
while(rightnums[right])swap(nums[left],nums[right]);
left++;right++;
}
if(gap==1)break;
gap=(gap/2)+(gap%2);
}
return nums;
}
};
Thank you Striver for providing detailed videos on DSA. Really appreciate your work!
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n) {
for(int i=0; i
i have the same approch
I don't know about c++,but in java once an array is created its size can't be altered since it is static in size. so its leading to creation of new array which is not the case we required for this question.
if problem is given in such way that nums1 length is upto n+m but it contains m elements then this solution will work:
int p1 = m-1;
int p2 = n-1;
int p = n+m-1;
while(p1>=0 && p2>=0){
if(nums1[p1]>nums2[p2]){
nums1[p] = nums1[p1];
p1--;
}
else{
nums1[p] = nums2[p2];
p2--;
}
p--;
}
while(p2>=0){
nums1[p] = nums2[p2];
p2--;
p--;
}
here it comes with time complexity of O(n+m) since no sorting is required in this approach.
@@yashwanthyerra2820 this is also a good approach.
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
In gap method when the gap is 3 why do you don't swap 7 and 6.(7>6) 20:03
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 found 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
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
your quality of teaching,frameworks and style of teaching all are superb sir💯
//Two line solution for(int i=0;i
Thank you Striver for making these in-depth very well explained videos
Optimal solution 2 was really good and your teaching skills made it easier and interesting
bhai aap genius ho!!.. real inspiration and best teacher to me...
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.
surely we will just keep learning
wassup with you rn? how far are you in his course and what's your leetcode profile or codechef stars?
update?
Done on 7 Jan 2025 at 19:04
Place : Home
Leaving for college(train in 2 hours)
The next time i come to my home town , I hope i would have cracked an internship
Keep us updated brother
Understood. Thank you Striver
Content is Absoluetly amazing
Respect++ for striver bhaiya.....
HIi Bro
If we use built in sort()
then How can we say it solved in constant space??
Because sort() will also need O(N) Space internally right?
Isn't the sort function based on a variation of quick sort? Which might take O(logN) stack space to execute?
sorting will be done in the array itself why it needs extra space?
because sort fnc uses quick sort .. in quick sort we dont use any extra space
Understood! Super amazing explanation as always, thank you very very very much for your effort!!
Best explanation on UA-cam ❤🔥🔥🔥
you are a god in programming, man.
Appreciate the efforts you are putting in. Content is Absoluetly amazing.
Lets take a moment to appreciate striver and the person who created this shell sort or gap method
00:06 Merge two sorted arrays without extra space
04:09 The problem with the approach is using an extra array.
08:21 Implementing a Brute Force solution to sort two arrays in the correct order
12:31 Sorting arrays using a two-pointer approach
16:52 Comparison algorithm for moving pointers based on a decreasing Gap
20:58 Implement the Gap method to arrange elements in ascending order.
24:56 Implement swap function to ensure left is always at array 1
29:13 Understanding the code for adjusting 'left' and 'right' in an array
Woho That is so so Cool . THe GAp method is LIT.
Very nice explanation🔥
my simple approach is
1. merge two arrays
2. sort once the final array - to get answer
Merging will allow you to utilize extra space.
@@yashpandey7 no it wont
awesome, short of words to thank you really. making a v big impact n my coding life.
3rd Approach is amazing
awesome explanation ever🙂
Appreciate the efforts you are putting in 😇
left,right=len(a)-1,0
while a[left]>b[right]:
a[left],b[right]=b[right],a[left]
left=left-1
right=right+1
a.sort()
b.sort()
Thanks a lot:
can we include this O(m+n) solution:
just start from the back and keep adding the greater one from both sides:
it will fill sorted.
amazing explanation thanks a lot. 😊
Amazing explanation
Thank you for provide good quality of content
Why is it not needed to swap 7 and 6 at 19:59 ? 7 is greater than 6, so we must swap 7 and 6. Or am I getting anything wrong ?
he has motioned below that he has done a mistake
can we consider this as optimal approach ??
public static void merge(int []a,int []b,int n){
int left = 0;
while(left
crystalll clear bhaiya!!!!
small issue at 19:54, should have swapped 7 and 6, but that's I guess okay 😅
Thank you for great content striver bhaiya ❤
Understood with ease 🤩..
Nice explanation.
in first optimal approach , we are modifying both the array , but we have to merge both the array , pls explain
Hi Raj,
How come the 1st optimal solution be optimal solution at all, when sorting method itself takes O(log n) of extra space? And, because of this the TC of 1st optimal solution is worse than Brute Force solution but the SC is better.
how simple is the second approach, thanks a lot, are you really sure interviewer will accept that?😐
14:27, can anyone explain me, why we are not merging the arrays
A small correction in the video - when you consider gap=3, while comparing 7 with 6, you're missing to swap the elements. Can you please check that once?
Thanks for the video!
Can someone tell me the which of the optimal approach has better complexity in case of time or Both of'em are somewhat equal?
Maybe i am wrong but -> The swap method assumed that every comparison involved elements from two different arrays (a and b). This caused problems when both indices were from the same array, leading to incorrect swaps and an unsorted result.
So to overcome this Create another method which will take the single array in which the swapping has to be done. if both indices are in arr1 then pass arr1 along with indices and if both indices are in arr2 pass arr2 along with indices.
why you did not swap at 19:37?
Yesss.... why he didn't swap that
@takeUforward shouldn't the time complexity of the brute force solution be O(m) as for traversal of both the arrays simultaneously, it would be O(n) and O(m-n) for traversal of the remaining larger array, so overall TC would be O(n)+O(m-n)=O(m). Please clarify, it would be of great help @striver
no look at the worst case:-
for eg:- arr1=[1,2,3] arr2=[4,5,6,7] in this case you will first traverse through entire arr1 then afterwards you traverse through entire arr2 so TC=O(m+n)
thnx for the amazing video ❤❤❤❤👌👌👌👌
Thanks a lot striver❤
Understood, thank you.
i guess there are more optimal appraoches like this one
void merges_sorted_arrays_optimal2(vector &a, vector &b){
for (int i = 0; i < b.size(); i++)
{
a.push_back(b[i]);
}
b.clear();
sort(a.begin(),a.end());
}
Understood✅🔥🔥
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 merge_fillFromBehind(vector& nums1, int m, vector& nums2, int n) {
if(n==0) return;
int i=0, j=0, k=(n+m-1);
while(i
I think more easier approach would be to take three pointers as:
i points to the last valid element in nums1 (at index m-1).
j points to the last element in nums2 (at index n-1).
k points to the last position in nums1 (at index m + n - 1).
Compare the elements at i and j and place the larger one at index k. Then move the corresponding pointer (i or j) and k backward.
After finishing the loop, if any elements are left in nums2, copy them into nums1. This happens because nums1 might already be sorted and have smaller elements at the beginning.
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
// If there are still elements left in nums2, copy them
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
Happy Coding
@@parthkamboj3505 I have also done the problem with this approach
Thanks gurujii
understood :) Thanks a lot.
Whats the intutition behind the gap method?
nice explanation,
Thank you so much
Thank u Striver Understood
Understood!🔥
Understood 🙏🏻
there is a more optimal and easier soln for this problem ..
though process -- 1--> since nums1 is of m+n size .. there are m elements and n zeroes present in the array .. we can use these zeroes as an extra space
2-->we need to keep in mind to not to distrupt m elements of nums1 as replacing any element with nums2 elements would lead to data loss
3--> as the arrays are sorted the best method which should come to mind will be 2 pointers..
4-->take a random exmaple.. if we start from the first elements of both array then it would lead to loss of m elements of nums[1].. even if we use that extra space which are 0 elements also it would still make things very complicated
5--> now if things seem complicated from front .. change point of view to backward direction and choose last element and try to put it in its correct position .. as we know last elements willl be largest in both array .. if we put last element in its corrects position which is nums[m+n-1](we keep a third pointer here) there would be two possibility if last element belongs to nums1 or nums2 .. if it belongs to nums1 .. then its a win as we can now distrupt its position and put other element in its earlier position.. if last element belong to num2 still it occupies that extra space and would not distrupt position of nums1 element which is again a win ..
we an now apply two pointer approach in backward direction starting from the largest element from both arrays (its just like the two pointer u applied in forward direction)..just here we use an extra pointer for keeping elements starting from last and move in bacckward direction .. so its kinda 3 pointer solution
try out an example to get a good understanding
i wont write the code as now u can make the code ..
time complexity worst case--0(m+n)..
like if it helps
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n) {
int left = m-1;
int right = n-1;
int high = m+n-1;
while(left>=0 && right>=0){
if(nums1[left] > nums2[right]){
nums1[high] = nums1[left];
left--;
high--;
}
else{
nums1[high] = nums2[right];
right--;
high--;
}
}
while(right >= 0){
nums1[high] = nums2[right];
right--;
high--;
}
}
}; this is the code...u should ignore it and focus on thought process then u can write code easily.. its just for help if anyone wanted
Excellent Explainaton
Can you tell me plz when this course complete
The entire syllabus is there on the website, you can do it at your own pace, don't wait for me
you can't apply optimal 1 to leetcode problem because they give nums1 of m + n size , so when you sort zeroes would come first
and after merging actual nums1 data will be erased.
what approach is to be used there?
The sorting could take extra space depending on the programming language being used. I use Python and Python uses Timsort which uses extra space for sorting.
in the 1st optimized solution, we didnt merge the arrays did we?
i have a question regarding first optimal solution its total space complexity is O(1) but why it is O(1) in our solution we performed sorting of both the arrays but in context of java when use Arrays.sort() it internally uses tim sort which is derives from insertion sort and merge sort which has a time complexity of O(n) so why we are including this space in our solution.
If shell sort has worst case complexity O(n^2) then how does the optimal2 solution complexity is nlogn it is also just basically sorting the imaginary combined array right?
Answer: Time complexity of shell sort depends on how you choose the gaps apparently so it"s not a fixed algorithm it can be of O(nlogn) too if you choose gaps this way
I think there is a rule as to how youre supposed to choose gaps but that is not required I think as shell sort is not that important it seems
GOD LEVEL EXPLAIN!!!!!!...... please came up with string playlist.!!!!!!!
Understood 🎉
In brute force, if a[left]
thank you for expaination
Greak work brother!
Thinks so found a new optimal approach:
Time complexity: O(m+n)
Code:
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
nums1[m:] = []
i = 0
j = 0
while i < m and j < n:
if nums1[i] > nums2[j]:
nums1.insert(i, nums2[j])
j += 1
m += 1
else:
i += 1
while j < n:
nums1.append(nums2[j])
j += 1
not O(m+n) because when you insert in array it is O(n) complexity which will make your solution O(mn + n^2)
class Solution {
public:
void swapIfGreater(vector&nums1,vector&nums2, int ind1,int ind2)
{
if(nums1[ind1] > nums2[ind2])
swap(nums1[ind1],nums2[ind2]);
}
void merge(vector& nums1, int m, vector& 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)
{
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???
Why would we do so much if we can just put everything on the second array in the first one and apply the sort function ?
The time complexity will be the same : O(n+m) * log(n+m)
The better solution with O(n+m) time complexity is
void merge(vector& nums1, int m, vector& nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
But the thing is
If we go for the optimal 2 approach
Its more like giving us NLogN time complexity which is same as any other sorting mechanisms
Which is we are using the sorted arrays as advantage but couldn't replicate that in complexity wise
just for saving spaces - we did over engineering i suppose on this aspect
do we really nead to sort for the optimal 1? I think we can just reverse the 2nd half of 1 array and merge it with the first half
What is the intuition for gap method?
understood 👍👍
Namaste bhaiya , last bit of code is not working properly.
could you please help me to do that .
If using the gap technique is optimal, then why don't we use it in the mergeSort algorithm where 2 sorted subarrays need to be merged. If we do that, we will be able to bring down the space complexity of mergeSort() from O(N) to O(1).
LeetCode solution: class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int r=n-1;
for(int i=m;i
Thank you
pls do complete this series upto ultra advance level.
Sir, I am not able to understand timecomplexcity can you make video on timcomplexcity
is it okay that first i merge both array and applied insertion sort
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n) {
int i = m - 1; // Pointer for nums1
int j = n - 1; // Pointer for nums2
int k = m + n - 1; // Pointer for the end of nums1
// Merge in reverse order
while(i>=0 && j>=0)
{
if(nums1[i] > nums2[j]){
nums1[k--] = nums1[i--];
}
else{
nums1[k--] = nums2[j--];
}
}
// remaining elements in nums2
while ( j >=0){
nums1[k--] = nums2[j--];
}
}
};
Striver Sir You should have solved leetcode problem that's difficulty level is greater than this !