Why my O(N^2) solution is getting Time Limit exceeded ?


  • 0
    A

    My solution complexity is O(N^2) and I am getting TLE, what is wrong?

    Note: I know I can reduce the memory to O(N) but that isn't the problem now.

    class Solution {
    public:
        vector <vector <int> > dp;
        vector <pair<int,int>> vec;
        int s;
        int solve(int curInd,int maxInd)
        {
            if(curInd==s)
                return 0;
            if(dp[curInd][maxInd]!=-1)
                return dp[curInd][maxInd];
            int ret= solve(curInd+1,maxInd);
            if(vec[curInd].first > vec[maxInd].first && vec[curInd].second > vec[maxInd].second)
                ret=max(ret, solve(curInd+1,curInd)+1);
            return dp[curInd][maxInd]=ret;
        }
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            vec=envelopes;
            vec.push_back(make_pair(-1,-1));
            s=vec.size();
            sort(vec.begin(),vec.end());
            dp= vector<vector<int>> (s, vector<int>(s,-1));
            return solve(1,0);
        }
    };

  • 0

    Use DP to avoid duplicated recursion.

    update: O(n^2) solution is still too slow. It can be solved by an O(nlogn) solution. Check LIS problem.


  • 0
    A

    I am using DP already.

    To be specific I'm using recursion+memoization which have the same time complexity.


  • 0

    See updated answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.