I really enjoy the way you approach the problem and solve it with different methods. What would be your approach if we want to schedule the same number of candidates for 3 different cities instead? I could only think of using brute force(back tracking) at the moment.
Nice explaination Sir, Lockdown and Leetcode with @Techdose. I saw almost 70./. of your videos your explaination is clear and too the point in all videos. Keep going Sir !!
Java solution class Solution { public int twoCitySchedCost(int[][] costs) { Arrays.sort(costs,(a,b)->(a[0]-a[1])-(b[0]-b[1])); int len=costs.length; int res=0; for(int i=0;i
Hey,I think after sorting it is not necessary that we have to take first n/2 from cityA..it can be from CityB also..i think it will be the min(cityA,cityB)..then whoever fills first rest will be from remaining cities filling count.Its while explaining the solution..
Not needed to compare...as here absolute difference is not taken while sorting..so in every case first half will be from A, second half will be from B city.
I already said that we are sorting based on profit we would get if we choose to go to city A. So the first N/2 elements will give max profit for going to city A. According to constraints of the problem, you had to send N/2 candidates to city A. So we needed to choose all first N/2 elements after sorting based on profit. Re-watch the video and listen carefully. I think it's easy to understand. You will get it.
@@uk007rider if you sort in decreasing order. the first half will be for city B and the second half for city A. in your approach you must have taken absolute difference. try to dry run for different input data. you will get why it is working and how it is not working in case of absolute difference
The heap approach will also be O(nlogn) as after every deletion of max from heap balancing the heap everytime will take O(logn) time. The heap won't balance itself in O(1) time.
c++ Heap solution: // Time complexity: O(NlogN) -> we need to push all the items in the heap // Space complexity: O(N) class Solution { public: int twoCitySchedCost(vector& costs) { auto comp = [](pair& lhs, pair& rhs){ return lhs.first > rhs.first; };
priority_queue maxHeap(comp); int n = costs.size(); for (int i = 0; i < n; ++i ) { maxHeap.push({costs[i][1] - costs[i][0], i}); }
int sum = 0; while (!maxHeap.empty()) { const auto& entry = maxHeap.top(); int idx = entry.second; if (maxHeap.size() > n/2) // the equal needs to be on the else here.. { sum += costs[idx][1]; } else // n/2 or smaller items left in the heap { sum += costs[idx][0]; } maxHeap.pop(); }
def twoCitySchedCost(self, arr: List[List[int]]) -> int: arr.sort(key=lambda x:(x[1]-x[0]),reverse=True) n=len(arr) x,y=0,0 for i in range(n//2): x+=arr[i][0]+arr[n-i-1][1] return x
Yes offcourse. I have uploaded my CODE using Dynamic Programming (Memoization) in CODE LINK in the description. Please have a look. It's easy to understand.
java solution : public int twoCitySchedCost(int[][] costs) { Arrays.sort(costs,(a,b) -> { return (a[0]-a[1])-(b[0]-b[1]); }); int n = costs.length; int ans = 0; for(int i=0;i=n/2?costs[i][1]:costs[i][0]; } return ans; }
Thank you for this approach, but I am not able to figure out why just considering one city max profit we will be able to get maximum profit,why we are not taking city B into consideration It will be great if you can explain me how we can expand this problem if we have 3 cities and 3N candidate Solution to this might be simple but its not striking
Use dynamic programming (memoization) to solve for as many N and as many cities as you want. I have uploaded DP CODE LINK in description as well. Please have a look. When there are just 2 cities then it doesn't matter whether you consider A or B, the other one will always get considered. We are doing based on profit of A. This means we segregating all max profit candidates for city A. Therefore, least profit candidates to A gets segregated on the other side. It was also guaranteed that N candidates had to go to A and B both. So, take most profitable half for A and other half for B. It's simple. You will get it.
6:44 is not a good example at all. Nothing guarantees that A of i < B of i in all pairs. The rest is great. It's a bit confusing what happens when the difference is negative.
Yeah, exactly. What if the element [30, 300] was [300, 30] instead? Then even when the list of pairs is sorted by the highest differences of each, B would be cheaper for that first pair. So even after sorting by the biggest difference, you need to check whether A or B is lower, and if either one is already full (you've already used n A's or n B's), then you use the other.
I've written a recursive function to calculate the min cost but I'm not able to memoize my solution class Solution { public int twoCitySchedCost(int[][] costs) { int nTotal=costs.length; return totalCost(costs,nTotal/2,nTotal/2,nTotal); } public int totalCost(int [][]costs,int a,int b,int nT){ if(a==0&&b==0) return 0; else if(a==0&&b>0) return totalCost(costs,a,b-1,nT-1)+costs[nT-1][1]; else if(a>0&&b==0) return totalCost(costs,a-1,b,nT-1)+costs[nT-1][0]; return Math.min(totalCost(costs,a-1,b,nT-1)+costs[nT-1][0],totalCost(costs,a,b-1,nT-1)+costs[nT-1][1]);
@@techdose4u you are awesome, I came accross several youtubers who claim to have mastered DS & Algorithm. But what I think about DS is that no one can master it, but they can only become good at it by practicing. Any way thanks for being honest.
how does our comparator takes into account for vector like [400,50] in [[10,20],[30,200],[400,50],[30,20]] wont doing a[1] - a[0] give a negative value for this in your explanation, you have taken the a[i][1] greater than a[i][0] for all i
(400,50) will have profit as -350. So we are at loss of 350 if we chose to go to city A. So after sorting in your array, (400,50) will come last. So, City B will be chosen for it.
Try that case. I don't know where is the problem. Will sorting won't work for -ve number? If it won't then this technique won't work either. So try to dry run.
I solved this question using Dynamic Programming. Here is my solution. class Solution { public: int twoCitySchedCost(vector& costs) { int n = costs.size(); int dp[200][200];
for (int i = 0; i < 200; i++) { for (int j = 0; j < 200; j++) { dp[i][j] = -1; } }
return solve(costs, n/2, n/2, 0, dp); }
int solve(vector& costs, int a, int b, int i, int dp[][200]) { int cost = 0;
if (a == 0) { int sum = 0; for (; i < costs.size(); i++) { sum += costs[i][1]; }
dp[a][b] = sum; return dp[a][b]; }
if (b == 0) { int sum = 0; for (; i < costs.size(); i++) { sum += costs[i][0]; }
total size array k 2N given hain, N candidates city A m jana hain and N candidates city B ma. Toh sir na 2N ki jagh i think N size suppose karka kia hain, So for N size (N/2) element city A ma jana hain and (N/2) element city B ma.
Could it be solved by dynamic programming ?if yes, please post a video on that one too. Please refer below link for my java solution with iterative approach in order of n^2 time complexity & O(1) space. github.com/master-raccoons/mission-achieve/blob/master/Practice/TwoCitySchedule.java
I like that you've explained the thinking process ("can I use sort?"). Rather than just explaining the solution.
:)
static bool comp(vector &a , vector &b)
{
return (a[0] - a[1]) < (b[0] - b[1]);
}
int twoCitySchedCost(vector& costs) {
sort(costs.begin() , costs.end() , comp);
int n = costs.size();
int ans = 0;
for(int i = 0 ; i < costs.size() / 2 ; i++)
{
ans += costs[i][0] + costs[i+n/2][1];
}
return ans;
}
please try this
amazing best part of explation was explaning why sorting will not work then move to right solution
Thanks :)
Sometimes I feel you only design those questions 😂
Perfect solutions every time !! 🙌
😂
Made the problem very easy to understand.Good explanation. Thanks a lot 👍
Welcome :)
best explaination . You got a subscriber
very clear explanation from the problem to the solution and time/space complexity. Thanks very much !!
Welcome :)
Great explanation
Thanks :)
Excellent explanation, thank you
This questions was tougher than most of the easy problems on LeetCode
Correct :)
There may be good solutions but i am following you because explanation and style of teaching is superb.
Thanks :)
another fantastic video from Tech Dose. I love the comprehensive approach in terms of methods to resolve the problem. You are a rising star 🌟
I really enjoy the way you approach the problem and solve it with different methods. What would be your approach if we want to schedule the same number of candidates for 3 different cities instead? I could only think of using brute force(back tracking) at the moment.
Using backtracking with memoization. This will work for all the cases.
Very Well Explained... Thank You :)
Nice explaination Sir, Lockdown and Leetcode with @Techdose. I saw almost 70./. of your videos your explaination is clear and too the point in all videos. Keep going Sir !!
Thanks :)
Finally it is i was waiting from one hour.
I hope you tried yourself :)
Great job
Thanks :)
Nice Explaination
Thanks :)
Java solution
class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs,(a,b)->(a[0]-a[1])-(b[0]-b[1]));
int len=costs.length;
int res=0;
for(int i=0;i
Thanks for continuously sharing :)
@@techdose4u
First of all ,I want you to thank for the great explanation video then even paid course in the internet
Keep rocking sir 🥳
Your explanation style is very good
Thanks :)
Hey,I think after sorting it is not necessary that we have to take first n/2 from cityA..it can be from CityB also..i think it will be the min(cityA,cityB)..then whoever fills first rest will be from remaining cities filling count.Its while explaining the solution..
Not needed to compare...as here absolute difference is not taken while sorting..so in every case first half will be from A, second half will be from B city.
I already said that we are sorting based on profit we would get if we choose to go to city A. So the first N/2 elements will give max profit for going to city A. According to constraints of the problem, you had to send N/2 candidates to city A. So we needed to choose all first N/2 elements after sorting based on profit. Re-watch the video and listen carefully. I think it's easy to understand. You will get it.
@@techdose4u i think i used diff approach after sorting the profit in desc order
@@uk007rider if you sort in decreasing order. the first half will be for city B and the second half for city A. in your approach you must have taken absolute difference. try to dry run for different input data. you will get why it is working and how it is not working in case of absolute difference
The heap approach will also be O(nlogn) as after every deletion of max from heap balancing the heap everytime will take O(logn) time. The heap won't balance itself in O(1) time.
I wrote O(N) extra space and not time. Time is O(NligN). I think you misunderstood by reading what I wrote for space 😅
@@techdose4u oh sorry my bad😅
@@techdose4u I think creating a new array of profits and sorting that array would also have O(NlogN) time and O(N) space complexity.
I think there seems to be issue with the comparator shouldn't it be
(b[1]-b[0])-(a[1]-a[0]) so that highest difference comes on top.
Nice explanation
Thanks :)
Thanks a ton 🙏 Elegant explanation. Fan of you sir 🤓
Thanks :)
Pls explain how you calculated complexity too
Okay. I try to explain it very briefly.
c++ Heap solution:
// Time complexity: O(NlogN) -> we need to push all the items in the heap
// Space complexity: O(N)
class Solution {
public:
int twoCitySchedCost(vector& costs) {
auto comp = [](pair& lhs, pair& rhs){
return lhs.first > rhs.first;
};
priority_queue maxHeap(comp);
int n = costs.size();
for (int i = 0; i < n; ++i )
{
maxHeap.push({costs[i][1] - costs[i][0], i});
}
int sum = 0;
while (!maxHeap.empty())
{
const auto& entry = maxHeap.top();
int idx = entry.second;
if (maxHeap.size() > n/2)
// the equal needs to be on the else here..
{
sum += costs[idx][1];
} else // n/2 or smaller items left in the heap
{
sum += costs[idx][0];
}
maxHeap.pop();
}
return sum;
}
};
Thanks for your time...
Welcome :)
Good explanation!
Thanks :)
Mad respect !!! Great explanation 👍🏻
Thanks :)
Great explanation. You make the logic so clear to understand. Thank you.
Welcome :)
def twoCitySchedCost(self, arr: List[List[int]]) -> int:
arr.sort(key=lambda x:(x[1]-x[0]),reverse=True)
n=len(arr)
x,y=0,0
for i in range(n//2):
x+=arr[i][0]+arr[n-i-1][1]
return x
Hello, is it also possible to solve it using dynamic programming?
Yes offcourse. I have uploaded my CODE using Dynamic Programming (Memoization) in CODE LINK in the description. Please have a look. It's easy to understand.
How will it solve minimize this cost matrix
10,20. 30,200. 400,50. 30,20
By sort by its diff.
java solution :
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs,(a,b) -> {
return (a[0]-a[1])-(b[0]-b[1]);
});
int n = costs.length;
int ans = 0;
for(int i=0;i=n/2?costs[i][1]:costs[i][0];
}
return ans;
}
Nice
Thanks :)
Thank you for this approach, but I am not able to figure out why just considering one city max profit we will be able to get maximum profit,why we are not taking city B into consideration
It will be great if you can explain me how we can expand this problem if we have 3 cities and 3N candidate
Solution to this might be simple but its not striking
Use dynamic programming (memoization) to solve for as many N and as many cities as you want. I have uploaded DP CODE LINK in description as well. Please have a look. When there are just 2 cities then it doesn't matter whether you consider A or B, the other one will always get considered. We are doing based on profit of A. This means we segregating all max profit candidates for city A. Therefore, least profit candidates to A gets segregated on the other side. It was also guaranteed that N candidates had to go to A and B both. So, take most profitable half for A and other half for B. It's simple. You will get it.
@@techdose4u Thanx , trying to digest :)
Rust:
costs.sort_unstable_by_key(|a| a[0] - a[1]);
let n = costs.len() / 2;
costs.iter().take(n).map(|x| x[0]).sum::() + costs.iter().skip(n).map(|x| x[1]).sum::()
👍
Java Solution - github.com/neeraj11789/tech-interview-problems/blob/33b0cd96a62a9155c0f801dea9e85974522ac11d/src/main/java/leetcode/junechallenge/TwoCityScheduling.java
Excellent explanation sir, thank you so much for such an amazing content ♥
Sir what if in the given example which j used , the pairs are opposite ?...here u r taking A city cost always less than B city cost ...
Since all candidates must go in either city A or B, then taking the opposite will also work
It will work even if A's cost is more. Take some examples and do dry run. You will get it.
y we used static in bool comparator function?
You need to make comparator static. Please read stackoverflow for this question.
6:44 is not a good example at all. Nothing guarantees that A of i < B of i in all pairs. The rest is great. It's a bit confusing what happens when the difference is negative.
Yeah, exactly. What if the element [30, 300] was [300, 30] instead? Then even when the list of pairs is sorted by the highest differences of each, B would be cheaper for that first pair. So even after sorting by the biggest difference, you need to check whether A or B is lower, and if either one is already full (you've already used n A's or n B's), then you use the other.
Well explained sir, thankyou :)
Welcome :)
Can it be done through dp?
It's dp problem only. I have added the new DP code link in the video description. Follow that.
perfect soln :D
I've written a recursive function to calculate the min cost but I'm not able to memoize my solution
class Solution {
public int twoCitySchedCost(int[][] costs) {
int nTotal=costs.length;
return totalCost(costs,nTotal/2,nTotal/2,nTotal);
}
public int totalCost(int [][]costs,int a,int b,int nT){
if(a==0&&b==0)
return 0;
else if(a==0&&b>0)
return totalCost(costs,a,b-1,nT-1)+costs[nT-1][1];
else if(a>0&&b==0)
return totalCost(costs,a-1,b,nT-1)+costs[nT-1][0];
return Math.min(totalCost(costs,a-1,b,nT-1)+costs[nT-1][0],totalCost(costs,a,b-1,nT-1)+costs[nT-1][1]);
}
}
Is it working?
I have added memoization solution to the video in a separate link DP solution. Please read that. It's pretty simple and self explanatory :)
@@mayankprakash9651 yes but it is too slow with exponential time complexity
How you made perfect your DS and algo part?
Nothing is perfect. I am still learning. I just try to improve each passing day. You can do it too with a lot of practice :)
@@techdose4u you are awesome, I came accross several youtubers who claim to have mastered DS & Algorithm.
But what I think about DS is that no one can master it, but they can only become good at it by practicing.
Any way thanks for being honest.
Tq bro waiting for your explanation
My pleasure. I hope you tried your best before looking at solution :)
@@techdose4u yea bro
Why will DP with memoization not work?
Can you make a video with the dp solution ?
I have posted my DP solution. Please have a look. It is nothing but recursion with memoization. Try to write recursive code.
@@techdose4u Didn't get it even after reading the discussions.
Which software you are using to make videos?
Inkspace pro with Wacom pro.
Can we use dp
This is a dp problem. Look at the description for dp solution code.
@@techdose4u ok i got it and it was really very good explaination
Thak you sir. 😊
Welcome :)
Sir please make a video on digit dp
Finally someone asked it :) Have you encountered this on hackerrank contest or on leetcode?
@@techdose4u It was in an Asia Pacific contest
how does our comparator takes into account for vector like [400,50] in [[10,20],[30,200],[400,50],[30,20]]
wont doing a[1] - a[0] give a negative value for this
in your explanation, you have taken the a[i][1] greater than a[i][0] for all i
(400,50) will have profit as -350. So we are at loss of 350 if we chose to go to city A. So after sorting in your array, (400,50) will come last. So, City B will be chosen for it.
What if there is a case where cost for city A is more than city B
Try that case. I don't know where is the problem. Will sorting won't work for -ve number? If it won't then this technique won't work either. So try to dry run.
@@techdose4u sure thank you 🙂
This is a very good explanation i wish i will see many more such types of problem solvings in future
Sir I have doubt in k similar string in leetcode please upload it sir please
If it comes in June challenge then sure otherwise when leetcode challenge ends then I will.
@@techdose4u thanks
How do you manage to keep Leetcoding + TH-cam + Work Full Time? Do you have any tips for me brother?
Just following passion with hard work :)
@@techdose4u I respect you for that man. I'll give my best.
👍
I did it with dp stiill faster than 97%
👍
I thought the parameter was the ratio of costs of both cities.....but it didn't work out
Nice idea though. By trying different parameters you might have been able to reach this profit parameter as well. Keep experimenting.
I solved this question using Dynamic Programming. Here is my solution.
class Solution {
public:
int twoCitySchedCost(vector& costs) {
int n = costs.size();
int dp[200][200];
for (int i = 0; i < 200; i++) {
for (int j = 0; j < 200; j++) {
dp[i][j] = -1;
}
}
return solve(costs, n/2, n/2, 0, dp);
}
int solve(vector& costs, int a, int b, int i, int dp[][200]) {
int cost = 0;
if (a == 0) {
int sum = 0;
for (; i < costs.size(); i++) {
sum += costs[i][1];
}
dp[a][b] = sum;
return dp[a][b];
}
if (b == 0) {
int sum = 0;
for (; i < costs.size(); i++) {
sum += costs[i][0];
}
dp[a][b] = sum;
return dp[a][b];
}
if (dp[a][b] != -1) {
return dp[a][b];
}
cost += min(costs[i][0] + solve(costs, a-1, b, i+1, dp), costs[i][1] + solve(costs, a, b-1, i+1, dp));
dp[a][b] = cost;
return dp[a][b];
}
};
I got same question in curefit interview but I messed it :(
Instead of subracting values we can also add city a cost and city b cost, and after sorting we could find??isn't
I don't think this will work. Share your code if it does.
Sir ji kaise samjaaate pura samajh hi nhi aaaya, top n/ 2 element coty A ke kaise honge...bhai
Please rewatch to get full understanding. I have already explained the reason in video.
total size array k 2N given hain, N candidates city A m jana hain and N candidates city B ma. Toh sir na 2N ki jagh i think N size suppose karka kia hain, So for N size (N/2) element city A ma jana hain and (N/2) element city B ma.
Is this a Greedy approach???
Yes.
Could it be solved by dynamic programming ?if yes, please post a video on that one too.
Please refer below link for my java solution with iterative approach in order of n^2 time complexity & O(1) space.
github.com/master-raccoons/mission-achieve/blob/master/Practice/TwoCitySchedule.java
awesome explanation!!!