Given two arrays A and B, of length N and length k respectively, if we move B over A and take the sum of product of corresponding elements of A and B, then find the minimum of those sum of products.

For example, if A=[2,3,4,5] and B=[1,3], then after moving B over A, we get 3 possible values [2*1+3*3, 3*1+4*3, 4*1+3*5], max of which is 19.

I tried coding for this and reached an \$O(n^2)\$ solution. Can I reduce the algorithm's complexity here?

My code in Python:

print max([sum([A[i+j]*B[j] for j in xrange(len(B))]) for i in xrange(len(A)-len(B)+1)])

This is effectively a convolution problem. Theoretically, this can (potentially) be done faster by a conversion to the frequency domain, that is, using a fast Fourier transform (FFT) convolution.

Writing a high-performance FFT convolution isn't something I'd want to reproduce here (even if I could reproduce it, which to be perfectly honest, I couldn't). Thankfully, I don't have to: libraries like numpy and scipy provide this functionality: see scipy.signal.fftconvolve.

The only thing that we have to be careful with is that convolution reverses the second array, so we must provide that in a reversed form:

import numpy
from scipy.signal import fftconvolve

x = numpy.array([2,3,4,5])
y = numpy.array([1,3])
maximum = numpy.max(fftconvolve(x, y[::-1], mode='valid')) # reversed view of y

For small arrays, this is likely to be slower than the naïve O(n2) convolution, due to the overhead of conversions (and multiplying complex numbers). If you are in this case, then you should try scipy.signal.convolve.

For an in-depth writeup of computational complexity comparisons between the naïve convolution and the fast Fourier transform, see here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.