another approach is to think this way: first all would go to city A, and now you have to move one person to city B while keep the total cost to be minimum, what would you do? after the move the cost would be sum(a)-a[k]+b[k] = sum(a)-(a[k]-b[k]), so you would move the person that has the highest difference from b-a. and then so on and so forth.
DFS is much easier to understand, with crystal clear logic. The greedy solution is almost impossible to come up with. cache={} def dfs(k, k1, k2): if (k1,k2) in cache: return cache[(k1,k2)] if k>len(costs)-1: return 0 l=10**10 r=10**10 if k1
I can always code the solution after I hear your explanation. I never see your code. But getting that thought and approach always stump me and I keep on thinking complicated intuitive ways to solve it.
Nice, the elegant solution mentioned (in the discussion) has for i in range(n // 2): minCost += (costs[i][0] + costs[n-i-1][1]) which can be made more elegant to for i in range(n): minCost += costs[i][i//(n//2)]
I am sure why cache would work with just counts, as countA=1 and countB=1 with two different total received mean different output, which means we not calculate all possibilities, any help?
What's the minimum possible cost regardless of how many people go to A or go to B? The minimum cost for each person, right? So, divide people into two groups. Those who have cost of flying to A less than flying to B. These people want to fly to A to save money. And the second group is those who want to fly to B. Now we have the minimum possible cost but distribution of people might be wrong. So if the groups turned out to have n people each, then we are done. If some group is larger than another, think how do you move people from this larger group so that each group has n people? Since now you have the minimum possible cost, you want to move people in the way that minimize the additional cost. Let's imagine that group B is larger. Then to minimize additional cost we would like to move those people to group A who will suffer the least by moving to flight to A. Or in other words we want to minimize additional cost from moving a person to group A and maximize the cost reduction in group B. Thus we tend to search people with cost of flying to A as little as possible and cost of flying to B as much as possible. Looking carefully at it shows that it is the same as just sort the differences.
So I'm a Computer Science student. I can answer the problems mathematically but actually implementing it in code is a very difficult task for me. Maybe it's because I only just started doing leetcode questions and I don't do coding unless I'm doing university work. Anyone have the same problem?
Yes, and tbh, everyone has the same problem when they start Leetcoding. You're applying both problem solving techniques AND language syntax. It isn't easy. It's like being a baby and being told that you need to understand grammar at the same time you are learning vocabulary. You can't just know these things from zero. You build intuition for the problem, and then slowly code it. The more you do it, the faster you will get at coding your solutions from scratch.
This solution is not intuitive at all; this type of sorting is very tricky. It's much easier to sort the costs by absolute difference and then, while both cities are not equal N, fill them with minimums. Once one city is full (equal to N), put everything into the second city
@@subinnair3835 and I see 2 Amazon and 2 Facebook. You cant say its FB(Meta) question if it was asked 26 times by Bloomberg and only 2 times by FB in a year
I was asked this question in one of the interview. I couldn't solve it. Because its really HARD. Just because leetcode marks them as medium it doesn't need to be medium. And interviewers grade you thinking that you can't solve medium also. So its a reject. Honestly, what's the point of these question in real world use case. Which company is running short of budjet to send employee overseas so that they can make millions for the company only. These questions are so useless
Min Heap: def twoCitySchedCost(self, costs: List[List[int]]) -> int: minH = [] for i, cost in enumerate(costs): heapq.heappush(minH, (cost[0] - cost[1], i)) res = 0 for _ in range(len(costs) // 2): index = heapq.heappop(minH)[1] res += costs[index][0] for _ in range(len(costs) // 2): index = heapq.heappop(minH)[1] res += costs[index][1] return res
Thanks for doing the daily leetcode challenge. Please don't stop
He’s a beast
wow this looked so difficult before you explained it. Those logic explanations are so good
Nice vid Man I got the oracle cloud services because of your channel
another approach is to think this way: first all would go to city A, and now you have to move one person to city B while keep the total cost to be minimum, what would you do? after the move the cost would be sum(a)-a[k]+b[k] = sum(a)-(a[k]-b[k]), so you would move the person that has the highest difference from b-a. and then so on and so forth.
your approach worked like charm with 3ms runtime. Thanks mark.
we can do A-B and then take the first half of array for A and 2nd half for B. That will also work.
DFS is much easier to understand, with crystal clear logic. The greedy solution is almost impossible to come up with.
cache={}
def dfs(k, k1, k2):
if (k1,k2) in cache:
return cache[(k1,k2)]
if k>len(costs)-1:
return 0
l=10**10
r=10**10
if k1
I can always code the solution after I hear your explanation. I never see your code. But getting that thought and approach always stump me and I keep on thinking complicated intuitive ways to solve it.
Replacing sorting with median finding makes this solution O(n) in time complexity.
Nice, the elegant solution mentioned (in the discussion) has
for i in range(n // 2):
minCost += (costs[i][0] + costs[n-i-1][1])
which can be made more elegant to
for i in range(n):
minCost += costs[i][i//(n//2)]
elegant, but so hard to read haha
looked very difficult. but i actually understood how to get there!
I am sure why cache would work with just counts, as countA=1 and countB=1 with two different total received mean different output, which means we not calculate all possibilities, any help?
does using heaps to sort while appending is little better?
No way I literally solved this question this afternoon, and you now solved it. Damn thats such a coincidence.
since it is 'problem of the day' ;-)
but how to come up with greedy solution on our own? Whats the natural thought process behind it?
What's the minimum possible cost regardless of how many people go to A or go to B? The minimum cost for each person, right?
So, divide people into two groups. Those who have cost of flying to A less than flying to B. These people want to fly to A to save money. And the second group is those who want to fly to B.
Now we have the minimum possible cost but distribution of people might be wrong.
So if the groups turned out to have n people each, then we are done.
If some group is larger than another, think how do you move people from this larger group so that each group has n people? Since now you have the minimum possible cost, you want to move people in the way that minimize the additional cost.
Let's imagine that group B is larger. Then to minimize additional cost we would like to move those people to group A who will suffer the least by moving to flight to A. Or in other words we want to minimize additional cost from moving a person to group A and maximize the cost reduction in group B. Thus we tend to search people with cost of flying to A as little as possible and cost of flying to B as much as possible.
Looking carefully at it shows that it is the same as just sort the differences.
@@eugeneshcherbo9821 thank you so much for that breakdown, very helpful in building the intuition
It's great to see the efficient solutions. Today I also solved it though.
Awesome explanation!! This is a super random qn...can we expect a face reveal? xD
Thanks for your effort 😘😘
ha for once, I solved a question before you did 🤣, (I am still going to watch the video though, I want to see if I wrote the most efficient solution)
Sir can you suggest me please where i can learn DS in python .
So I'm a Computer Science student. I can answer the problems mathematically but actually implementing it in code is a very difficult task for me. Maybe it's because I only just started doing leetcode questions and I don't do coding unless I'm doing university work. Anyone have the same problem?
Yes, and tbh, everyone has the same problem when they start Leetcoding. You're applying both problem solving techniques AND language syntax. It isn't easy. It's like being a baby and being told that you need to understand grammar at the same time you are learning vocabulary. You can't just know these things from zero. You build intuition for the problem, and then slowly code it. The more you do it, the faster you will get at coding your solutions from scratch.
You can learn fancy tech skills in weeks. But solving leet code problems took years of practice.
Excellent 👏👏👏👏
Can someone please explain why DP solution had complexity O(n*n).
This solution is not intuitive at all; this type of sorting is very tricky. It's much easier to sort the costs by absolute difference and then, while both cities are not equal N, fill them with minimums. Once one city is full (equal to N), put everything into the second city
Can I plz see the alternative way to solve it using DP in code form? Thanks.
Well preview is not actually accurate. Based on data from leetcode this question is asked only by Bloomberg in the last 0-6 months
Its Accurate !
Check in 6months-1year category
@@subinnair3835 and I see 2 Amazon and 2 Facebook. You cant say its FB(Meta) question if it was asked 26 times by Bloomberg and only 2 times by FB in a year
@@Code8-o4c I mean Meta did ask it. It would be proper to put Bloomberg however.
Great Great Great
First
I was asked this question in one of the interview. I couldn't solve it. Because its really HARD. Just because leetcode marks them as medium it doesn't need to be medium. And interviewers grade you thinking that you can't solve medium also. So its a reject. Honestly, what's the point of these question in real world use case. Which company is running short of budjet to send employee overseas so that they can make millions for the company only. These questions are so useless
Min Heap:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
minH = []
for i, cost in enumerate(costs):
heapq.heappush(minH, (cost[0] - cost[1], i))
res = 0
for _ in range(len(costs) // 2):
index = heapq.heappop(minH)[1]
res += costs[index][0]
for _ in range(len(costs) // 2):
index = heapq.heappop(minH)[1]
res += costs[index][1]
return res
It's great to see the efficient solutions. Today I also solved it though.