Find the Largest Square Submatrix in a NxM Matrix

Some time ago a bright intern we had came up with a really interesting brain teaser he was asked during one of the interview he made to get an internship.
The problem is this:

having as input a random generated matrix N x M whose elements are integers with values {1,2,....,9}, you are asked to find the biggest square made of he same digits.
In the case there are multiple equally big squares, just pick up the first one.

Since it is and interesting brain teaser and I'm currently experimenting a bit with Dynamic Programming I came up with this solution:

Let's define T(i,j) as the side's length of the biggest square which is possible to build having those characteristic and having the cell (i,j) as bottom right element, then:

if

• (i,j) == (i-1,j-1) and
• the previous T(i-1,j-1) elements in the same column have the same value as (i,j) and
• the previous T(i-1,j-1) elements in the same row have the same value as (i,j)

then

• T(i,j) = T(i-1,j-1) +1

else

• T(i,j) = 1 since we can't expand the previous square and we have to start building another one instead

so basically if the matrix is:

5,5,6
5,5,5
5,5,5

the respective T(i,j) values when considering the cell (3,3) would be

1,1,1
1,2,1
1,1,X

being X what we want to find out.
So our if else will in turn compare the element (i,j) marked in green with the elements marked in red stopping when one of the checks fails or, if they all pass, updating the value to T(i-1,j-1) +1:

5,5,6
5,5,5
5,5,5

5,5,6
5,5,5
5,5,5

5,5,6
5,5,5
5,5,5

which in this case will fail at the second test causing: X = 1.
If the matrix would have been made of all of 5 then: X = T(i-1,j-1) + 1 = 2 + 1 = 3

Here comes the code:

void findMaxSquare(const unsigned int* aMatrix,

const unsigned int aNumRows, const unsigned int aNumColumns) {



unsigned int *result = (unsigned int*) malloc(sizeof(unsigned int) * aNumColumns * aNumRows);

int i,j;

// set the first row to 1 (it's the biggest square those cells can build)

for(i = 0; i < aNumColumns; ++i) {

result[i] = 1;

}

// set the first column to 1 (it's the biggest square those cells can build)

for(i = 1; i < aNumRows; ++i) {

*(result + i*aNumColumns) = 1;

}

unsigned int maxSquareSide = 1; // store the side of the biggest square we can build

unsigned int maxXIndex = 0; // and its row

unsigned int maxYIndex = 0; // and its column



for(i = 1; i < aNumRows; ++i) {

for(j = 1; j < aNumColumns; ++j) {

// check whether the current item is the same as the previous one

// if so, the previous element aMatrix[i-1][j-1] build a square of side result[i-1][j-1]

// so check whether the same value aMatrix[i][j] is repeated in column j result[i-1][j-1] times.

// if so, check whether the same value aMatrix[i][j] is repeated in row i result[i-1][j-1] times.

if( (aMatrix + i*aNumColumns)[j] == (aMatrix + (i-1)*aNumColumns)[j-1] &&

isColumnTheSame(aMatrix, aNumColumns, i, j, (result + (i-1)*aNumColumns)[j-1]) &&

isRowTheSame(aMatrix, aNumColumns, i, j, (result + (i-1)*aNumColumns)[j-1])) {

// if we get here, this item enlarges of 1 cell

// the square having as bottom right aMatrix[i-1][j-1]

(result + i*aNumColumns)[j] = (result + (i-1)*aNumColumns)[j-1] + 1;



//store the value and relative indexes if it's the biggest square found found so far

if(maxSquareSide < (result + i*aNumColumns)[j]) {

maxSquareSide = (result + i*aNumColumns)[j];

maxXIndex = i;

maxYIndex = j;

}

continue;

}

// this is the begininning of a new square

(result + i*aNumColumns)[j] = 1;

}

}



printf("the maximum square is made of '%d', is %3d digits wide and has top left ( %3d , %3d )\n",

(aMatrix+(maxXIndex-(maxSquareSide - 1))*aNumColumns)[maxYIndex - (maxSquareSide - 1)],

maxSquareSide,

maxXIndex - (maxSquareSide - 1) + 1,

maxYIndex - (maxSquareSide - 1) + 1);

free(result);

}

This algorithm can be still be improved:

1. if the input matrix is not a squared but n >>m or m>>n the first for loop instead of iterating through all the rows should iterate through max{n,m}
2. once found a square made of the same integers we should check whether is possible to build a bigger one, if not stop the procedure

about the complexity I believe it's a O(n*m*(n+m)/4) so for n=m O(n^3)

God Bless Peripheral Vision

Just saved my macbook pro from falling from the armrest of my sofa (yeah, I shouldn't have put it there in the first place, I know).
While I was reading a book something was bothering me, at the last (milli)second I realised it was my macbook that was slowly sliding out of the armrest.
Saved it when it had just begun the free fall.
God bless peripheral vision...that and my feline reaction time.