Given a $2$D integer array grid of size m $\times$ n.

A partition is formed by making a single straight horizontal or vertical cut that divides grid into two non-empty rectangular subgrids.

You may optionally remove at most $1$ cell from at most $1$ of the two subgrids. A partition is valid if:

• The sum of values in both subgrids is equal after the optional cell removal.

• If a cell is removed, the remaining cells in that subgrid must remain non-empty and form a single $4$-directionally connected component.

Return true if there exists at least $1$ valid partition, or false otherwise.

Note: Two cells are considered connected if they share an edge.

Constraints:

• $1 \leq$ m $==$ grid.length $\leq 10^5$

• $1 \leq$ n $==$ grid[i].length $\leq 10^5$

• $2 \leq$ m * n $\leq 10^5$

• $1 \leq$ grid[i][j] $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.