better algorithm for checking 5 in a row/col in a matrix

Question

is there a good algorithm for checking whether there are 5 same elements in a row or a column or diagonally given a square matrix, say 6x6?

there is ofcourse the naive algorithm of iterating through every spot and then for each point in the matrix, iterate through that row, col and then the diagonal. I am wondering if there is a better way of doing it.

Answer 1

You could keep a histogram in a dictionary (mapping element type -> int). And then you iterate over your row or column or diagonal, and increment histogram[element], and either check at the end to see if you have any 5s in the histogram, or if you can allow more than 5 copies, you can just stop once you've reached 5 for any element.

Simple, one-dimensional, example:

m = ['A', 'A', 'A', 'A', 'B', 'A']

h = {}
for x in m:
    if x in h:
        h[x] += 1
    else:
        h[x] = 1

print "Histogram:", h

for k in h:
    if h[k]>=5:
        print "%s appears %d times." % (k,h[k])

Output:

Histogram: {'A': 5, 'B': 1}
A appears 5 times.

Essentially, h[x] will store the number of times the element x appears in the array (in your case, this will be the current row, or column or diagonal). The elements don't have to appear consecutively, but the counts would be reset each time you start considering a new row/column/diagonal.

Answer 2

You can check whether there are k same elements in a matrix of integers in a single pass.

Suppose that n is the size of the matrix and m is the largest element. We have n column, n row and 1 diagonal. Foreach column, row or diagonal we have at most n distinct element.

Now we can create a histogram containing (n + n + 1) * (2 * m + 1) element. Representing the rows, columns and the diagonal each of them containing at most n distinct element.

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

Now the tricky part is how to update this histogram ?

Consider this function in pseudo-code:

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

Now all you have to do is to iterate throw the histogram and check whether there is an element > k