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.

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

[@aritralahiri8321]

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

[@qbmain1487]

thanks! Finally solved after 1 day of struggling :(

[@jacksparr0w300]

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

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

[@aaronpcjb]

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

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

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

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

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

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

[@chicmac10]

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

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

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

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

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

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

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

[@neighboroldwang]

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

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

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

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

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

[@siyandasphesihlengcobo4623]

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

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

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

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

[@CSam-hc4uk]

Very clear explanation. Thank you very much!

[@NeetCode]

Thanks!

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

[@andre-ur6lf]

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

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

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

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

[@Jakirseu]

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

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

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

[@rajarajan1338]

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

[@HarshSharma-ff3ox]

Thank you for such a great solution 💯

[@harunguven8581]

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

[@UyenVyNguyen-r5m]

very easy to understand, thanks a lot!

[@hernanvelazquez1421]

Nice and clear explanation at the begining. Thanks.

[@iesmatty]

Thank you so much for your explanation

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

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

[@samandarboymurodov8941]

very good explanation. thank you!

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

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

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

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

[@nikhilgoyal007]

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

[@Ozaki978]

Very clear and helpful explanation,thanks!

[@JSH1994]

thank you! saving the day as always

[@saikoushik7626]

Definitely you are genius

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

[@medakremlakhdhar419]

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

[@osmanmusse9432]

Great Explanation

[@nileshdhamanekar4545]

Great job explaining!

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

[@SunGod-887]

thanks for this amazing explanation

[@divyam1175]

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

[@studyaccount794]

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

[@37zaidkhan29]

Good Explanation bro

[@shleebeez]

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

[@UddhikaIshara]

Thank you very much 🤩

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

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

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

[@sanooosai]

thank you sir

[@formulaint]

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

[@KillerMindawg]

sorting is O(nlogn)

[@georgeli6820]

amazing explanation! Thank you!

[@adityadhikle9473]

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

[@Rohitsingh2410]

Why start from back?

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

[@jamescoughlin6357]

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

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

[@harshverm776]

Thanks !!!

[@JordanRohilliard]

Ended up being a three pointer method lol

[@JohnDoe19754]

Thank you so much

[@chadguru9565]

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=(nums1).sort()

[@電腦騙徒剋星]

rubbish code

[@chadguru9565]

@@電腦騙徒剋星 Why rubbish? Because it's not optimal for memory? I'm not very good at this

[@g.deepakkrishnaa3847]

@@chadguru9565 it is o(nlogn) time complexity because the most optimal sorting algorithm that Python uses is merge sort and its time complexity is o(nlogn) which is higher than o(n)

[@gehadhisham2539]

Wow, thank you

[@oqant0424]

thanks

[@tatsuya370]

Nice explanation, do u have discord?

[@BTS__Army18]

Getting an error in line 2

[@roshanzameer5020]

Well, this isn't really a Easy problem.

[@ssuriset]

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

[@edwardteach2]

U a God

[@mgtowhour]

the time complexity is o(m+n) I think not o(n)

[@lingyundai964]

why?

[@leeroymlg4692]

o(m+n) simplifies to o(n). it's o(n)

[@akshaibaruah1720]

great!

[@nguyentuan1990]

how can this problem be easy?

[@RN-jo8zt]

it's medium level probkem

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

[@matthewzarate8851]

Lol, not easy.

[@sabu4539]

yeah its not, without using sort().