LeetCode Daily Problem P3546 Equal Sum Matrix Partition I

---

Timeline

Timeline

2026-03-25

init

Prefix sum

---

Problem:

P3546 Equal Sum Matrix Partition I

https://leetcode.cn/problems/equal-sum-grid-partition-i/description/?envType=daily-question&envId=2026-03-25

A prefix sum reskin problem; note that the sum may exceed the maximum value representable by int.

#include <vector>
using std::vector;

class Solution {
    public:
        bool canPartitionGrid(vector<vector<int> > &grid)
        {
                // 1 <= m == grid.length <= 105
                // 1 <= n == grid[i].length <= 105
                // 2 <= m * n <= 105
                // 1 <= grid[i][j] <= 105
                int i, j, m = grid.size(), n = grid[0].size();
                int total = m * n;
                long last;
                vector<long> prefix_sum(total, 0);
                vector<long> suffix_sum(total, 0);

                // Horizontal split
                last = grid[0][0];
                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (i == 0 && j == 0)
                                        continue;
                                prefix_sum[i * n + j] = last + prefix_sum[i * n + j - 1];
                                last = grid[i][j];
                        }
                }

                last = grid[m - 1][n - 1];
                for (i = m - 1; i >= 0; i--) {
                        for (j = n - 1; j >= 0; j--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_sum[i * n + j] = last + suffix_sum[i * n + j + 1];
                                last = grid[i][j];
                        }
                }

                for (i = 0; i < m - 1; i++) {
                        if (prefix_sum[i * n + n - 1] + grid[i][n - 1] == suffix_sum[i * n + n - 1])
                                return true;
                }

                // Vertical split
                prefix_sum[0] = 0;
                last = grid[0][0];
                for (j = 0; j < n; j++) {
                        for (i = 0; i < m; i++) {
                                if (i == 0 && j == 0)
                                        continue;
                                prefix_sum[j * m + i] = last + prefix_sum[j * m + i - 1];
                                last = grid[i][j];
                        }
                }

                suffix_sum[total - 1] = 0;
                last = grid[m - 1][n - 1];
                for (j = n - 1; j >= 0; j--) {
                        for (i = m - 1; i >= 0; i--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_sum[j * m + i] = last + suffix_sum[j * m + i + 1];
                                last = grid[i][j];
                        }
                }
                for (j = 1; j < n; j++) {
                        if (prefix_sum[j * m] == suffix_sum[j * m] + grid[0][j])
                                return true;
                }

                return false;
        }
};