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

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

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

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

[@HoppyGamer]

One of the cleanest explainations of Merge Sort on YT

[@adrianfrankowski3784]

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

[@bombrman1994]

this video would get more than a million videos if it was named properly and included anywhere in description or title the tag "merge" sort, most people explain it so vaguely

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

[@cosepeter2197]

Your explanations are a thing of beauty ❤

[@rahulsbhatt]

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

[@dheerendrapratapsingh9406]

Best explanation of mergeSort so far

[@malakggh]

there are no reason to use two pointers L and R. its same if we create a new sub array each time!! like this: l_arr = merge_sort(arr[:m]) r_arr = merge_sort(arr[m:])

[@DimaLifeIsGood]

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

[@krateskim4169]

Awesome explanation

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

[@ttrey743]

That is only if the items in the original list are non-primitives. For a list with primitives it's a copy by value.

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

[@rayray66]

this was amazing!

[@mahendrakoteri9233]

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

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

[@ValhaVaiyagam]

Thank you Boy..

[@sarvesh6785]

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

[@hasibqureshi6409]

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

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

[@pwnweb5734]

need an heapsort solution too :/

[@DEVANSHGOYAL-i7h]

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?

[@valorantfever3990]

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

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

[@penguinduck5979]

Quicksort's worst case time complexity is n^2 which does not satisfy the nlogn time complexity requirement

[@PannyaTrehan]

d

[@BurhanAijaz]

it was kinda easy problem

[@MeanSoybean]

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