First, if you simply compare all the pairs, you will need to compute all the difference of \(NM\) pairs. Under the constraints this time, it requires \(4\times 10^{10}\) number of calculations, which does not finish in the time limit.

Instead, we first sort the two arrays. Generally, if the order of a given sequence or set does not matter, making it monotonic by sorting it may sometimes make the problem easier to solve. We can almost always sort as large sequence as given, and if the problem is solvable then the problem for the sorted array should be also solvable, so there are no disadvantages in considering such cases.

Now, we suppose that the array has been sorted. That is, we assume that \(A_1\leq A_2\cdots \leq A_N\) and \(B_1\leq B_2\cdots \leq B_M\). Then for each \(i=1,2,\ldots,N\), in this order, we will find such \(j\) that minimizes \(\lvert A_i-B_j\rvert\). If \(A_i\leq B_j\) then for any \(j< j'\), \(\lvert A_i-B_j\rvert=B_j-A_i\leq B_{j'}-A_i=\lvert A_i-B_{j'}\rvert\), so we do not have to check any \(j'\) greater than \(j\). It looks like we have reduced the number more or less, but if \(A_i>B_N\), then we have to inspect every pair, so it is not enough. Here, the point is that the converse is also useful. That is, if \(B_j\leq A_i<B_{j+1}\), then for each \(j'\leq j\), \(\lvert A_{i+1}-B_{j'} \rvert=A_{i+1}-B_{j'}\geq A_{i+1}-B_{j}\geq A_i-B_j=\lvert A_i-B_j\rvert\), so we do not have to inspect it.

Overall, we can find the answer by repeating the following steps, starting from \(A_1\) and \(B_1\):

• If the value \(\lvert A_i-B_j\rvert\) is less than the minimum difference so far, then update the preliminary answer.
• Then, compare \(A_i\) and \(B_j\).
• If \(A_i> B_j\), then update \(B_j\) to \(B_{j+1}\) and continue the next iteration.
• If \(A_i\leq B_j\), then we do not have to compute \(\lvert A_{i}-B_{j'}\rvert\) for any \(j'\) such that \(j<j'\). Moreover, also for \(A_{i+1}\), we do not have to compute \(\lvert A_{i+1}-B_{j'}\rvert\) for any \(j'\) such that \(j'<j\), so we go on to the next iteration with \(A_{i+1}\) and \(B_j\).
• If \(i>N\) and \(j>M\), terminate the operations.

Now let us consider the complexity of the steps above. In every step, the value \(i+j\) increases by \(1\) each, so the number of iterations is at most \(N+M-1\). Since each operation can be done in a total of \(O(1)\) time, this part can be done in a total of \(O(N+M)\) time, so together with the initial sort, the original problem has been solved in a total of \(O(N\log N+M\log M)\) time.

Sample code in C++:

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

#define N 200010
#define INF 1010000000
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n, m;
	int a[N];
	int b[N];
	int ans = INF;
	cin >> n >> m;
	rep(i, n)cin >> a[i];
	rep(i, m)cin >> b[i];
	sort(a, a + n);
	sort(b, b + m);
	int x = 0;
	int y = 0;
	while ((x < n) && (y < m)) {
		ans = min(ans, abs(a[x] - b[y]));
		if (a[x] > b[y])y++;
		else x++;
	}
	cout << ans << endl;

	return 0;
}