TLE -Why does leetcode not accept DFS solutions [C++]
demelos
61

I have this question lingering on my mind from quite some time now. Why leetcode does not accept DFS solutions. In general I get many TLEs for 'hard' problems if I use DFS. I was able to solve below problem in 10 mins. Am I going to fail a FAANG interview if I do it this way.?
@Leetcode community and my expert friends @FAANG - I need your honest opinion. Isnt it good enough to quickly solve a problem in your natural way of thinking and then try for DP solution to cut the bar. ?

https://leetcode.com/problems/triangle/

class Solution {
public:
    void minTotalUtil(vector<vector<int>>& triangle, int h, int j, int runningSum, int& minSum) {
        if(h == triangle.size()) {
            minSum = min(minSum, runningSum);
            return;
        }
           
        
        minTotalUtil(triangle, h+1, j, runningSum+triangle[h][j], minSum);
        minTotalUtil(triangle, h+1, j+1, runningSum+triangle[h][j], minSum);
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        int minSum = INT_MAX;
        minTotalUtil(triangle, 0, 0, 0, minSum);
        
        cout << minSum << endl;
        return minSum;
        
    }
};
Comments (1)