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 !!
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.
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
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.
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
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(); }
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.
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.
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; }
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.
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]; }
@@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.
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]);
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.
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
![30 ชั่วโมงคนเดียว บนรถไฟชั้น 3 โซเวียต [Around The World Ep. 2]](http://i.ytimg.com/vi/MlE9boAVqDA/mqdefault.jpg)
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 :)
There may be good solutions but i am following you because explanation and style of teaching is superb.
Thanks :)
very clear explanation from the problem to the solution and time/space complexity. Thanks very much !!
Welcome :)
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 :)
best explaination . You got a subscriber
another fantastic video from Tech Dose. I love the comprehensive approach in terms of methods to resolve the problem. You are a rising star 🌟
Great explanation. You make the logic so clear to understand. Thank you.
Welcome :)
This questions was tougher than most of the easy problems on LeetCode
Correct :)
Your explanation style is very good
Thanks :)
Very Well Explained... Thank You :)
Excellent explanation, thank you
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.
Thanks a ton 🙏 Elegant explanation. Fan of you sir 🤓
Thanks :)
Excellent explanation sir, thank you so much for such an amazing content ♥
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 🥳
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
Finally it is i was waiting from one hour.
I hope you tried yourself :)
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.
Great explanation
Thanks :)
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.
Pls explain how you calculated complexity too
Okay. I try to explain it very briefly.
Nice Explaination
Thanks :)
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
Great job
Thanks :)
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;
}
};
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::()
👍
Mad respect !!! Great explanation 👍🏻
Thanks :)
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.
Nice explanation
Thanks :)
Good explanation!
Thanks :)
Thanks for your time...
Welcome :)
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 :)
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;
}
Well explained sir, thankyou :)
Welcome :)
Nice
Thanks :)
Java Solution - github.com/neeraj11789/tech-interview-problems/blob/33b0cd96a62a9155c0f801dea9e85974522ac11d/src/main/java/leetcode/junechallenge/TwoCityScheduling.java
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
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.
Tq bro waiting for your explanation
My pleasure. I hope you tried your best before looking at solution :)
@@techdose4u yea bro
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.
How will it solve minimize this cost matrix
10,20. 30,200. 400,50. 30,20
By sort by its diff.
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.
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];
}
};
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.
perfect soln :D
Which software you are using to make videos?
Inkspace pro with Wacom pro.
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
Why will DP with memoization not work?
I did it with dp stiill faster than 97%
👍
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.
Thak you sir. 😊
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.
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 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.
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
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.
I got same question in curefit interview but I messed it :(
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.
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
Is this a Greedy approach???
Yes.
awesome explanation!!!