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; }
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
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
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]
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
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.
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)
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.
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:])
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.
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
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
Ok, I'm still traveling but I had already recorded this one a while back and just edited it.
you still uploaded
Thanks Neet, enjoy your vacation
Thank you
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;
}
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
great catch. since it's passed by reference it's pass.
I also noticed that and got confused, thanks for the comment
Good catch! I had similar doubt why using nums instead of arr at 16:00
awesome catch!
Your explanation of nlog(n) tc was brilliant. However some users can find the code a bit confusing.
Try this:
def merge_sort(self,arr):
if len(arr)
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
One of the cleanest explainations of Merge Sort on YT
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]
Yes, this is even better
I don't see it. Isn't this code execution creating new list?
# Dividing the array elements
L = arr[:mid]
# Into 2 halves
R = arr[mid:]
Thanks, had to revise this after seeing today's daily.
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
Your explanations are a thing of beauty ❤
I used heapsort. Do you recommend knowing the other algorithms by heart like Mergesort, Quicksort, etc.. for interviews?
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.
You can precalculate len(left) and len(right) in merge function to make it a little bit faster.
Best explanation of mergeSort so far
Nice, explanation of concept, simplicity of code is amazing, thank you for doing it :)
Awesome explanation
this question was asked inside the "insertion sort" lesson on neetcode D:
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)
@@doc9448 i think its there for you to do insertion sort
this was amazing!
I was waiting for your video. Great explanation as always 🔥🔥
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.
That is only if the items in the original list are non-primitives. For a list with primitives it's a copy by value.
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:])
I did try Quick Sort but still got TLE..
so here I am
Thank you Boy..
QuickSort does not pass in java as well. With all the tricks to have it nlogn
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.
it is not that official channel. but videos are same. how .? no copy right issue?
need an heapsort solution too :/
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
Heap sort is not better than merge/quick overall , but its memory efficient. You should have gone for heap sort bro :(
Why is i initialized with L and not 0. what is the problem if we initialize i = 0?
Hi, I also have this problem. Have you solved it?
why is not Quicsort working for this problem?
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
It's because one of the problems forces it into worst case which becomes n*n which causes tle
Quicksort's worst case time complexity is n^2 which does not satisfy the nlogn time complexity requirement
it was kinda easy problem
almost as if array sorting is one of the first things taught in DSA
d