patternpythonMinor

Finding the max product of a 2D array

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

thearrayproductmaxfinding

Problem

Given a 2D array of unsigned integers and a maximum length n, find a path in that matrix that is not longer than n and which maximizes the product of the elements in the path. The output should consist of both the path and the product.

A path consists of neighbouring integers that are either all in the same row, or in the same column, or down a diagonal in the down-right direction. The code for this problem is below:

```
def maxPathProduct(self, matrix, maxLen):
"""
Take a 2D Array of ints
and return the largest Product of list of ints of length maxLen
and the product of the list integers
"""
maxProduct = -1
maxList = []
if len(matrix) == 0:
return maxProduct, maxList
numRows = len(matrix)
numCols = len(matrix[0])

for direction in range(1, 4):
if direction == 1:
numLines = numCols
elif direction == 2:
numLines = numRows
elif direction == 3:
numLines = numRows + numCols -1
for line in range (0,numLines):
pathProduct = 1
pathLen = 0
if direction == 1:
headRow = 0
headCol = line
elif direction ==2:
headCol = 0
headRow = line
elif direction == 3:
headRow = 0 if line >= numRows else line
headCol = line-numRows if line >= numRows else 0
tailRow = headRow
tailCol = headCol
pathList = []
while headRow maxLen:
pathProduct /= matrix[tailRow][tailCol]
pathList = pathList[1:]
if direction== 1:
tailRow += 1
elif direction == 2:
tailCol += 1
elif direction == 3:
tailCol += 1
tailRow += 1
if pathProduct > maxProduct:
maxProdu

Solution

First of all, if this function is not in a class you must remove the self parameter, there's no need of that. Then you should insert a check if the parameters are correct, that is the rows number and the columns number must be at least equals to maxLength:

if len(matrix) < maxLen and len(matrix[0]) < maxLen:
        return -1 # return error code

In this cases, when you have to move across a matrix, I suggest you to use a sort of direction tuples, which are tuples of the form (1,0), (0,1), (1,1), (-1,0) etc..; so for each element of the matrix you add to the indexes of that element one of this tuples multiplied for a number. Maybe it's more complicate to speak about it than show it:

def maxPathProduct(matrix, maxLen):
    if len(matrix)  maxProduct:
                    maxProduct = tempProduct
                    maxList = tempList
    return maxProduct, maxList

In this case you have only to move from left-to-right ((0,1)), up-to-down ((1,0)) and diagonally-up-to-down ((1,1)). With those direction tuples you can avoid that terrible long list of if-elif-else. I've tried this solution a bit, I'm not completely sure that it works, but I hope that you understand the trick.

Code Snippets

if len(matrix) < maxLen and len(matrix[0]) < maxLen:
        return -1 # return error code

def maxPathProduct(matrix, maxLen):
    if len(matrix) < maxLen and len(matrix[0]) < maxLen:
        return -1
    maxProduct = -1
    maxList = []
    directions = [(1, 0), (0, 1), (1, 1)] 
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            for dir in directions:
                tempProduct = 1
                tempList = []
                inc = 0
                indexOutOfBound = False
                while len(tempList) < maxLen and not indexOutOfBound:
                    row = i + dir[0] * inc
                    col = j + dir[1] * inc
                    if row < len(matrix) and col < len(matrix[0]):
                        tempProduct *= matrix[row][col]
                        tempList.append(matrix[row][col])
                        inc += 1
                    else:
                        indexOutOfBound = True
                if tempProduct > maxProduct:
                    maxProduct = tempProduct
                    maxList = tempList
    return maxProduct, maxList

Context

StackExchange Code Review Q#158422, answer score: 2

Revisions (0)

No revisions yet.