Maximum Sum Submatrix

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Maximum Sum Submatrix. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Google Maps may represent a geographic region as a grid of signed traffic-impact scores. Find the contiguous rectangular submatrix with the largest possible sum.

Return an array [max_sum, top, left, bottom, right], where max_sum is the rectangle's sum and the coordinates are inclusive, zero-based indices. If multiple rectangles have the same sum, return the one encountered first by the algorithm's top-to-bottom and left-to-right search order.

A rectangle must contain at least one cell. You may assume the matrix is non-empty.

Constraints

1 <= rows, cols <= 150
-10^4 <= matrix[r][c] <= 10^4
The matrix is non-empty and rectangular
The returned coordinates are zero-based and inclusive

Function Signature

def max_sum_submatrix(matrix):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output