Merge Sorted Array - Leetcode 88 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@phantombeing3015]

It's not fully free though. It asks for subscription in some videos.

[@theoreticalphysics3644]

yeah ngl this wasn't "easy" imo. this really helped me though, thanks

[@thisinnotmystomach6279]

agreed

[@jpfdjsldfji]

Great solution man! Managed to come up with a slightly cleaner solution that avoids having to loop over n at the end to continue filling: i = m+n-1, m = m-1, n = n-1 while n >= 0: if m >= 0 and nums1[m] > nums2[n]: nums1[i] = nums1[m] m-=1 else: nums1[i] = nums2[n] n-=1 i-=1 Because we only care about iterating n overall, as that's our indicator that the fill has been completed, we can remove m>=0 from our while loop conditions and just ensure that we no longer consider m in our fill if it's completed. Both solutions ar efine, but if it's concision you're looking for, I hope that helps guys!

[@SAROJKUMAR-xe8vm]

nice sol'n.

[@jackfrost8969]

your index bounds are incorrect. this is correct solution in Java: class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int resultIndex = m + n - 1; while (n > 0) { if (m > 0 && nums1[m - 1] > nums2[n - 1]) { nums1[resultIndex] = nums1[m - 1]; m -= 1; } else { nums1[resultIndex] = nums2[n - 1]; n -= 1; } resultIndex -= 1; } } }

[@jpfdjsldfji]

@@jackfrost8969 They are correct- but as I've seen from your solution, they can be improved further for concision. Thanks for the insight, nice find.

[@Shubhamkumar-ng1pm]

its certainly not a leetcode easy its medium difficulty.

[@qbmain1487]

thanks! Finally solved after 1 day of struggling :(

[@aritralahiri8321]

Clear and Crisp explanation , always love your explanations . Gracias !

[@harpercfc_]

Not as marquee as other medium or hard problems are but I do have some takeaways from it. Thanks for your video as always 🥰

[@lamedev1342]

My way worked for a bit and was a lot more complicated. This was much better. Initially I just decided to iterate through nums1 to check if there was a 0, which indicated empty space. Then I just put the remaining values of nums2 in that order so all values would be filled. Then I performed selection sort on nums1 to sort. It didn't work because an array could have [-1,0,3,0,0,0]

[@Se7_7]

lol.

[@jacksparr0w300]

I really appreciate that example and clarity on that edge case.

[@neighboroldwang]

My brain blowed up with these three pointers... Good brain training...

[@diassyes]

Thanks. I saw a more minimalistic version in discussions (Go language): func merge(nums1 []int, m int, nums2 []int, n int) { for n > 0 { if m == 0 || nums1[m-1] < nums2[n-1] { nums1[m + n - 1] = nums2[n-1] n-- } else { nums1[m + n - 1] = nums1[m-1] m-- } } }

[@nhbknhb]

this one is cool

[@crimsonghoul8983]

There is a small issue here. n > 0 would work if m > n. Some test cases would fail if only n > 0 was utilized. Also, assigning m + n -1 as last simplifies the program.

[@sarvarkhalimov111]

Thank you, with your step by step explanation, it was easy to grasp and follow.

[@CSam-hc4uk]

Very clear explanation. Thank you very much!

[@NeetCode]

Thanks!

[@TheVzlalover]

Thanks for the video! Exactly at 3:13, when you said "How do we get the largest value?", I already got the idea how to optimally solve the problem.

[@d_starcode1197]

Why the condition for while loop is > 0 ,it should be >=0 right? Because it needs to chsck the first element also

[@siyandasphesihlengcobo4623]

This was a superb explaination! Other videos were complicating it.

[@spaghettiking653]

Yay, I managed to get this one one my own. I was wondering what other algorithm you could've done, since an O(m+n) solution is supposed to be optimal.

[@shamikguharay3177]

Some test cases will fail for this. Added latest code using similar approach that gets passed for all test cases.. class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ last = m + n - 1 while m > 0 and n > 0 : if nums1[m-1] > nums2[n-1]: nums1[last]=nums1[m-1] m -= 1 else: nums1[last]=nums2[n-1] n -=1 last -= 1 while m == 0 and n > 0: nums1[last]=nums2[n-1] n -= 1 last -= 1 # No need to handle remaining elements of nums1 because they are already in place #while m > 0 and n == 0: # nums1[last] = nums1[m-1] # m -= 1 # last -= 1 print(nums1)

[@TheArcticKitten]

isn't this technically a threepointer? cause of last? either way great and clear solution and explanation thanks

[@gottliebuahengo1236]

No, the other it's not. The loop variables (n & m) are iterators, not pointers.

[@HarshSharma-ff3ox]

Thank you for such a great solution 💯

[@harrisoncramer]

Interestingly, the n value here is actually not needed, since it will always be equal to the length of the second array and can be derived. See: function mergeArrays(nums1: number[], m: number, nums2: number[]) { let target = nums1.length - 1; // Last index of first array let p1 = m - 1; // Pointer to last non-zero element in first array let p2 = nums2.length - 1; // Pointer to last element in second array while (p2 >= 0) { if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[target] = nums1[p1]; target-- p1-- } else { nums1[target] = nums2[p2]; target-- p2-- } } };

[@samandarboymurodov8941]

very good explanation. thank you!

[@mcafalchio]

I really like your solution, I was going like that but got lost in the last while. I am tottaly in favor of less weird solutions

[@Eduardo-Alvarez-Hernandez]

I have another solution which I believe is simpler and more elegant with the same time complexity of O(n): class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: for i in range(len(nums2)): nums1[m+i] = nums2[i] nums1.sort() Hope it helps! :)

[@rafeeali8307]

sorting is nlogn

[@lileggy9553]

Hey! Amazing and incredibly helpful video! Just wanted to point out a slight error at 5:39 m and n are not the indexes of the last value but rather they are specifying the amount of numbers in each array The code you've written is correct as the index of the last element = the total length - 1, but is not aligned if m and n were indexes themselves as instead you would have to add 1 Please correct me if I'm wrong, hope this helps out anyone confused on this bit!

[@vinhnghiang1273]

thank you, i was counting for several minutes to try understand what he was saying !!! I think you're right !

[@hernanvelazquez1421]

Nice and clear explanation at the begining. Thanks.

[@UyenVyNguyen-r5m]

very easy to understand, thanks a lot!

[@Ozaki978]

Very clear and helpful explanation,thanks!

[@nileshdhamanekar4545]

Great job explaining!

[@jsarvesh]

Excellent explanation! key example i feel for this problem is nums1 = [4,5,6] and nums2=[1,2]; also using write_pointer instead of last was super helpful while writing code

[@iRYO400]

Before watching the video solved it by myself, runtime was O(N*logM + log(M+N)), that's not satisfied me. Then, once I saw the picture at 3:22, I tried again and got O(M + N). Of course, if I counted in a right way

[@Jakirseu]

We already checked n > 0 in the first while loop. Why we need secondary while loop with n > 0 ?

[@flying-musk]

Hi @NeetCode first of all, thanks for your sharing, it's clever. would like to share here one point we actually only need to go through nums2 var merge = function (nums1, m, nums2, n) { let i = m - 1; let j = n - 1; let k = m + n - 1; while (j >= 0) { if (nums1[i] >= nums2[j]) { nums1[k] = nums1[i]; i--; } else { nums1[k] = nums2[j]; j--; } k--; } // we actually only need to go through nums2 };

[@varunsharma7911]

Hi, the algorithm does not seem to work for the latest test cases. Also the m > 0 and n > 0 instead of m >= 0 and n >= 0 seems to cause problems too because it fails to consider the last remaining indices which are 0.

[@varunsharma7911]

Test cases it caused problems with: tc1: nums1 = [2, 0], m = 1, nums2 = [1], n = 1 tc2: nums1 = [0], m = 0, nums2 = [1], n = 1

[@finitehour]

Change the m >= 0 to m > 0. It will work with the latest test cases.

[@osmanmusse9432]

Great Explanation

[@JSH1994]

thank you! saving the day as always

[@notTejaVyas]

the fact that the zeroes at the end of the list were always exactly equivalent the length of array 2 let me just: nums1.reverse() for i in range(len(nums2)): nums1[i] = nums2[i] nums1.reverse() nums1.sort() would fall apart if they added edge cases though, especially considering that in the real world, the array length would double when i add values beyond a threshold, not extend by length(n)

[@iesmatty]

Thank you so much for your explanation

[@andrewchen2349]

Thank you for this video! Yet, I think line 14 is not necessary, and line 19 can be changed to n-=1. The reason is value "last" will decrease automatically if m or n decreases by 1. I tried it, and it worked!

[@aaaa-ez1ff]

very clear explanation, could you please also add the complexity analysis? thanks.

[@7inzy]

Time: O(n) O(m+n) exactly. same, linear. linear while loop going thru both lists. Space: O(1). no extra space being used

[@georgeli6820]

amazing explanation! Thank you!

[@Se7_7]

i dont understand yet, why is there nums1[m] if m is number of element.. which is suppose to be out of bounds, since array starts counting from 0.

[@Se7_7]

okay, just finishing the video! yes, n-1 and m-1 is important, why is my code outter bound then!!

[@echo__jyc]

clear and simple! thanks

[@moulee007]

he took "last = m+n-1". thats okay but when he compared " if nums1[m] > nums2[n]" here why didnt he take " if nums1[m-1] > nums2[n-1]" like this? we have to take elements inside array right so nums1[0] will be the first element not nums1[1] . can you explain

[@moulee007]

sorry i didnt see the video till the end : ) my bad. he actually changed it .frustated for no reason🤣🤣🤣

[@SunGod-887]

thanks for this amazing explanation

[@saikoushik7626]

Definitely you are genius

[@rafeeali8307]

This solution is easier in my opinion "class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Merges nums2 into nums1 as one sorted array in-place. """ # Set pointers for nums1 and nums2 i = m - 1 # Pointer for nums1 j = n - 1 # Pointer for nums2 sortedIndex = n + m - 1 # Pointer for where the merged number goes # Iterate from the back and fill nums1 from the largest values while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[sortedIndex] = nums1[i] i -= 1 else: nums1[sortedIndex] = nums2[j] j -= 1 sortedIndex -= 1 "

[@chicmac10]

class Solution(object): def merge(self, nums1, m, nums2, n): nums1[m:] = nums2[:n] nums1.sort()

[@ganeshmurugan5498]

9:19 why we have to update the pointer n, last = n - 1, last - 1 without this line leetcode says time exceeded why

[@raahim88991]

If we dont do this loop will continue to run forever

[@ganeshmurugan5498]

@@raahim88991 thanks

[@harunguven8581]

A little correction m and n is the length of nums1 and nums2, not last element's index. Thanks for great explanation.

[@krishnajoshi364]

Thank you :) I had a question. If nums1 was not large enough to accommodate both arrays then in that case this would have become merge part of merge & sort algorithm. In that case would it have been better to append the remaining elements at nums1 or create a new empty array and put the sorted elements in that?

[@davinmercier2895]

I think it is because the fastest sorting algorithm is O(N × log N). The goal is to get O(N).

[@siddheshmhatre2811]

# simple and optimal j = 0 for i in range(len(nums1)): if nums1[i] == 0 and j < n: nums1[i] = nums2[j] j += 1 nums1.sort() nums1

[@andre-ur6lf]

what if nums2 values are smaller than nums1? is it still efficient to start adding the numbers from back to front?

[@eloscvr]

C++ shortcut: class Solution { public: void merge(vector& nums1, int m, vector& nums2, int n) { for(int i = 0; i

[@sajramkisho9991]

O(NlogN) time complexity by the way ....

[@adityadhikle9473]

When you recorded this video Likes : 2972, Dislikes: 4690. Now when I'm commenting Likes: 8067 Dislikes: 715. Such a turn around.

[@jacksblue]

In my solution, I just copied the the numbers from the second array into the first array where the 0s are. The I used Insertion Sort to sort the array but I think this is better

[@sunnyarora3557]

lol same

[@37zaidkhan29]

Good Explanation bro

[@UddhikaIshara]

Thank you very much 🤩

[@gehadhisham2539]

Wow, thank you

[@sanooosai]

thank you sir

[@JohnDoe19754]

Thank you so much

[@nikhilgoyal007]

Line 18 in the end should say nums1[last] = nums2[n-1] , no ?

[@harshverm776]

Thanks !!!

[@divyam1175]

why u write nums1[m] ?? should not it be nums1[m-1]?? 6:50

[@Shanky_17]

why cant i iterate over list 1 and insert list 2 nodes whenever the situation agrees ?and also modifying list 1 at the same time ?

[@andyzhang6965]

I think this solution would be O(n^2). You are iterating through list 1 (O(n)), then you are inserting when the situation agrees (O(n) to use insert in python). O(n) * O(n) = O(n^2)

[@Shanky_17]

@@andyzhang6965 oh ! got it mate thanks :)

[@studyaccount794]

Looks like leetcode removed the dislikes from this problem. It has only 583 dislikes now.

[@azijulmunsi5888]

can anyone explain me last line of code? would not while loop also work for the leftovers too? just like 3,2 swapping position ?

[@solo-angel]

class Solution(object): def merge(self, nums1, m, nums2, n): last = m + n - 1 while m > 0 and n > 0: if nums1[m-1] > nums2[n-1]: nums1[last] = nums1[m-1] m -= 1 else: nums1[last] = nums2[n-1] n -= 1 last -= 1 while n > 0: nums1[last] = nums2[n-1] n -= 1 last -= 1

[@medakremlakhdhar419]

Why not just put the nums2 inside nums1 and sort the array ? wouldn't that be much easier ?

[@shleebeez]

which section is this under on the site? i'm not seeing it

[@ssuriset]

If this is supposed to be "easy" I am fucked

[@tatsuya370]

Nice explanation, do u have discord?

[@hasanenesturan5936]

Its not that hard You can do just for j in range(n): nums1[m+j] = nums2[j] nums1.sort() thats all nums1[m+j] meaning fourth element or after the elements of nums1 you are adding to that empty space the first element of nums2 and the others after that just sorting the array.

[@Desmond-yd7ld]

Here, time complexity would be O(nlogn) but the approach in the video has linear time O(n) complexity and uses constant space.

[@MrGermanChe]

how about this solution? : def mergeSortedArray( lst1 :list, lst2 :list) -> list : return [item for element in list(zip(lst1,lst2)) for item in element]

[@IwoGda]

1. In this problem you're not supposed to return anything (should be done in-place) 2. It's O(n) additional memory (like first solution in video) couse you're making a list in memory with list comprehension. 3. I do not think your list is sorted On the other note, you have to think about memory while using list comprehensions becouse they are stored there. Generators store only one value at a time so sometimes it's better to use those.

[@rajarajan1338]

for i in range(n): nums1[m+i] = nums2[i] nums1.sort()

[@RafiqulIslam-je4zy]

void merge(vector& nums1, int m, vector& nums2, int n) { for(int i=m;i

[@TheJanstyler]

Higher time complexity. Sort is O(nlogn). This one is O(n+m).

[@jamescoughlin6357]

I don't understand, I think im going to have to watch this like three times in a row

[@Rohitsingh2410]

Why start from back?

[@akagamishanks7991]

Amazing explaination, but how is this an easy problem?

[@akshaibaruah1720]

great!

[@oqant0424]

thanks

[@Arunak13203]

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1.sort() index=0 if n>0: for i in range(0,len(nums1)): if nums1[i]==0: nums1[i]=nums2[index] index+=1 if index==n: break nums1.sort() return nums1 Accepted ✅

[@vishnunarayanan4397]

Can we merge it from the beginning ?

[@sameerkrbhardwaj7439]

don't do that you have to manage much corner cases and you have to write too many cases.

[@amulyagunturu3816]

How two 2 came you compares 1 and 2 at first 1 is min so we inserted 1 next 2,5 2 is min but next how 2 came

[@edwardteach2]

U a God

[@hippybonus]

Can we put array2 into the end of array1 and use the sort() function? Like this: for i in range(n): nums1[m+i] = nums2[i] nums1.sort()

[@clashgamers4072]

O(nlogn) for sorting

[@ritchievales]

I did this in Java and it takes only 2ms in solve all the testcases however I think this problem is meant to use a two pointer approach

[@ankurrawat5156]

simple java solution below.. class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int j=0; for(int i=m;i

[@kuno6725]

Won’t that not have runtime of O(m + n)

[@matthewzarate8851]

Lol, not easy.

[@sabu4539]

yeah its not, without using sort().

[@formulaintuition8756]

Just add nums2 to the empty slots in nums1, then sort nums1.

[@KillerMindawg]

sorting is O(nlogn)

[@BTS__Army18]

Getting an error in line 2

[@roshanzameer5020]

Well, this isn't really a Easy problem.

[@nguyentuan1990]

how can this problem be easy?

[@gopalchavan306]

nice

[@FactFinders-of3mu]

smart

[@sleepypanda7172]

🤯🤯🤯🤯🤯🤯thanksssssssss

[@RN-jo8zt]

it's medium level probkem

[@rishabhsharma9719]

Can We can also do this by using merge sort?

[@NeetCode]

I think we can, but the time complexity would be worse since merge sort is O(nlogn)

[@vxcx1869]

How can this be considered easy for god sake 💀

[@Momentum_animation]

Yoo wanna be leetcode buddies 😂😂😭,I hope we aren't cooked

[@akagamishanks7991]

last = m + n - 1 don't make any sense to me bc m ist the index of last value of nums1 and n is the index of last value auf nums2. So considering the example from the vid m would be 2 and n would also be 2. So 2+2=4 which is not the last index of m

[@kngcrisp3265]

M and n are not index values

[@jeffnguyen91]

What's the difference of this and merge two sorted lists? (kzbin.info/www/bejne/jnrHmpqhbpppq5I) I thought arrays in Python are called lists?

[@NeetCode]

Yeah, arrays in python are called lists, but the merge two sorted lists video is about Linked lists. The name does make it confusing, sorry about that.

[@Everafterbreak_]

i've solved hard ones easier than this one

[@rafeeali8307]

fr this fucked up my head, at first I thought it would be an easy merge problem like in merge sort