[FIXED] Why my code is giving Time Limit Exceeded?

Issue

Today while solving a question on leetcode, I applied dfs on a directed graph which runs on O(N) time, but my code is giving TLE, so after trying too many time I checked on comments and there was a accepted code which also runs on O(N). So now I am confused as why my code is not getting accepted and giving time limit exceeded. My code:-

public:
    int ans=INT_MIN;
    vector<vector<int>> gr;
    void dfs(int head, int time, vector<int> inform){
        if(gr[head].size()==0) {ans=max(ans,time);return;}
        for(auto next:gr[head]){
            dfs(next, inform[head]+time, inform);
        }
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        gr.resize(n);
        for(int i=0 ; i<n ; i++){
            if(manager[i]!=-1) gr[manager[i]].push_back(i);
        }
        dfs(headID,0, informTime);
        return ans;
    }

One of accepted code:-

    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int res = 0;
        for (int i = 0; i < n; ++i)
            res = max(res, dfs(i, manager, informTime));
        return res;
    }

    int dfs(int i, vector<int>& manager, vector<int>& informTime) {
        if (manager[i] != -1) {
            informTime[i] += dfs(manager[i], manager, informTime);
            manager[i] = -1;
        }
        return informTime[i];
    }

If anyone needs question link:- https://leetcode.com/problems/time-needed-to-inform-all-employees/

Solution

In your dfs() function, you pass inform by value, which means the compiler makes a copy of inform every time you call the function, not the inform itself.

You should pass by reference instead.

void dfs(int head, int time, vector<int> &inform)

Answered By - justANewb stands with Ukraine

Answer Checked By - Mildred Charles (PHPFixing Admin)