O(n^2) Time limit exceed

• The last question:
N<=1000;
Why O(n^2) get TLE

• Could you please paste your code in your post? Without your code others won't be able to troubleshoot the problem for you, thanks.

• ``````class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
vector <unordered_map <long long , int>> ans;

// cout<<A.size()<<endl;
long long num = 0;
int n = A.size();

if(n == 0) return 0;

unordered_map <long long , int> tmp_ans;

for(int i = 0 ; i < n ; i++){
if(tmp_ans.find(A[i]) == tmp_ans.end()){
tmp_ans[A[i]] = 1;
}else
tmp_ans[A[i]] ++;
}

// calculate duplicate numbers
for(auto i : tmp_ans){
long long x = i.second;
if(x >= 3){

if(x % 2 == 0)
num += (long long)pow(2.0 , (double) x) - 1 -   x / 2 * (x - 1) - x;
else
num += (long long)pow(2.0 , (double) x) - 1 -   (x - 1) / 2 * x - x;

}
}

for(int i = 0 ; i < n ; i++){
// keep a hashmap with the key to be the distance between two numbers and value to be the number of elements
unordered_map <long long , int> tmp;
for(int j  = 0 ; j < i ; j++){
long long dis = (long long)A[i] - (long long)A[j];

if(dis == 0)
continue;

if(ans[j].find(dis) == ans[j].end()){
if(tmp.find(dis) == tmp.end())
tmp[dis] = 2;
else
tmp[dis]++;
}else{
num += (ans[j][dis] - 1);
if(tmp.find(dis) == tmp.end())
tmp[dis] = ans[j][dis] + 1;
else
tmp[dis] += ans[j][dis];
}
}

ans.push_back(tmp);

}

return num;
}
};
``````

Hi , I think my solution is O(n^2) , I used only two loops.
And it got a TLE when n = 1000.
Could you help me figure out why it is TLE?

• This python solution got accepted:

```class Solution(object):
def numberOfArithmeticSlices(self, A):
ans = 0;
dp = [{} for i in xrange(len(A))]
for i in xrange(1, len(A)):
for j in xrange(0, i):
dist = A[i] - A[j]
s = dp[j].get(dist, 0) + 1
dp[i][dist] = dp[i].get(dist, 0) + s
ans += s
ans -= i
return ans;
```

but almost identical solution in c++ got MLE/TLE:

```class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ans = 0;
vector<unordered_map<long long, int>> dp(A.size());
for (int i = 1; i < A.size(); i++) {
for (int j = 0; j < i; j++) {
long long dist = (long long)A[i] - A[j];
auto it = dp[j].find(dist);
int s = (it == dp[j].end() ? 0 : it->second) + 1;
dp[i][dist] += s;
ans += s;
}
ans -= i;
}
return ans;
}
};
```

• ``````typedef long long LL;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
if(n<3) return 0;
vector<unordered_map<LL,LL> > dp(n);
vector<unordered_map<LL,LL> > par(n);
unordered_map<LL,LL> ct;
LL count = 0;
for(int i=0;i<n;i++){
ct[A[i]]++;
for(int j=0;j<i;j++){
LL diff = (LL)A[i]-(LL)A[j];
if(diff == 0){
continue;
}
par[i][diff] += 1;
dp[i][diff] += dp[j][diff] + par[j][diff];
count += dp[j][diff]+par[j][diff];
}
}
for(auto pr:ct) if(pr.second>2){
LL k = pr.second;
count += (1LL<<k) - 1 - k - k*(k-1)/2;
}
return count;
}
};
``````

Sry, forgot to post my code.
I only used 2 loops, and it is definitely O(n^2), but got TLE

• My JavaScript solution gets MLE. And it is basically the same as nehcdnr's solution.

``````var numberOfArithmeticSlices = function (A) {
let res = 0;
const dp = Array(A.length).fill(0).map(() => new Map());

for (let i = 0; i < A.length; i++) {
for (let j = 0; j < i; j++) {
const diff = A[i] - A[j];

let count = 1;
if (dp[j].has(diff)) {
count += dp[j].get(diff);
res += dp[j].get(diff);
}

dp[i].set(diff, (dp[i].get(diff) || 0) + count);
}
}

return res;
};
``````

• This post is deleted!

• @pumpkingg Can you explain the logic?

• @pumpkingg I have a question regarding your python code. Why we need ans -= i? Could you please explain this line of code?

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