3546. Equal Sum Grid Partition I

Medium

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

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

Intuition

The problem is essentially about determining if the matrix can be split into two equal-sum halves through a single horizontal or vertical cut.

To achieve this:

Calculate the total sum s of all elements in the matrix. If s is odd, an equal partition is impossible since two equal integers can't sum to an odd number, so we immediately return false.
If the total sum s is even, we need to explore potential cut lines:
- Horizontal Cut: Traverse each row, keeping a running total pre of the sums of the rows processed so far. At each step, check if doubling this running total (pre * 2) equals s. If it does and the current row is not the last row, an equal partition is possible with a horizontal cut, so return true.
- Vertical Cut: Similarly, traverse each column, accumulating the column sums into pre. Again, if pre * 2 equals s and the current column is not the last one, it suggests an equal partition is feasible with a vertical cut, so return true.
If none of these potential cuts allow for an equal partition, return false.

This approach effectively checks if there's a way to partition the matrix into two sections with equal sums through simple arithmetic and traversal.

Solution Approach

The solution approach uses the Enumeration and Prefix Sum technique to determine if the grid can be evenly split by a single cut.

Here's the step-by-step breakdown:

Calculate the Total Sum:
- First, calculate the sum s of all elements in the matrix using a nested sum operation: s = sum(sum(row) for row in grid). If this sum is odd (s % 2), return False immediately because an even partition isn't possible when the total sum is odd.
Horizontal Cut Check:
- Initialize a prefix sum pre to zero.
- Traverse each row of the matrix. For each row, add its sum to pre (pre += sum(row)).
- After updating pre, check if pre * 2 == s. If it is true and you haven't reached the last row (i != len(grid) - 1), a horizontal cut is possible between the current row and the next. Return True in this case.
Vertical Cut Check:
- Reset the prefix sum pre to zero.
- Use zip(*grid) to traverse each column as if it were a row, allowing for column-wise operations. For each column, update pre with the sum of its elements (pre += sum(col)).
- After updating pre, check if pre * 2 == s. If true and the current column isn't the last column (j != len(grid[0]) - 1), a vertical cut is feasible between the current column and the next. Return True.
Return False:
- If neither horizontal nor vertical checks result in an equal partition, return False.

The solution efficiently verifies potential cuts by leveraging the summation properties of the grid's rows and columns. This approach minimizes unnecessary computations and performs O(m + n) checks.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Given a 3 x 3 matrix:

grid = [
    [2, 2, 2],
    [2, 2, 2],
    [2, 2, 2]
]

Let's determine if it's possible to make either a horizontal or vertical cut so that the sections formed have equal sums:

Calculate the Total Sum:

Compute the total sum s of all elements in the grid:

s = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 18

Since s is even, an equal partition is possible in theory.

Horizontal Cut Check:
- Start with pre = 0.
- Traverse each row and calculate the running total:
  - After first row: pre = 6 (sum of [2, 2, 2])
    - Check: pre * 2 = 12, which is not equal to s = 18
  - After second row: pre = 12 (sum of [2, 2, 2] + [2, 2, 2])
    - Check: pre * 2 = 24, which is not equal to s = 18
  - After third row: pre = 18 (sum of all rows)
- No suitable horizontal cut was found since no intermediate check met the condition for an equal partition.
Vertical Cut Check:
- Reset pre = 0.
- Use zip(*grid) to access columns and calculate the running total:
  - First column: [2, 2, 2], pre = 6
    - Check: pre * 2 = 12, which is not equal to s = 18
  - Second column: [2, 2, 2], pre = 12
    - Check: pre * 2 = 24, which is not equal to s = 18
  - Third column: [2, 2, 2], pre = 18
- No suitable vertical cut was found.
Conclusion:
- Both cut checks result in False, thus unable to split the matrix into two sections with equal sum using a single horizontal or vertical cut.

Final Result: False

Solution Implementation

1from typing import List
2
3class Solution:
4    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
5        # Calculate total sum of all elements in the grid
6        total_sum = sum(sum(row) for row in grid)
7
8        # If total sum is odd, we cannot partition it into two equal parts
9        if total_sum % 2 != 0:
10            return False
11
12        # Check for a horizontal partition
13        cumulative_sum = 0
14        for i, row in enumerate(grid):
15            cumulative_sum += sum(row)
16            # If cumulative_sum equals half of the total, a horizontal partition is possible
17            # Ensure it's not splitting at the last row
18            if cumulative_sum * 2 == total_sum and i != len(grid) - 1:
19                return True
20
21        # Check for a vertical partition
22        cumulative_sum = 0
23        for j, col in enumerate(zip(*grid)):  # Transpose to iterate over columns
24            cumulative_sum += sum(col)
25            # If cumulative_sum equals half of the total, a vertical partition is possible
26            # Ensure it's not splitting at the last column
27            if cumulative_sum * 2 == total_sum and j != len(grid[0]) - 1:
28                return True
29
30        # If no partition was found, return False
31        return False
32

1class Solution {
2
3    public boolean canPartitionGrid(int[][] grid) {
4        // Variable to store the total sum of all elements in the grid
5        long totalSum = 0;
6
7        // Calculate the total sum of all elements in the grid
8        for (int[] row : grid) {
9            for (int element : row) {
10                totalSum += element;
11            }
12        }
13
14        // If the total sum is not even, it's not possible to partition into two equal parts
15        if (totalSum % 2 != 0) {
16            return false;
17        }
18
19        int numberOfRows = grid.length;
20        int numberOfColumns = grid[0].length;
21        long prefixSum = 0;
22
23        // Check if there is a horizontal partition that divides the grid into two areas of equal sum
24        for (int i = 0; i < numberOfRows; ++i) {
25            for (int element : grid[i]) {
26                prefixSum += element;
27            }
28
29            // Check if the current prefix sum is half of the total sum
30            if (prefixSum * 2 == totalSum && i < numberOfRows - 1) {
31                return true;
32            }
33        }
34
35        // Reset the prefix sum for checking the vertical partition
36        prefixSum = 0;
37
38        // Check if there is a vertical partition that divides the grid into two areas of equal sum
39        for (int j = 0; j < numberOfColumns; ++j) {
40            for (int i = 0; i < numberOfRows; ++i) {
41                prefixSum += grid[i][j];
42            }
43
44            // Check if the current prefix sum is half of the total sum
45            if (prefixSum * 2 == totalSum && j < numberOfColumns - 1) {
46                return true;
47            }
48        }
49
50        // If no valid partition is found, return false
51        return false;
52    }
53}
54

1class Solution {
2public:
3    bool canPartitionGrid(std::vector<std::vector<int>>& grid) {
4        long long totalSum = 0; // Variable to store the total sum of all grid elements
5      
6        // Calculate the total sum of the grid
7        for (const auto& row : grid) {
8            for (int val : row) {
9                totalSum += val;
10            }
11        }
12      
13        // If the total sum is odd, it's impossible to partition the grid into equal parts
14        if (totalSum % 2 != 0) {
15            return false;
16        }
17      
18        int rows = grid.size(); // Number of rows in the grid
19        int cols = grid[0].size(); // Number of columns in the grid
20        long long prefixSum = 0; // Variable to store the prefix sum of grid elements
21      
22        // Check if we can partition horizontally
23        for (int i = 0; i < rows; ++i) {
24            for (int val : grid[i]) {
25                prefixSum += val;
26            }
27            // If prefix sum equals half of total sum, and it's not the last row, partition is possible
28            if (prefixSum * 2 == totalSum && i + 1 < rows) {
29                return true;
30            }
31        }
32      
33        // Reset prefix sum for the vertical check
34        prefixSum = 0;
35      
36        // Check if we can partition vertically
37        for (int j = 0; j < cols; ++j) {
38            for (int i = 0; i < rows; ++i) {
39                prefixSum += grid[i][j];
40            }
41            // If prefix sum equals half of total sum, and it's not the last column, partition is possible
42            if (prefixSum * 2 == totalSum && j + 1 < cols) {
43                return true;
44            }
45        }
46      
47        // If no valid partition is found, return false
48        return false;
49    }
50};
51

1function canPartitionGrid(grid: number[][]): boolean {
2    let sum = 0;
3
4    // Calculate the total sum of the grid.
5    for (const row of grid) {
6        sum += row.reduce((a, b) => a + b, 0);
7    }
8
9    // If the total sum is odd, it's impossible to partition the grid into two equal parts.
10    if (sum % 2 !== 0) {
11        return false;
12    }
13
14    const [rowCount, columnCount] = [grid.length, grid[0].length];
15    let prefixSum = 0;
16
17    // Check if we can partition horizontally by summing row-wise.
18    for (let i = 0; i < rowCount; ++i) {
19        prefixSum += grid[i].reduce((a, b) => a + b, 0);
20        // Check if the sum up to the current row equals half of the total sum.
21        // Ensure we don't consider the last row (i + 1 < rowCount) since we need at least one row below.
22        if (prefixSum * 2 === sum && i + 1 < rowCount) {
23            return true;
24        }
25    }
26
27    prefixSum = 0;
28
29    // Check if we can partition vertically by summing column-wise.
30    for (let j = 0; j < columnCount; ++j) {
31        for (let i = 0; i < rowCount; ++i) {
32            prefixSum += grid[i][j];
33        }
34        // Check if the sum up to the current column equals half of the total sum.
35        // Ensure we don't consider the last column (j + 1 < columnCount) since we need at least one column after.
36        if (prefixSum * 2 === sum && j + 1 < columnCount) {
37            return true;
38        }
39    }
40
41    // If no valid partition is found, return false.
42    return false;
43}
44

Time and Space Complexity

The time complexity of the code is O(m \times n), where m and n are the numbers of rows and columns in the matrix, respectively. This is because the code iterates through each element of the grid twice—once for all rows and once for all columns.

The space complexity is O(1) as the code uses a constant amount of extra space regardless of the input size. This constant space accounts for the variables used in the iteration and summation processes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don't know