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

general
,
1

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

2

Should these both be the same size?

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

3

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