Find all possible distances from two arrays

Question

Given two sorted array A and B length N. Each elements may contain natural number less than M. Determine all possible distances for all combinations elements A and B. In this case, if A[i] - B[j] < 0, then the distance is M + (A[i] - B[j]).

Example :

A = {0,2,3}
B = {1,2}
M = 5

Distances = {0,1,2,3,4}

Note: I know O(N^2) solution, but I need faster solution than O(N^2) and O(N x M).

Edit: Array A, B, and Distances contain distinct elements.

Answer 1

You can get a O(MlogM) complexity solution in the following way.

1. Prepare an array Ax of length M with Ax[i] = 1 if i belongs to A (and 0 otherwise)
2. Prepare an array Bx of length M with Bx[M-1-i] = 1 if i belongs to B (and 0 otherwise)
3. Use the Fast Fourier Transform to convolve these 2 sequences together
4. Inspect the output array, non-zero values correspond to possible distances

Note that the FFT is normally done with floating point numbers, so in step 4 you probably want to test if the output is greater than 0.5 to avoid potential rounding noise issues.