Matrix largest product of n numbers in a row

Question

Hello I'm having trouble with a little program I am trying to write. The problem is if I'm given any matrix size (lets just say a 4x4 for this example), find the largest product of n numbers in a row (lets say n = 3). The 3 numbers in a row can be horizontal, vertical, or diagonal. So heres a matrix:

1 1 2 5
1 5 2 4
1 7 2 3
1 8 2 1

If n was equal to 3 then my largest product would be 280 (5*7*8). Now I have my matrix loaded into a 2D vector. I'm not too picky on how the program works(brute force is fine), so far I know I'm going to have to have at least two nested for loops to go through each staring location of the matrix but I haven't been successful in finding the current answer. Any advice will help, thank you.

Answer 1

Version to find max product in rows using rolling multiplication to save some resources. This rolling procedure means that we don't have to multiply n values to find each product of these n values, but instead we have to just do one multiplication and one division:

if (currN == N) { // compute full product first time
    while (currn) {
         product *= (*it3++);
          --currn;
    }
 } else {          // rolling computation
     product *= (*(it3 + n - 1)) / (*(it3 - 1));
     it3 += n;
 }

It is up to you to complete this to handle also columns:

populate matrix:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;

typedef vector< vector< int> > Matrix;
typedef Matrix::iterator outIt;
typedef vector< int>::iterator inIt;

void fillMatrix( Matrix& matrix) {
    outIt it = matrix.begin();
    (*it).push_back( 1);
    (*it).push_back( 1);
    (*it).push_back( 2);
    (*it).push_back( 5);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 5);
    (*it).push_back( 2);
    (*it).push_back( 4);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 7);
    (*it).push_back( 2);
    (*it).push_back( 3);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 8);
    (*it).push_back( 2);
    (*it).push_back( 1);
}

print matrix and find max product in rows:

void printMatrix( Matrix& matrix) {
    outIt it = matrix.begin();
    while ( it != matrix.end()) {
        inIt it2 = (*it).begin();
        while ( it2 != (*it).end()) {
            printf( "%d", *it2);
            ++it2;
        }
        printf( "\n");
        ++it;
    }
}

/**
 * 
 * @param matrix
 * Largest product in row using rolling multiplication
 * @param n number of factors
 * @param v factors of largest product
 * @return largest product
 */
int largestProductInRow( Matrix& matrix, int n, vector< int>& v) {
    if ( n > matrix.size()) return -1;
    int res = 0;
    int N = matrix.size() - n + 1; // number of products in row (or column)
    /* search in rows */
    outIt it = matrix.begin();
    while (it != matrix.end()) {
        inIt it2 = (*it).begin();
        int currN = N;
        int product = 1;
        while (currN) {       // rolling product calculation
            inIt it3 = it2;
            int currn = n;
            if (currN == N) { // compute full product first time
                while (currn) {
                    product *= (*it3++);
                    --currn;
                }
            } else {          // rolling computation
                product *= (*(it3 + n - 1)) / (*(it3 - 1));
                it3 += n;
            }
            if (product > res) {
                res = product;
                copy(it3 - n, it3, v.begin());
            }
            --currN;
            ++it2;
        }
        ++it;
    }
    return res;
}

usage:

/*
 * 
 */
int main(int argc, char** argv) {

    Matrix matrix( 4, vector< int>());
    fillMatrix( matrix);
    printMatrix( matrix);
    vector< int> v(3);
    int res = largestProductInRow( matrix, 3, v);
    printf( "res:%d\n", res);
    copy( v.begin(), v.end(), ostream_iterator<int>(cout, ","));
    return 0;
}

result:

res:42

7,2,3,

RUN SUCCESSFUL (total time: 113ms)

Answer 2

Lets say we have s x t matrix (s columns and t rows).

int res = 0;
if(s >= n)
{
    for (int r = 0; r < t; ++r) // for each row
    {
        for (int i = 0; i <= s-n; ++i)  //moving through the row
        {
            int mul = m[i][0];
            for (int j = 1; j < n; ++j) //calculating product in a row
            {
                mul*=m[i][j];
            }
            if(mul > res)
            {
                res = mul;
                //save i, j here if needed
            }
        }   
    }
}


if(t >= n)
{
    for (int c = 0; c < s; ++c) // for each column
    {
        for (int i = 0; i <= t-n; ++i)  //moving through the column
        {
            int mul = m[0][i];
            for (int j = 1; j < n; ++j) //calculating product in a column
            {
                mul*=m[j][i];
            }
            if(mul > res)
            {
                res = mul;
                //save i, j here if needed
            }
        }   
    }   
}

Answer 3

If you insist on brute-force, then as you said, you need to iterate over all [x,y], which will be the starting points of the rows. From these you can iterate over k adjacent elements in all directions. You can store the directions as vectors in an array. This would run in O(k n^2).

For n x n matrix and looking for k elements in row, C-like pseudocode would look like this (note there is no bounds checking, for the sake of simplicity):

// define an array of directions as [x,y] unit vectors
// you only need to check in 4 directions, other 4 are the same, just reversed
int[4][2] dirs = {{1,0}, {1,1}, {0,1}, {-1,1}};

// iterate over all starting positions
for (x = 0; x < n; ++x) {
    for (y = 0; y < n; ++y) {
        // iterate over all directions
        for (d = 0; d < 4; ++d) {
            result = 1;
            // iterate over elements in row starting at [x,y]
            // going in direction dirs[d]
            for (i = 0; i < k; ++i) {
                // multiply current result by the element,
                // which is i places far from the beginning [x,y]
                // in the direction pointed by dirs[d]
                new_x = x + i * dirs[d][0];
                new_y = y + i * dirs[d][1];
                // you need to check the bounds, i'm not writing it here
                // if new_x or new_y are outside of the matrix
                // then continue with next direction
                result *= matrix[new_x][new_y];
            }
            if (result > max) {
                max = result;
            }
        }
    }
}

Slightly better, less of a brute-force way would be to start on the boundary of a matrix, pick a direction and go in this direction to the opposite side of the matrix, keeping the product of the last k numbers on the way.

While walking, you keep the product, multiplying it by the number you got to and dividing by the number you left k steps ago. This way, with some bounds checking of course, the product is always product of the last k numbers, therefore if the current product is more than maximum, just let max = product. This runs always in O(n^2).