3546. Equal Sum Grid Partition I LeetCode Solution

3 months ago

LeetCode Admin

4 minutes

In this guide, you will get 3546. Equal Sum Grid Partition I LeetCode Solution with the best time and space complexity. The solution to Equal Sum Grid Partition I 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.

Problem Statement
Complexity Analysis
Equal Sum Grid Partition I solution in C++
Equal Sum Grid Partition I solution in Java
Equal Sum Grid Partition I solution in Python
Additional Resources

3546. Equal Sum Grid Partition I LeetCode Solution image

Problem Statement of Equal Sum Grid Partition I

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 the elements in both sections is equal.

Return true if such a partition exists; otherwise return false.

Example 1:

Input: grid = [[1,4],[2,3]]
Output: true
Explanation:

A horizontal cut between row 0 and row 1 results in two non-empty sections, each with a sum of 5. Thus, the answer is true.

Example 2:

Input: grid = [[1,3],[2,4]]
Output: false
Explanation:
No horizontal or vertical cut results in two non-empty sections with equal sums. Thus, 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)

3546. Equal Sum Grid Partition I LeetCode Solution in C++

class Solution {
 public:
  bool canPartitionGrid(vector<vector<int>>& grid) {
    const long totalSum = accumulate(grid.begin(), grid.end(), 0L,
                                     [](long acc, const vector<int>& row) {
      return acc + accumulate(row.begin(), row.end(), 0L);
    });
    return canPartition(grid, totalSum) ||
           canPartition(transposed(grid), totalSum);
  }

 private:
  bool canPartition(const vector<vector<int>>& lines, long totalSum) {
    long runningSum = 0;
    for (const vector<int>& line : lines) {
      runningSum += accumulate(line.begin(), line.end(), 0L);
      if (runningSum * 2 == totalSum)
        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;
  }
};
/* code provided by PROGIEZ */

3546. Equal Sum Grid Partition I LeetCode Solution in Java

class Solution {
  public boolean canPartitionGrid(int[][] grid) {
    final long totalSum = Arrays.stream(grid).flatMapToInt(Arrays::stream).asLongStream().sum();
    return canPartition(grid, totalSum) || canPartition(transposed(grid), totalSum);
  }

  private boolean canPartition(int[][] lines, long totalSum) {
    long runningSum = 0;
    for (int[] line : lines) {
      runningSum += Arrays.stream(line).asLongStream().sum();
      if (runningSum * 2 == totalSum)
        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;
  }
}
// code provided by PROGIEZ

3546. Equal Sum Grid Partition I LeetCode Solution in Python

class Solution:
  def canPartitionGrid(self, grid: list[list[int]]) -> bool:
    totalSum = sum(map(sum, grid))

    def canPartition(grid: list[list[int]]) -> bool:
      runningSum = 0
      for row in grid:
        runningSum += sum(row)
        if runningSum * 2 == totalSum:
          return True
      return False

    return canPartition(grid) or canPartition(zip(*grid))
 # code by PROGIEZ