Skip to main content
Back to problems
#3546
Medium Algorithms

Equal sum grid partition i

Array Matrix Enumeration Prefix Sum
42.3% acceptance
Feb 25, 2026
77
5
Given an m x n matrix of positive integers, determine if it is possible to make one horizontal or one vertical cut such that both sections are non-empty and have equal sum.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn can_partition_grid(grid: Vec<Vec<i32>>) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    let total: i64 = grid.iter().flat_map(|r| r.iter()).map(|&x| x as i64).sum();
    
    if total % 2 != 0 { return false; }
    let half = total / 2;
    
    // Try horizontal cuts
    let mut prefix = 0i64;
    for r in 0..m - 1 {
      prefix += grid[r].iter().map(|&x| x as i64).sum::<i64>();
      if prefix == half { return true; }
    }
    
    // Try vertical cuts
    let mut prefix = 0i64;
    for c in 0..n - 1 {
      prefix += grid.iter().map(|row| row[c] as i64).sum::<i64>();
      if prefix == half { return true; }
    }
    
    false
  }
}