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
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++; }
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
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.
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.
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.
@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)
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--]; } } }
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
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.
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
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.
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
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.
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()
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
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--]; } } } };
The gap method explained in this video is not entirely correct. When gap becomes 1 we have to perform the iterations with gap = 1 up until our array is sorted. If we break away after only 1 iteration then it is possible that our array is not fully sorted.
Linear time which ig should be better the nlogn in method 2 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--]; } } }
Please watch our new video on the same topic: ruclips.net/video/n7uwj04E0I4/видео.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 RUclips
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
Thank you Striver for providing detailed videos on DSA. Really appreciate your work!
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;
}
};
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
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
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?
Optimal solution 2 was really good and your teaching skills made it easier and interesting
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?
can we consider this as optimal approach ??
public static void merge(int []a,int []b,int n){
int left = 0;
while(left
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
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n) {
for(int i=0; i
i have the same approch
Thank you Striver for making these in-depth very well explained videos
Respect++ for striver bhaiya.....
bhai aap genius ho!!.. real inspiration and best teacher to me...
your quality of teaching,frameworks and style of teaching all are superb sir💯
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.
Content is Absoluetly amazing
awesome, short of words to thank you really. making a v big impact n my coding life.
3rd Approach is amazing
Understood! Super amazing explanation as always, thank you very very very much for your effort!!
//Two line solution for(int i=0;i
Can someone tell me the which of the optimal approach has better complexity in case of time or Both of'em are somewhat equal?
Understood. Thank you Striver
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?
you are a god in programming, man.
LeetCode solution: class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int r=n-1;
for(int i=m;i
Appreciate the efforts you are putting in. Content is Absoluetly amazing.
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.
Very nice explanation🔥
@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)
in first optimal approach , we are modifying both the array , but we have to merge both the array , pls explain
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());
}
amazing explanation thanks a lot. 😊
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--];
}
}
}
Thank you for provide good quality of content
In gap method when the gap is 3 why do you don't swap 7 and 6.(7>6) 20:03
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
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.
Best explanation on RUclips ❤🔥🔥🔥
Appreciate the efforts you are putting in 😇
Thank you for great content striver bhaiya ❤
crystalll clear bhaiya!!!!
Understood 🙏🏻
Striver Sir You should have solved leetcode problem that's difficulty level is greater than this !
understood :) Thanks a lot.
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
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
Understood, thank you.
Understood with ease 🤩..
pls do complete this series upto ultra advance level.
Thank u Striver Understood
Whats the intutition behind the gap method?
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
UNDERSTOOD;
thank you for expaination
GOD LEVEL EXPLAIN!!!!!!...... please came up with string playlist.!!!!!!!
Optimal understood but leetcode not accepted solutina
thnx for the amazing video ❤❤❤❤👌👌👌👌
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???
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.
Excellent Explainaton
Thanks a lot striver❤
nice explanation,
Understood.
In gap method....
When gap = 3, we compared 7 & 6 and didn't swap them.
yes there would be swapping
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)
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?
why you did not swap at 19:37?
Yesss.... why he didn't swap that
Greak work brother!
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.
In brute force, if a[left]
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
Understood!🔥
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
🤔
Understood✅🔥🔥
Understood 🎉
Understood
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
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 case gap is odd , take the ceiling
Understood!
Is this course available in udemy
UNDERSTOOD
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
understood 👍👍
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--];
}
}
}
};
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 ?
yup idk why nobody noticed this
he has motioned below that he has done a mistake
The gap method explained in this video is not entirely correct. When gap becomes 1 we have to perform the iterations with gap = 1 up until our array is sorted. If we break away after only 1 iteration then it is possible that our array is not fully sorted.
is it okay that first i merge both array and applied insertion sort
tq tq very much
understood 👍
Namaste bhaiya , last bit of code is not working properly.
could you please help me to do that .
why do we need two optimal approaches, when one gets the work done?
superb
Linear time which ig should be better the nlogn in method 2
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--];
}
}
}