3548. Equal Sum Grid Partition II

/**
 * Problem: LeetCode 3548 - Equal Sum Grid Partition II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.HashSet;

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long totalSum = 0;
        for (int[] row : grid) {
            for (int val : row) {
                totalSum += val;
            }
        }

        return canPartition(grid, totalSum) ||
               canPartition(reverseRows(grid), totalSum) ||
               canPartition(transpose(grid), totalSum) ||
               canPartition(reverseRows(transpose(grid)), totalSum);
    }

    private boolean canPartition(int[][] grid, long totalSum) {
        int m = grid.length;
        int n = grid[0].length;
        long topSum = 0;
        HashSet<Long> seen = new HashSet<>();

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

            long botSum = totalSum - topSum;
            long diff = topSum - botSum;

            if (diff == 0) {
                return true;
            }

            if (diff > 0) {
                if (i == 0) {
                    // Top section has height 1: only end elements can be removed without disconnecting
                    if (n > 1) {
                        if (diff == grid[0][0] || diff == grid[0][n - 1]) {
                            return true;
                        }
                    }
                } else if (n == 1) {
                    // Top section has width 1: only top or bottom element can be removed
                    if (diff == grid[0][0] || diff == grid[i][0]) {
                        return true;
                    }
                } else {
                    // Top section has height >= 2 and width >= 2: any cell can be removed
                    if (seen.contains(diff)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private int[][] reverseRows(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] rev = new int[m][n];
        for (int i = 0; i < m; i++) {
            rev[i] = grid[m - 1 - i];
        }
        return rev;
    }

    private int[][] transpose(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] trans = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                trans[j][i] = grid[i][j];
            }
        }
        return trans;
    }
}

"""
Problem: LeetCode 3548 - Equal Sum Grid Partition II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
class Solution:
    def canPartitionGrid(self, grid: list[list[int]]) -> bool:
        total_sum = sum(sum(row) for row in grid)

        def can_partition(g: list[list[int]]) -> bool:
            R = len(g)
            C = len(g[0])
            top_sum = 0
            seen = set()

            for i in range(R - 1):
                for j in range(C):
                    seen.add(g[i][j])
                    top_sum += g[i][j]

                bot_sum = total_sum - top_sum
                diff = top_sum - bot_sum

                if diff == 0:
                    return True

                if diff > 0:
                    if i == 0:
                        if C > 1 and (diff == g[0][0] or diff == g[0][C - 1]):
                            return True
                    elif C == 1:
                        if diff == g[0][0] or diff == g[i][0]:
                            return True
                    else:
                        if diff in seen:
                            return True

            return False

        def reverse_rows(g: list[list[int]]) -> list[list[int]]:
            return g[::-1]

        def transpose(g: list[list[int]]) -> list[list[int]]:
            return [list(col) for col in zip(*g)]

        return (
            can_partition(grid) or
            can_partition(reverse_rows(grid)) or
            can_partition(transpose(grid)) or
            can_partition(reverse_rows(transpose(grid)))
        )

/**
 * Problem: LeetCode 3548 - Equal Sum Grid Partition II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long totalSum = 0;
        for (const auto& row : grid) {
            for (int val : row) {
                totalSum += val;
            }
        }

        if (canPartition(grid, totalSum)) return true;
        if (canPartition(reverseRows(grid), totalSum)) return true;
        vector<vector<int>> trans = transpose(grid);
        if (canPartition(trans, totalSum)) return true;
        if (canPartition(reverseRows(trans), totalSum)) return true;

        return false;
    }

private:
    bool canPartition(const vector<vector<int>>& grid, long long totalSum) {
        int m = grid.size();
        int n = grid[0].size();
        long long topSum = 0;
        unordered_set<long long> seen;

        for (int i = 0; i < m - 1; ++i) {
            for (int j = 0; j < n; ++j) {
                seen.insert(grid[i][j]);
                topSum += grid[i][j];
            }

            long long botSum = totalSum - topSum;
            long long diff = topSum - botSum;

            if (diff == 0) {
                return true;
            }

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

        return false;
    }

    vector<vector<int>> reverseRows(const vector<vector<int>>& grid) {
        int m = grid.size();
        vector<vector<int>> rev(m);
        for (int i = 0; i < m; ++i) {
            rev[i] = grid[m - 1 - i];
        }
        return rev;
    }

    vector<vector<int>> transpose(const vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> trans(n, vector<int>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                trans[j][i] = grid[i][j];
            }
        }
        return trans;
    }
};

/**
 * Problem: LeetCode 3548 - Equal Sum Grid Partition II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var canPartitionGrid = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let totalSum = 0;

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

    function canPartition(g) {
        const R = g.length;
        const C = g[0].length;
        let topSum = 0;
        const seen = new Set();

        for (let i = 0; i < R - 1; i++) {
            for (let j = 0; j < C; j++) {
                seen.add(g[i][j]);
                topSum += g[i][j];
            }

            const botSum = totalSum - topSum;
            const diff = topSum - botSum;

            if (diff === 0) {
                return true;
            }

            if (diff > 0) {
                if (i === 0) {
                    if (C > 1 && (diff === g[0][0] || diff === g[0][C - 1])) {
                        return true;
                    }
                } else if (C === 1) {
                    if (diff === g[0][0] || diff === g[i][0]) {
                        return true;
                    }
                } else {
                    if (seen.has(diff)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    function reverseRows(g) {
        const R = g.length;
        const rev = new Array(R);
        for (let i = 0; i < R; i++) {
            rev[i] = g[R - 1 - i];
        }
        return rev;
    }

    function transpose(g) {
        const R = g.length;
        const C = g[0].length;
        const trans = Array.from({ length: C }, () => new Array(R));
        for (let i = 0; i < R; i++) {
            for (let j = 0; j < C; j++) {
                trans[j][i] = g[i][j];
            }
        }
        return trans;
    }

    if (canPartition(grid)) return true;
    if (canPartition(reverseRows(grid))) return true;
    const trans = transpose(grid);
    if (canPartition(trans)) return true;
    if (canPartition(reverseRows(trans))) return true;

    return false;
};