3546: Equal Sum Grid Partition I

Difficulty: Medium

Topics: Matrix, Prefix Sum, Array Manipulation

Companies: Microsoft, Amazon, Oracle

Key Insight: The solution requires calculating prefix sums efficiently and understanding parity conditions for equal partitioning.

Problem Statement

Given an m x n matrix of positive integers, determine if a single horizontal or vertical cut can split the grid into two non-empty parts with equal sums.

Example 1

Input: grid = [[1,4],[2,3]]
Output: true
Explanation: Horizontal cut after first row creates two parts with sum 5 each

Example 2

Input: grid = [[1,3],[2,4]]
Output: false
Explanation: No valid cut exists

Problem Link: View on LeetCode ↗

Approach 1: Brute Force Checking

Check all possible horizontal and vertical cuts by calculating partition sums directly.

Algorithm Steps

Calculate total sum of all elements
Return false if total is odd
Check every possible horizontal cut position
Check every possible vertical cut position

Complexity Analysis

Time Complexity	Space Complexity
O(m²n + n²m)	O(1)

Brute Force Solution

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long total = 0;
        int m = grid.size(), n = grid[0].size();
        
        for (auto& row : grid)
            for (int num : row)
                total += num;
        
        if (total % 2 != 0) return false;
        long long target = total / 2;
        
        // Check horizontal cuts
        if (m > 1) {
            long long upperSum = 0;
            for (int i = 0; i < m-1; ++i) {
                for (int num : grid[i])
                    upperSum += num;
                if (upperSum == target) return true;
            }
        }
        
        // Check vertical cuts
        if (n > 1) {
            long long leftSum = 0;
            for (int j = 0; j < n-1; ++j) {
                for (int i = 0; i < m; ++i)
                    leftSum += grid[i][j];
                if (leftSum == target) return true;
            }
        }
        
        return false;
    }
};

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long total = 0;
        int m = grid.length, n = grid[0].length;
        
        for (int[] row : grid)
            for (int num : row)
                total += num;
        
        if (total % 2 != 0) return false;
        long target = total / 2;
        
        // Check horizontal cuts
        if (m > 1) {
            long upperSum = 0;
            for (int i = 0; i < m-1; ++i) {
                for (int num : grid[i])
                    upperSum += num;
                if (upperSum == target) return true;
            }
        }
        
        // Check vertical cuts
        if (n > 1) {
            long leftSum = 0;
            for (int j = 0; j < n-1; ++j) {
                for (int i = 0; i < m; ++i)
                    leftSum += grid[i][j];
                if (leftSum == target) return true;
            }
        }
        
        return false;
    }
}

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        total = sum(num for row in grid for num in row)
        if total % 2 != 0: return False
        target, m, n = total//2, len(grid), len(grid[0])
        
        # Horizontal checks
        if m > 1:
            current = 0
            for i in range(m-1):
                current += sum(grid[i])
                if current == target: return True
        
        # Vertical checks
        if n > 1:
            current = 0
            for j in range(n-1):
                current += sum(row[j] for row in grid)
                if current == target: return True
        
        return False

Use Case: Only suitable for small grids (m,n < 50) due to quadratic complexity

Approach 2: Original Prefix Sum

Initial implementation with separate sum calculations for rows and columns.

Algorithm Steps

Calculate total sum in first pass
Compute row sums in second pass
Compute column sums in third pass
Check prefix sums for valid partitions

Complexity Analysis

Time Complexity	Space Complexity
O(3m*n)	O(max(m,n))

Original Solution

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        int total = 0;
        for(auto& row : grid) {
            for(int num : row) {
                total += num;
            }
        }
        
        if(total % 2 != 0) return false;
        int target = total / 2;
        
        int rowSum = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int num : grid[i]) {
                rowSum += num;
            }
            if(rowSum == target && i != grid.size()-1) {
                return true;
            }
        }
        
        int n = grid[0].size();
        vector<int> colSums(n, 0);
        for(int j = 0; j < n; ++j) {
            for(int i = 0; i < grid.size(); ++i) {
                colSums[j] += grid[i][j];
            }
        }
        
        int colPrefix = 0;
        for(int j = 0; j < n; ++j) {
            colPrefix += colSums[j];
            if(colPrefix == target && j != n-1) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        int total = 0;
        for(int[] row : grid) {
            for(int num : row) {
                total += num;
            }
        }
        
        if(total % 2 != 0) return false;
        int target = total / 2;
        
        int rowSum = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int num : grid[i]) {
                rowSum += num;
            }
            if(rowSum == target && i != grid.length-1) {
                return true;
            }
        }
        
        int n = grid[0].length;
        int[] colSums = new int[n];
        for(int j = 0; j < n; j++) {
            for(int i = 0; i < grid.length; i++) {
                colSums[j] += grid[i][j];
            }
        }
        
        int colPrefix = 0;
        for(int j = 0; j < n; j++) {
            colPrefix += colSums[j];
            if(colPrefix == target && j != n-1) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        total = sum(num for row in grid for num in row)
        
        if total % 2 != 0:
            return False
        
        target = total // 2
        current = 0
        
        # Check horizontal cuts
        for i in range(len(grid)):
            current += sum(grid[i])
            if current == target and i != len(grid)-1:
                return True
        
        # Check vertical cuts
        if len(grid[0]) == 1:
            return False
            
        col_sums = [sum(row[j] for row in grid) for j in range(len(grid[0]))]
        current_col = 0
        
        for j in range(len(col_sums)):
            current_col += col_sums[j]
            if current_col == target and j != len(col_sums)-1:
                return True
        
        return False

Note: This approach uses three separate loops leading to higher constant factors

Approach 3: Optimized Prefix Sum with Precomputation

Calculate total sum, row sums, and column sums in a single pass, then check prefix sums efficiently.

Algorithm Steps

Compute total sum, row sums, and column sums in one loop
Return false if total is odd
Check horizontal cuts using precomputed row sums
Check vertical cuts using precomputed column sums

Complexity Analysis

Time Complexity	Space Complexity
O(m*n)	O(m + n)

Optimal Solution

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return false;
        int n = grid[0].size();
        if (n == 0) return false;
        
        long long total = 0;
        vector<long long> rowSums(m, 0);
        vector<long long> colSums(n, 0);
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rowSums[i] += grid[i][j];
                colSums[j] += grid[i][j];
                total += grid[i][j];
            }
        }
        
        if (total % 2 != 0) return false;
        long long target = total / 2;
        
        // Check horizontal cuts
        long long rowPrefix = 0;
        for (int i = 0; i < m; ++i) {
            rowPrefix += rowSums[i];
            if (rowPrefix == target && i != m - 1) {
                return true;
            }
        }
        
        // Check vertical cuts
        long long colPrefix = 0;
        for (int j = 0; j < n; ++j) {
            colPrefix += colSums[j];
            if (colPrefix == target && j != n - 1) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        int m = grid.length;
        if (m == 0) return false;
        int n = grid[0].length;
        if (n == 0) return false;
        
        long total = 0;
        long[] rowSums = new long[m];
        long[] colSums = new long[n];
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rowSums[i] += grid[i][j];
                colSums[j] += grid[i][j];
                total += grid[i][j];
            }
        }
        
        if (total % 2 != 0) return false;
        long target = total / 2;
        
        // Check horizontal cuts
        long rowPrefix = 0;
        for (int i = 0; i < m; ++i) {
            rowPrefix += rowSums[i];
            if (rowPrefix == target && i != m - 1) {
                return true;
            }
        }
        
        // Check vertical cuts
        long colPrefix = 0;
        for (int j = 0; j < n; ++j) {
            colPrefix += colSums[j];
            if (colPrefix == target && j != n - 1) {
                return true;
            }
        }
        
        return false;
    }
}

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        if not grid or not grid[0]:
            return False
        
        m, n = len(grid), len(grid[0])
        total = 0
        row_sums = [0] * m
        col_sums = [0] * n
        
        for i in range(m):
            for j in range(n):
                row_sums[i] += grid[i][j]
                col_sums[j] += grid[i][j]
                total += grid[i][j]
        
        if total % 2 != 0:
            return False
        target = total // 2
        
        # Check horizontal cuts
        current = 0
        for i in range(m):
            current += row_sums[i]
            if current == target and i != m - 1:
                return True
        
        # Check vertical cuts
        current = 0
        for j in range(n):
            current += col_sums[j]
            if current == target and j != n - 1:
                return True
        
        return False

Optimization Insight: Precompute row and column sums during total calculation to eliminate redundant loops. This reduces time complexity from O(3mn) to O(mn).

Approach Comparison

Approach	Time	Space	Best For
Brute Force	O(m²n + n²m)	O(1)	Small grids (m,n < 50)
Original Prefix Sum	O(3m*n)	O(max(m,n))	Medium grids
Optimized Prefix Sum	O(m*n)	O(m + n)	Large grids (m,n > 10³)

Important: The vertical cut check must be skipped for single-column grids to avoid invalid partitions.

Edge Case Analysis

1. Single Row Grid

Input: [[1,1]] → Output: true (vertical cut)

2. Single Column Grid

Input: [[2],[2]] → Output: true (horizontal cut)

3. Minimum Valid Grid

Input: [[1,1]] → Output: true

Pitfall: Always verify cuts don't create empty sections (check i != m-1 and j != n-1).

Frequently Asked Questions

1. Why check total parity first?

Odd totals can't be split into two equal integer sums, providing early exit.

2. How to handle empty sections?

We ensure cuts aren't at grid edges using i != m-1 and j != n-1 checks.

3. Why process rows before columns?

Row checks often complete faster, enabling early returns for better performance.

4. How does column sum calculation work?

We transpose the grid and sum columns using list comprehensions for efficiency.

5. What's the maximum grid size handled?

Efficiently handles max constraints (m*n ≤ 1e5) with linear time complexity.

6. Can we optimize space further?

Yes by calculating column sums during iteration, but complicates code structure.

7. How to verify correct partitioning?

Verify sum(left/top) = sum(right/bottom) = total/2 with non-empty sections.

8. Why use prefix sums?

Allows O(1) sum comparison after each row/column instead of recalculating.

9. Handle varying row lengths?

Problem constraints ensure rectangular grids (all rows same length).

10. Real-world applications?

Data partitioning, load balancing, and resource allocation systems.

Final Analysis: This problem demonstrates efficient matrix traversal techniques and mathematical optimization for partition problems. The solution leverages prefix sums and early termination checks to achieve optimal performance.