#3548

Equal Sum Grid Partition II

hard · 21.7% accepted · 40 likes · top 2%

array · hash table · matrix · enumeration · prefix sum

Description

You are given an m x n matrix grid of positive integers. Your task is to determine if it is possible to make either one horizontal or one vertical cut on the grid such that:

- Each of the two resulting sections formed by the cut is non-empty.

- The sum of elements in both sections is equal, or can be made equal by discounting at most one single cell in total (from either section).

- If a cell is discounted, the rest of the section must remain connected.

Return true if such a partition exists; otherwise, return false.

Note: A section is connected if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.

Solution