For explanation purposes, let \(A,B\) be \(0\)-indexed.

By setting \(A_i = -A_i \bmod M\), we can rephrase this as a problem of minimizing \(\max_{0 \le i \lt N}((B_i-A_i) \bmod M)\).

Since the original order of \(A,B\) does not affect the answer, we sort \(A,B\) in ascending order beforehand.

\(O(N \log N + N \log M)\) Solution

To conclude, the answer is \(\min_{0 \le j \lt N}(\max_{0 \le i \lt N}((B_i-A_{i+j \bmod N}) \bmod M))\). (In other words, we only need to consider cyclic shifts for rearranging \(A\).) For the proof of this fact, refer to the \(O(N \log N)\) solution section.

If we binary search on the answer \(X\), we need to determine whether there exists a \(j\) such that \((B_i-A_{i+j \bmod N}) \bmod M \le X\) for all \(i\). Focusing on each \(B_i\), the set of possible values for \(j\) forms an interval on a circle. In other words, we need to find whether there exists a common intersection among those \(N\) intervals on the circle, which can be computed in \(O(N)\) using techniques like cumulative sums. Also, the part of finding intervals for each \(i\) can be computed in \(O(N)\) overall using the two-pointer technique. The total time complexity is \(O(N \log N + N \log M)\).

\(O(N \log N)\) Solution

\((B_i-A_i) \bmod M\) equals \(B_i-A_i\) when \(A_i \le B_i\), and \(B_i-(A_i-M)\) when \(A_i \gt B_i\).

Based on this, we can see that determining whether the answer is at most \(X\, (X \lt M)\) can be computed through the following procedure:

1. Subtract \(M\) from any \(0\) or more elements of \(A\)
2. Then, determine whether we can rearrange \(B\) such that \(A_i \le B_i \le A_i+X\) holds for all \(i\)

Step 2. is a problem where we have \(N\) intervals of equal length and \(N\) points on a number line, and we want to match intervals and points such that each point lies within its matched interval. It’s clear that matching in ascending order of \(A,B\) is optimal.

Also, when we fix the number \(k\) of elements in \(A\) from which we subtract \(M\), it’s optimal to choose the \(k\) largest elements of \(A_i\) in descending order and subtract \(M\) from them. Note that since \(B_i\) is contained in \([0,M)\), we can take the intersection of each interval \([A_i,A_i+X]\) with \([0,M)\), and it can be shown that this choice is strictly better than other choices.

Based on this, we can further rephrase that the answer is the minimum value obtained through the following procedure:

1. Let \(B'_0, B'_1, \dots , B'_{2N-1}\) be \(B_0, B_1, \dots , B_{N-1}, B_0+M, B_1+M, \dots, B_{N-1}+M\)
2. Choose \(k\) such that \(0 \le k \le N\) and \(A_i \le B'_{i+k}\) holds for all \(i\)
3. Find \(\max_{0 \le i \lt N}(B'_{i+k}-A_i)\)

Since the value computed in step 3. is monotonically increasing with respect to \(k\), it’s optimal to choose the smallest \(k\) that satisfies the condition in step 2.. By binary searching on \(k\), we can find the answer in \(O(N \log N)\). (Code)