1

I have a sqaure matrix and a smaller square which moves inside the matrix at all possible positions (does not go out of the matrix). I need to find the smallest number in all such possible overlappings.

The problem is that the sizes of both can go upto thousands. Any fast way to do that?

I know one way - if there's an array instead of a matrix and a window instead of a square, we can do that in linear time using a deque.

Thanks in advance.

EDIT: Examples

Matrix:

1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
8 0 9 0 5

For a square of size 3, total 9 overlappings are possible. For each overlapping the minimum numbers in matrix form are:

1 1 1
2 1 1
0 0 0
Bruce
  • 945
  • 3
  • 12
  • 24
  • Sounds like you want to perform 2d correlation. Depends on the language and libraries you are using but there are efficient methods: e.g. http://stackoverflow.com/questions/1100100/fft-based-2d-convolution-and-correlation-in-python – YXD Apr 12 '13 at 10:17
  • @MrE Yes, it is similar to correlation but its not - correlation is a linear spacial filter, but this is non-linear. Plus I can't use any libraries. – Bruce Apr 12 '13 at 10:22
  • What is "the smallest number in all such possible overlappings"? – ypnos Apr 12 '13 at 10:25
  • What @ypnos said - what is the operation then? Can you show us a toy example of input and output? – YXD Apr 12 '13 at 10:29
  • @ypnos Updated, please look. – Bruce Apr 12 '13 at 10:43
  • Do you just need to return 0 in your example or the whole 3x3 array? If the array, your example solves "find the smallest number in each possible overlap" (reduced ambiguity). If just 0 (or the applicable square), you can just look for the lowest number in the entire array, in O(n^2). – Bernhard Barker Apr 12 '13 at 12:19

1 Answers1

1

It is possible in O(k * n^2) with your deque idea:

If your smaller square is k x k, iterate the first row of elements from 1 to k in your matrix and treat it as an array by precomputing the minimum of the elements from 1 to k, from 2 to k + 1 etc in each column of the matrix (this precomputation will take O(k * n^2)). This is what your first row will be:

*********
1 3 6 2 5
8 2 3 4 5
3 8 6 1 5
*********
7 4 8 2 1
8 0 9 0 5

The precomputation I mentioned will give you the minimum in each of its columns, so you will have reduced the problem to your 1d array problem.

Then continue with the row of elements from 2 to k + 1:

1 3 6 2 5
*********
8 2 3 4 5
3 8 6 1 5
7 4 8 2 1
*********
8 0 9 0 5

There will be O(n) rows and you will be able to solve each one in O(n) because our precomputation allows us to reduce them to basic arrays.

IVlad
  • 43,099
  • 13
  • 111
  • 179