This. It is an easy question, some people would think hard or be confused about. This is the problem with programmers or engineers sometimes making something easy confusingly hard.
Counting sort has O (m + n) time and O (m + n) space where n is the # of seats and m is the number of students. Sorting is essentially in O(nlogn) + O(mlogm) time since both arrays were being sorted. But there was a constraint in this problem that n is up to 100 and m + n does not exceed 300
Exactly. Based on that, if I consider the algorithm takes less space and less time, I would go for sorting. It will work well even after removing the constraints.
if logn is of base 10 then any n below 10 or below 100 would have a significantly lower value than n + 100. After 100 nlogn will start doubling. So for O(n + 300) < (300 log 300)
This is an example of how to make an easy question confusing. Neet's explanation is good. But how is this question presented? It makes it confusing. Also, about the constraints. How I look at it is; students and seats are less than or equal 100 but not less than 1. Does that mean the. Max # you can iterate is 100? The number of items in each array doesn't matter? But both must not be greater than 100 or less than 1. Example if seats [1~100] and students [1~100] then the moves will be 0? Because every students have every seat?
Big Fan of your work here but I have one suggestion if you could give a formal proof for how the solutions works for questions like these it wud be excellent I dont think most people dont cover it nonetheless it is quite important too.
This question was so weirdly worded. Meanwhile a trivial solution is to find the difference between the sums of the arrays. It did solve 53 testcases for me 😅😂😂😂😂
The way this question was worded made it hard to understand.
This.
It is an easy question, some people would think hard or be confused about.
This is the problem with programmers or engineers sometimes making something easy confusingly hard.
sounds like a skill issue to me
@@RTZemun Yeah on part of the person who wrote this question
@@RTZemun shoo fly
@@GPT-X938 zap zap can win
Counting sort has O (m + n) time and O (m + n) space where n is the # of seats and m is the number of students. Sorting is essentially in O(nlogn) + O(mlogm) time since both arrays were being sorted. But there was a constraint in this problem that n is up to 100 and m + n does not exceed 300
Man finds counting sort hammer. Processed to see counting sort nails.
after seeing your diagram, I was able to come up with the solution, moving forward I'll try and see if I can draw the problem out
considering array is small sorting is sweet and simple approach. Counting sort can be discussed if interviewer ask for more optimised approach.
i literally had no idea what they were asking in this question….once nice thing in interviews is that at least you can ask clarifying questions
1. Sort both array.
2. Add abs different of same index value.
If you consider space complexity, nlogn solution would be preferable
Space complexity of python's built in sort (timsort variant) is theta n. So all the solutions are basically equivalent for time/space.
Space is not free for sort in python. It's omega(nlogn).
Exactly. Based on that, if I consider the algorithm takes less space and less time, I would go for sorting.
It will work well even after removing the constraints.
You are doing god's work. I can't describe to you how much your videos have helped me in learning algorithms. I will forever be grateful!
if logn is of base 10 then any n below 10 or below 100 would have a significantly lower value than n + 100. After 100 nlogn will start doubling. So for O(n + 300) < (300 log 300)
honestly can't say trying counting sort is meaningful in this problem.
but it was a great example to show big-O is not always correct measure
yeah i came up with both solutions and was confused why the regular sorting was consistently faster then couting sort
This is an example of how to make an easy question confusing.
Neet's explanation is good.
But how is this question presented? It makes it confusing.
Also, about the constraints. How I look at it is; students and seats are less than or equal 100 but not less than 1.
Does that mean the. Max # you can iterate is 100? The number of items in each array doesn't matter?
But both must not be greater than 100 or less than 1.
Example if seats [1~100] and students [1~100] then the moves will be 0? Because every students have every seat?
Following you since last 4 month with 95 percent consistency
Thanks for the different approaches.
Big Fan of your work here but I have one suggestion if you could give a formal proof for how the solutions works for questions like these it wud be excellent I dont think most people dont cover it nonetheless it is quite important too.
When the n is small, nlogn and n tend to be the quite the same. That is why sorting is better in this case.
My solution
seats = sorted(seats)
students = sorted(students)
res = 0
for i in range(len(students)):
res += abs(seats[i] - students[i])
return res
This week , Leetcode has made us to count numbers 👏👏
thanks man i've been doing the daily Q for the last few weeks and it's always good to double check against your solutions
I really liked the way, you explained about the need of those sort methods A.K.A Rant 😂
thank you for different solutions!
Sort both array
SUM += diff from i to n indices did the trick
AM I WRONG FROM DOING LIKE THIS
Commented by looking at the first half sorry !
This question was so weirdly worded.
Meanwhile a trivial solution is to find the difference between the sums of the arrays. It did solve 53 testcases for me 😅😂😂😂😂
Log100 is supposed to be 2 right?
that is when the base is 10 but in computer science generally the base is taken as 2 because of binary, so log 100 base 2 will be 6.64385618…
@@mohd.tabishkhan4868 You are absolutely right. Don't know why I thought this was actual math.
I just cam r to understand this question.
Nice 🎉
Seems like internship season started in leetcode. 😅
Bro leetcode problem no 481 try
2:22 lmao erase that one real quick
never try to relate real-world problems with dsa
Bro
The solution is not clear or convincing