In this guide, you will get 3548. Equal Sum Grid Partition II LeetCode Solution with the best time and space complexity. The solution to Equal Sum Grid Partition II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
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 <= 105
1 <= n == grid[i].length <= 105
2 <= m * n <= 105
1 <= grid[i][j] <= 105
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
3548. Equal Sum Grid Partition II LeetCode Solution in C++
class Solution {
public:
bool canPartitionGrid(vector<vector<int>>& grid) {
const long sum = accumulate(grid.begin(), grid.end(), 0L,
[](long acc, const vector<int>& row) {
return acc + accumulate(row.begin(), row.end(), 0L);
});
return canPartition(grid, sum) || canPartition(reversed(grid), sum) ||
canPartition(reversed(transposed(grid)), sum) ||
canPartition(transposed(grid), sum);
}
private:
bool canPartition(const vector<vector<int>>& grid, long sum) {
long topSum = 0;
unordered_set<int> seen;
for (int i = 0; i < grid.size(); ++i) {
topSum += accumulate(grid[i].begin(), grid[i].end(), 0L);
const long botSum = sum - topSum;
seen.insert(grid[i].begin(), grid[i].end());
if (topSum - botSum == 0 || topSum - botSum == grid[0][0] ||
topSum - botSum == grid[0].back() || topSum - botSum == grid[i][0])
return true;
if (grid[0].size() > 1 && i > 0 && seen.count(topSum - botSum))
return true;
}
return false;
}
vector<vector<int>> transposed(const vector<vector<int>>& grid) {
vector<vector<int>> res(grid[0].size(), vector<int>(grid.size()));
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
res[j][i] = grid[i][j];
return res;
}
vector<vector<int>> reversed(const vector<vector<int>>& grid) {
return {grid.rbegin(), grid.rend()};
}
}; /* code provided by PROGIEZ */
3548. Equal Sum Grid Partition II LeetCode Solution in Java
class Solution {
public boolean canPartitionGrid(int[][] grid) {
final long sum = Arrays.stream(grid).flatMapToInt(Arrays::stream).asLongStream().sum();
return canPartition(grid, sum) || canPartition(reversed(grid), sum) ||
canPartition(reversed(transposed(grid)), sum) || canPartition(transposed(grid), sum);
}
private boolean canPartition(int[][] grid, long sum) {
long topSum = 0;
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < grid.length; ++i) {
topSum += Arrays.stream(grid[i]).asLongStream().sum();
final long botSum = sum - topSum;
Arrays.stream(grid[i]).forEach(seen::add);
if (topSum - botSum == 0 || topSum - botSum == grid[0][0] ||
topSum - botSum == grid[0][grid[0].length - 1] || topSum - botSum == grid[i][0])
return true;
if (grid[0].length > 1 && i > 0 && seen.contains((int) (topSum - botSum)))
return true;
}
return false;
}
private int[][] transposed(int[][] grid) {
int[][] res = new int[grid[0].length][grid.length];
for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
res[j][i] = grid[i][j];
return res;
}
private int[][] reversed(int[][] grid) {
return Arrays.stream(grid).collect(Collectors.collectingAndThen(Collectors.toList(), list -> {
Collections.reverse(list);
return list.toArray(new int[0][]);
}));
}
} // code provided by PROGIEZ
3548. Equal Sum Grid Partition II LeetCode Solution in Python
class Solution:
def canPartitionGrid(self, grid: list[list[int]]) -> bool:
summ = sum(map(sum, grid))
def canPartition(grid: list[list[int]]) -> bool:
topSum = 0
seen = set()
for i, row in enumerate(grid):
topSum += sum(row)
botSum = summ - topSum
seen |= set(row)
if topSum - botSum in (0, grid[0][0], grid[0][-1], row[0]):
return True
if len(grid[0]) > 1 and i > 0 and topSum - botSum in seen:
return True
return False
return (canPartition(grid) or
canPartition(grid[::-1]) or
canPartition(list(zip(*grid))[::-1]) or
canPartition(list(zip(*grid)))) # code by PROGIEZ
