What is the Time-Complexity of following code? Given array is permutation of (1 to n).
Difference between en1 and en2, changed 40 character(s)
#include <bits/stdc++.h>↵
using namespace std;↵
typedef vector<int> vi;↵
void solve()↵
{↵
int n; cin>>n;↵
vi v(n); ↵
        for(int i=0;i<n;i++)cin>>v[i];↵
↵
vi ans(n+1,0);↵
↵
for(int i=0;i<n;i++)↵
{↵
ans[i] = 1e9;↵
for(int j=i-1;j>=0;j--)↵
{↵
if(ans[i]<i-j)↵
break;↵
↵
ans[i] = min(ans[i],abs(v[i]-v[j])+(abs(i-j)));↵
}↵
↵
for(int j=i+1;j<n;j++)↵
{↵
if(ans[i] < j-i)↵
{↵
break;↵
}↵
↵
ans[i] = min(ans[i],abs(v[i]-v[j])+abs(i-j));↵
}↵
↵
cout<<ans[i]<<" ";↵
}↵
 }↵
signed main()↵
{↵
int T;↵
T=1;↵
cin>>T;↵
while(T--)↵
{↵
solve();↵
}↵
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English CodeKar 2022-12-25 10:36:07 40
en1 English CodeKar 2022-12-25 10:34:59 658 The given code is working for 2<=N<=2e5. According to me it should be O(n^2) but it passed the given constraint. Given that v is permutation of (1 to n). (published)