hi, bro your 2nd approach is still having space complexity of O(M+N). M=recursive call stack and N=indegree vector in each call to validate our answer. (Here, M=requests.size() and N= unique buildings)
In the first approach, if we take do not approve the request at first and then take the approved request, why is this method not working? Can anyone tell me the reason for this?
It will work only if you update vector to original state See, try this way // Ignore this request and move on to the next request without incrementing the count. maxRequest(requests, indegree, n, index + 1, count); // Consider this request, increment and decrement for the buildings involved. indegree[requests[index][0]]--; indegree[requests[index][1]]++; // Move on to the next request and also increment the count of requests. maxRequest(requests, indegree, n, index + 1, count + 1); // Backtrack to the previous values to move back to the original state before the second recursion. indegree[requests[index][0]]++; indegree[requests[index][1]]--; This is because to backtrack, we need original vector, and not the updated one.
I encountered the same problem ... it's because in his code ...he has declared indegree vector publicly...so after returning from 1 call it will still have previous value...to make it work you have to call compensatory part in the end explicitly.....else u can declare indegree vector in function and pass it as argument and then i suppose what u were trying to do..would work...i.e first calling not take part and then calling take part.
approach1: class Solution { int ans = INT_MIN; public: void solve(int n, vector& req, vector &blocks, int ind, int count){ if(ind==req.size()){ for(int i=0; i
you have really good communication skills keep going
Thank you! 😃
hi, bro your 2nd approach is still having space complexity of O(M+N). M=recursive call stack and N=indegree vector in each call to validate our answer. (Here, M=requests.size() and N= unique buildings)
yes he said the time complexity will remain same
@@I_Keshav_Prajapati I'm talking about space complexity...time complexity is same in both the approaches.
Hello sir. Please make a video on yesterday's challenge. It would be of great help!
In the first approach, if we take do not approve the request at first and then take the approved request, why is this method not working? Can anyone tell me the reason for this?
It will work only if you update vector to original state
See, try this way
// Ignore this request and move on to the next request without incrementing the count.
maxRequest(requests, indegree, n, index + 1, count);
// Consider this request, increment and decrement for the buildings involved.
indegree[requests[index][0]]--;
indegree[requests[index][1]]++;
// Move on to the next request and also increment the count of requests.
maxRequest(requests, indegree, n, index + 1, count + 1);
// Backtrack to the previous values to move back to the original state before the second recursion.
indegree[requests[index][0]]++;
indegree[requests[index][1]]--;
This is because to backtrack, we need original vector, and not the updated one.
I encountered the same problem ... it's because in his code ...he has declared indegree vector publicly...so after returning from 1 call it will still have previous value...to make it work you have to call compensatory part in the end explicitly.....else u can declare indegree vector in function and pass it as argument and then i suppose what u were trying to do..would work...i.e first calling not take part and then calling take part.
approach1:
class Solution {
int ans = INT_MIN;
public:
void solve(int n, vector& req, vector &blocks, int ind, int count){
if(ind==req.size()){
for(int i=0; i