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.
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
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.
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.
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++; }
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
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
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()); }
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.
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--]; } } };
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.
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).
@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)
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
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--]; } } }
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.
Better Approach ngl: class Solution { public: 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--]; } } } };
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
LEETCODE NOT ACCEPTING OPTIMAL SOLUTION 1 left = n - 1 right = 0 # Swap the elements until arr1[left] is smaller than arr2[right]: while left >= 0 and right < m: if arr1[left] > arr2[right]: arr1[left], arr2[right] = arr2[right], arr1[left] left -= 1 right += 1 else: break # Sort arr1[] and arr2[] individually: arr1.sort() arr2.sort()
gap method solution not working in javascript because first time when gap =1 it should execute loop for adjacent elements for once. If gap =1, break the loop going forward . Let me know if I am wrong or any other best possible way.
O(n+m) code. Very Easy To Understand : class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i=m-1,j=n-1,k=m+n-1; while(i>=0&&j>=0) nums1[k--]=nums1[i]>=nums2[j]?nums1[i--]:nums2[j--]; while(i>=0) nums1[k--]=nums1[i--]; while(j>=0) nums1[k--]=nums2[j--]; } }
Can some One please explain what mistake does this code have i am sorting an array using Shell Sort 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++; }
Please watch our new video on the same topic: th-cam.com/video/n7uwj04E0I4/w-d-xo.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 TH-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
It's really good to see how much teaching skills you have improved. Thanks!
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
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.
Thank you Striver for providing detailed videos on DSA. Really appreciate your work!
So far the clearest explanation I could find for the gap method. Thanks a lot!!
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.
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?
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;
}
};
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
your quality of teaching,frameworks and style of teaching all are superb sir💯
can we consider this as optimal approach ??
public static void merge(int []a,int []b,int n){
int left = 0;
while(left
Lets take a moment to appreciate striver and the person who created this shell sort or gap method
Optimal solution 2 was really good and your teaching skills made it easier and interesting
//Two line solution for(int i=0;i
Thank you Striver for making these in-depth very well explained videos
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
Respect++ for striver bhaiya.....
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.
bhai aap genius ho!!.. real inspiration and best teacher to me...
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?
In gap method when the gap is 3 why do you don't swap 7 and 6.(7>6) 20:03
3rd Approach is amazing
Woho That is so so Cool . THe GAp method is LIT.
you are a god in programming, man.
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());
}
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.
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--];
}
}
};
Understood. Thank you Striver
LeetCode solution: class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int r=n-1;
for(int i=m;i
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?
Content is Absoluetly amazing
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.
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).
@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)
awesome, short of words to thank you really. making a v big impact n my coding life.
Can someone tell me the which of the optimal approach has better complexity in case of time or Both of'em are somewhat equal?
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???
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
A better idea would be to take 2nd solution and instead of sorting the two, we use the 3rd gap method on both the array.
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)
awesome explanation ever🙂
GOD LEVEL EXPLAIN!!!!!!...... please came up with string playlist.!!!!!!!
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--];
}
}
}
pls do complete this series upto ultra advance level.
Appreciate the efforts you are putting in. Content is Absoluetly amazing.
Understood! Super amazing explanation as always, thank you very very very much for your effort!!
Nice explanation.
Very nice explanation🔥
amazing explanation thanks a lot. 😊
Whats the intutition behind the gap method?
in first optimal approach , we are modifying both the array , but we have to merge both the array , pls explain
Thank you for provide good quality of content
Best explanation on TH-cam ❤🔥🔥🔥
Sir, I am not able to understand timecomplexcity can you make video on timcomplexcity
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.
Brother, please complete it as soon as possible.
Yes bro, just not wanting to compromise on the quality.
@@takeUforward please do take your time but do not compromise the quality thats what it is helpful to us students
Appreciate the efforts you are putting in 😇
crystalll clear bhaiya!!!!
In gap method....
When gap = 3, we compared 7 & 6 and didn't swap them.
yes there would be swapping
small issue at 19:54, should have swapped 7 and 6, but that's I guess okay 😅
Thank u Striver Understood
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
Thank you for great content striver bhaiya ❤
Better Approach ngl:
class Solution {
public:
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--];
}
}
}
};
Striver Sir You should have solved leetcode problem that's difficulty level is greater than this !
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
the optimal 1 code :
#include
#include
#include
void mergeTwoSortedArraysWithoutExtraSpace(vector &a, vector &b)
{
long long n=a.size();
long long m=b.size();
int left=n-1;
int right=0;
while(left>=0 && rightb[right]){
swap(a[left],b[right]);
left--;
right++;
}
else break;
}
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
}
can you explain why did he took a.begin(),a.begin()+m
What is the intuition for gap method?
one of the main constraint was the array must be without extra spaces......so its unclear whether we need to take one 0 or enitrely skip 0
in optimal first approach i think inbuilt sort use some memory so space is not O(1)
while using sort function you take into account only the time complexity, which is N logN, the space complexity is O (1).
@@saswatrath4646 why is that? I read somewhere that sort is based on a variation of quick sort which might take O(logN) stack space
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
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
Understood with ease 🤩..
LEETCODE NOT ACCEPTING OPTIMAL SOLUTION 1
left = n - 1
right = 0
# Swap the elements until arr1[left] is smaller than arr2[right]:
while left >= 0 and right < m:
if arr1[left] > arr2[right]:
arr1[left], arr2[right] = arr2[right], arr1[left]
left -= 1
right += 1
else:
break
# Sort arr1[] and arr2[] individually:
arr1.sort()
arr2.sort()
what i see that here in optimal code 1 we basically just sorting both of the arrays but not merging them to one sorted array
🤔
gap method solution not working in javascript because first time when gap =1 it should execute loop for adjacent elements for once. If gap =1, break the loop going forward . Let me know if I am wrong or any other best possible way.
Understood, thank you.
Understood 🙏🏻
understood :) Thanks a lot.
nice explanation,
Excellent Explainaton
Is this course available in udemy
The time Complexity will be O(m+n) & not min(m,n), see it
Thanks a lot striver❤
thank you for expaination
is it okay that first i merge both array and applied insertion sort
thnx for the amazing video ❤❤❤❤👌👌👌👌
Namaste bhaiya , last bit of code is not working properly.
could you please help me to do that .
where is the proof of second optimal solution that the algo works?
how did we make sure that it works and how did it was figured out?
1
why do we need two optimal approaches, when one gets the work done?
in case gap is odd , take the ceiling
In brute force, if a[left]
O(n+m) code. Very Easy To Understand :
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i=m-1,j=n-1,k=m+n-1;
while(i>=0&&j>=0)
nums1[k--]=nums1[i]>=nums2[j]?nums1[i--]:nums2[j--];
while(i>=0)
nums1[k--]=nums1[i--];
while(j>=0)
nums1[k--]=nums2[j--];
}
}
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 some One please explain what mistake does this code have i am sorting an array using Shell Sort
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;
}
};
why you did not swap at 19:37?
Yesss.... why he didn't swap that
UNDERSTOOD;