Daily LeetCode - by Vítor Belim

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.

Example 1:

Input: grid = [[1,4],[2,3]]

Output: true

Explanation:

A horizontal cut after the first row gives sums 1 + 4 = 5 and 2 + 3 = 5, which are equal. Thus, the answer is true.

Example 2:

Input: grid = [[1,2],[3,4]]

Output: true

Explanation:

A vertical cut after the first column gives sums 1 + 3 = 4 and 2 + 4 = 6.
By discounting 2 from the right section (6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer is true.

Example 3:

Input: grid = [[1,2,4],[2,3,5]]

Output: false

Explanation:

A horizontal cut after the first row gives 1 + 2 + 4 = 7 and 2 + 3 + 5 = 10.
By discounting 3 from the bottom section (10 - 3 = 7), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts ([2] and [5]). Thus, the answer is false.

Example 4:

Input: grid = [[4,1,8],[3,2,6]]

Output: false

Explanation:

No valid cut exists, so the answer is false.

Constraints:

1 <= m == grid.length <= 10⁵
1 <= n == grid[i].length <= 10⁵
2 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

Solutions

This code checks whether a 2D grid can be partitioned into two equal-sum regions using a single straight cut (either horizontal or vertical). It first calculates the total sum of all elements, then rotates the grid four times to test different cut orientations using the rotateGrid helper function. For each orientation, it accumulates sums row-by-row (excluding the last row) and looks for a position where the prefix sum equals half the total, or where the difference (prefix_sum * 2 - total) matches a previously seen grid value, indicating a valid partition point. Special handling applies when there's only a single column—it directly checks if any partial sum equals half the total. The rotateGrid helper performs a 90-degree clockwise rotation by transforming each element at position [i][j] to [j][m-1-i] in a new transposed grid, allowing the algorithm to test partitions in all four directions.

Language: javascript(2026-03-26 10:52)DONE

CPU Performance92.86%

Memory Performance100.00%

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var canPartitionGrid = function (grid) {
    let m = grid.length;
    let n = grid[0].length;
    let total = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            total += grid[i][j];
        }
    }

    for (let k = 0; k < 4; k++) {
        if (k > 0) {
            grid = rotateGrid(grid);
            m = grid.length;
            n = grid[0].length;
        }

        if (m < 2) {
            continue;
        }

        if (n == 1) {
            let sum = 0;

            for (let i = 0; i < m - 1; i++) {
                sum += grid[i][0];

                let diff = sum * 2 - total;
                if (diff === 0 || diff === grid[0][0] || diff === grid[i][0]) {
                    return true;
                }
            }

            continue;
        }

        let sum = 0;
        const seen = new Set();
        seen.add(0);

        for (let i = 0; i < m - 1; i++) {
            for (let j = 0; j < n; j++) {
                sum += grid[i][j];
                seen.add(grid[i][j]);
            }

            let diff = sum * 2 - total;

            if (i === 0 && (diff === 0 || diff === grid[0][0] || diff === grid[0][n - 1])) {
                return true;
            }

            if (i > 0 && seen.has(diff)) {
                return true;
            }
        }
    }

    return false;
};

const rotateGrid = (grid) => {
    const m = grid.length;
    const n = grid[0].length;

    const res = Array.from({ length: n }, () => new Array(m).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            res[j][m - 1 - i] = grid[i][j];
        }
    }

    return res;
};

Description

Solutions

AI Explanation