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

• 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);
}
};``````

• 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.

• I am using DP already.

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