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.

[@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.

[@theoreticalphysics3644]

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

[@thisinnotmystomach6279]

agreed

[@shrayanmandal2004]

agreed

[@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 🥰

[@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.

[@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]

[@Dotkt]

lol.

[@julio.carrasquel]

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.

[@aaronpcjb]

Going from right to left is genius. It was the missing piece needed for me to solve it in O(1) space.

[@neighboroldwang]

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

[@jacksparr0w300]

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

[@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 ....

[@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

[@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.

[@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 };

[@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

[@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 "

[@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)

[@chicmac10]

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

[@d_starcode1197]

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

[@lingshuaikong5644]

Actually, you can see @lileggy9553's comment. m is initially 3, so m is not the index but how many digits are in the array. So the condition for while loop should be >0 instead of >=0. I had the same confusion as you. But @lileggy9553's comment clarified that.

[@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 !

[@lingshuaikong5644]

Thanks!

[@sarvarkhalimov111]

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

[@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-- } } };

[@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

[@CSam-hc4uk]

Very clear explanation. Thank you very much!

[@NeetCode]

Thanks!

[@siyandasphesihlengcobo4623]

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

[@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.

[@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!

[@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

[@adityadhikle9473]

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

[@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.

[@JordanRohilliard]

I already know two pointer method is the way to solve. Just didnt solve in time so looking at the solution before I solve again on my own

[@samandarboymurodov8941]

very good explanation. thank you!

[@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)

[@HarshSharma-ff3ox]

Thank you for such a great solution 💯

[@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

[@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

[@Jakirseu]

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

[@UyenVyNguyen-r5m]

very easy to understand, thanks a lot!

[@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

[@hernanvelazquez1421]

Nice and clear explanation at the begining. Thanks.

[@iesmatty]

Thank you so much for your explanation

[@Ozaki978]

Very clear and helpful explanation,thanks!

[@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.

[@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 ✅

[@JSH1994]

thank you! saving the day as always

[@osmanmusse9432]

Great Explanation

[@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

[@saikoushik7626]

Definitely you are genius

[@nileshdhamanekar4545]

Great job explaining!

[@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

[@studyaccount794]

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

[@andre-ur6lf]

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

[@harunguven8581]

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

[@mrholeechit]

Question isn't it doing like this a bit better? Instead doing 2 whiles you can get away with just one for loop. var merge = function (nums1, m, nums2, n) { const n1 = [...nums1]; let i1 = m - 1; let i2 = n - 1; for (let i = nums1.length - 1; i >= 0; i--) { if (nums2[i2] >= n1[i1] || n1[i1] === undefined) { nums1[i] = nums2[i2]; i2--; } else { nums1[i] = n1[i1]; i1--; } } };

[@SunGod-887]

thanks for this amazing explanation

[@sanooosai]

thank you sir

[@divyam1175]

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

[@rajarajan1338]

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

[@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).

[@nikhilgoyal007]

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

[@UddhikaIshara]

Thank you very much 🤩

[@Dotkt]

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.

[@Dotkt]

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

[@37zaidkhan29]

Good Explanation bro

[@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).

[@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🤣🤣🤣

[@georgeli6820]

amazing explanation! Thank you!

[@medakremlakhdhar419]

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

[@harshverm776]

Thanks !!!

[@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 :)

[@tatsuya370]

Nice explanation, do u have discord?

[@akagamishanks7991]

Amazing explaination, but how is this an easy problem?

[@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.

[@jamescoughlin6357]

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

[@oqant0424]

thanks

[@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 ?

[@JohnDoe19754]

Thank you so much

[@gehadhisham2539]

Wow, thank you

[@shleebeez]

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

[@edwardteach2]

U a God

[@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.

[@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)

[@ssuriset]

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

[@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

[@Rohitsingh2410]

Why start from back?

[@akshaibaruah1720]

great!

[@JordanRohilliard]

Ended up being a three pointer method lol

[@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

[@roshanzameer5020]

Well, this isn't really a Easy problem.

[@formulaint]

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

[@KillerMindawg]

sorting is O(nlogn)

[@gopalchavan306]

nice

[@matthewzarate8851]

Lol, not easy.

[@sabu4539]

yeah its not, without using sort().

[@nguyentuan1990]

how can this problem be easy?

[@sleepypanda7172]

🤯🤯🤯🤯🤯🤯thanksssssssss

[@BTS__Army18]

Getting an error in line 2

[@vxcx1869]

How can this be considered easy for god sake 💀

[@Momentum_animation]

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

[@FactFinders-of3mu]

smart

[@RN-jo8zt]

it's medium level probkem