Sort an Array - Leetcode 912 - Python

[@NeetCodeIO]

Ok, I'm still traveling but I had already recorded this one a while back and just edited it.

[@BurhanAijaz]

you still uploaded

[@yang5843]

Thanks Neet, enjoy your vacation

[@vixguy]

Thank you

[@dennisgatere7821]

A missed opportunity for this question IMO is counting sort, just tried it and it beats 99% when I submitted it but you need shifting for negative values, check it out and hopefully one day you add it to the channel. public int[] sortArray(int[] nums) { if (nums == null || nums.length == 0) return new int[]{}; int shift = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int num : nums) { shift = Math.min(shift, num); max = Math.max(max, num); } max -= shift; int[] counts = new int[max + 1]; for (int num : nums) { counts[num - shift]++; } for (int num = 0, i = 0; num < counts.length; num++) { while (counts[num] > 0) { nums[i++] = num + shift; counts[num]--; } } return nums; }

[@tunguyenxuan8296]

At 16:00, the code must be arr[i] = left[j]. The solution will actually work if you put it nums[i] = left[j] as you will assign nums to arr, but for the correctness, it must be arr inside merge function

[@karanssh]

great catch. since it's passed by reference it's pass.

[@adarshsasidharan254]

I also noticed that and got confused, thanks for the comment

[@snoopdogg_007]

Good catch! I had similar doubt why using nums instead of arr at 16:00

[@metarus208]

awesome catch!

[@HoppyGamer]

One of the cleanest explainations of Merge Sort on YT

[@DmitriyKl]

For those struggling to understand this solution, there's actually a slightly more straightforward way that was easier for me to understand. The overall approach is the same, there are 3 distinct steps: 1 - check if base case 2 - sort left and right halves 3 - merge sorted halves the solution becomes: # base case - array already sorted because len is

[@rahulsbhatt]

Thanks, had to revise this after seeing today's daily.

[@DimaLifeIsGood]

Nice, explanation of concept, simplicity of code is amazing, thank you for doing it :)

[@adrianfrankowski3784]

You can precalculate len(left) and len(right) in merge function to make it a little bit faster.

[@cosepeter2197]

Your explanations are a thing of beauty ❤

[@krateskim4169]

Awesome explanation

[@sarvesh6785]

I was waiting for your video. Great explanation as always 🔥🔥

[@aliramazani2024]

Great job. However, the code below is slightly more efficient than your code because it performs all operations on the original list instead of creating new lists 'left' and 'right'. Overall, it was great to learn your approach as well. def mergeSort(arr): if len(arr) > 1: # Finding the mid of the array mid = len(arr)//2 # Dividing the array elements L = arr[:mid] # Into 2 halves R = arr[mid:] # Sorting the first half mergeSort(L) # Sorting the second half mergeSort(R) i = j = k = 0 # Copy data to temp arrays L[] and R[] while i < len(L) and j < len(R): if L[i]

[@varshasingh1299]

Yes, this is even better

[@degamer106]

I used heapsort. Do you recommend knowing the other algorithms by heart like Mergesort, Quicksort, etc.. for interviews?

[@garth2356]

I don't know what you mean by "know them by heart" but you should be able to write those algorithms and understand what every statement does so that you can manipulate them according to your need.

[@dheerendrapratapsingh9406]

Best explanation of mergeSort so far

[@TheSiddhaartha]

The two arrays in *merge* method, still overwrite the *nums* array. In python, array slice copies by reference and not value. So better use .copy after slice eg arr[L:M+1].copy(). Otherwise answers are incorrect on computer. Maybe LeetCode accepted it with some sort of inbuilt conversion but Python interpreter gave incorrect results. So I used .copy() which solved the problem.

[@u4rr837]

I passed this problem on leetcode using quick sort. just randomly choose pivot and randomly separate elements with same key. It's quite inefficient though.

[@mufaddaltatiwala2199]

You don't need to pass arr as an argument to the merge and mergeSort methods since they are already inside the sortArray, instead you can simply modify the nums array from both these methods and return nums in the end

[@khyunwoo1]

this question was asked inside the "insertion sort" lesson on neetcode D:

[@doc9448]

I noticed that too. I skipped it there, marked the lesson complete and came back to it in the merge sort lesson (it also appeared there in the leetcode section)

[@ahmadbasyouni9173]

@@doc9448 i think its there for you to do insertion sort

[@mahendrakoteri9233]

I did try Quick Sort but still got TLE.. so here I am

[@user-du9sh8ld7p]

Why is i initialized with L and not 0. what is the problem if we initialize i = 0?

[@YINXUANYIN]

Hi, I also have this problem. Have you solved it?

[@hasibqureshi6409]

it is not that official channel. but videos are same. how .? no copy right issue?

[@pwnweb5734]

need an heapsort solution too :/

[@mirshodoripov1035]

why is not Quicsort working for this problem?

[@mirshodoripov1035]

class Solution: def sortArray(self, nums: List[int]) -> List[int]: import random if len(nums) < 2: return nums # base case else: random.shuffle(nums) pivot = nums.pop() # recursive case less = [nums[i] for i in range(len(nums)) if nums[i] pivot] return self.sortArray(less) + [pivot] + self.sortArray(greater) return nums

[@benpurcell591]

It's because one of the problems forces it into worst case which becomes n*n which causes tle

[@valorantfever3990]

Heap sort is not better than merge/quick overall , but its memory efficient. You should have gone for heap sort bro :(

[@PannyaTrehan]

d

[@BurhanAijaz]

it was kinda easy problem

[@MeanSoybean]

almost as if array sorting is one of the first things taught in DSA