# Why my code is giving TLE in some cases ? (see description)

link to the question (CSES - Apartments)

My solution

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n, m, k;
cin >> n >> m >> k;

int person[n];
int apaSize[m];
for(int i = 0; i < n; i++) cin >> person[i];
for(int i = 0; i < m; i++) cin >> apaSize[i];

sort(person, person + n);
sort(apaSize, apaSize + m);

int counter = 0;
int j = 0;
int idx = 0;;

for(int i = 0; i < n; i++)
{
idx = lower_bound(apaSize + idx, apaSize + m, person[i] - k) - (apaSize);
for(j = idx; j < m; j++)
{
if((apaSize[j] >= (person[i] - k)) && ((apaSize[j] <= (person[i] + k))))
{
counter++;
idx = j+1;
break;
}
}
}

cout << counter << endl;

return 0;
}
``````

Other accepted solution

``````#include <bits/stdc++.h>

using namespace std;

//constant initialization
const int maxn=2e5+10;

//variables used for the current problem
int n,m,k,a[maxn],b[maxn],ans;

void solve() {
cin >> n >> m >> k;
for (int i=0;i<n;++i) cin >> a[i];
for (int i=0;i<m;++i) cin >> b[i];
sort(a,a+n); sort(b,b+m);
int i=0,j=0;
while (i<n && j<m){
if (abs(a[i]-b[j])<=k){ //Found a suitable apartment for the applicant
++i; ++j; //Move to the next one.
++ans;
}
else{
if (a[i]-b[j]>k){
//If the desired apartment size of the applicant is too big
//Move the "apartment" pointer to the right to find a bigger one
++j;
}
else{
//If the desired apartment size is too small
//Skip that applicant and move to the next person
++i;
}
}
}
cout << ans << "\n";
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
``````

Time complexity of my code is O(n^2) and if I am not wrong the time complexity of other accepted solution is also O(n^2) even when there is one while loop because in worst case the while loop will run n * m times.

So my question is, The complexity of the accepted solution is similar to mine, so why my code is not giving runtime error is 3 cases.
CSES - Apartments

Should these both be the same size?

Looks more like O(n + m) (excluding the sorting) to me.

Oh! I see, it’s really O(n+m) because, in each iteration of the while loop, either i, j or both will get incremented. so the complexity will be O(n+m).

Thanks.

1 Like