Skip to main content
Talentd

Equal Sum Grid Partition I - Solution & Explanation

MediumArrayMatrixEnumerationPrefix Sum14 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a 2D grid of integers and need to determine whether a single horizontal or vertical cut can divide the grid into two parts with equal total sum. The cut must split the grid along row or column boundaries, and both resulting regions must have the same sum.

Approach 1: Brute Force Enumeration (O(m*n*(m+n)) time, O(1) space)

Start by computing the total sum of the grid. Then try every possible horizontal cut and vertical cut. For each candidate cut, iterate through the relevant portion of the grid and compute the sum of both partitions directly. A horizontal cut requires summing rows above and below the cut; a vertical cut requires summing columns on both sides. This method is straightforward but inefficient because each cut recomputes large portions of the grid, leading to repeated work across iterations.

Approach 2: Enumeration + Prefix Sum (O(m*n) time, O(m+n) space)

Compute the total grid sum first. Then build running prefix sums for rows and columns while scanning the grid. For horizontal partitions, maintain a cumulative sum of rows from top to bottom. After processing each row, check whether the accumulated sum equals half of the total grid sum. For vertical partitions, maintain cumulative column sums while iterating across columns and perform the same comparison. This avoids recomputing sums for every candidate cut because each prefix value represents the sum of an entire region. The key insight is that any valid partition must split the total sum exactly in half, so you only check whether a prefix region equals totalSum / 2.

The solution relies on efficient grid traversal and incremental accumulation, which fits naturally with Prefix Sum techniques. The cut positions are tested through simple Enumeration while scanning the Matrix.

Recommended for interviews: Enumeration combined with prefix sums is the expected approach. The brute force version demonstrates the core idea of testing every possible cut, but the optimized prefix accumulation shows that you understand how to eliminate redundant work and reduce the complexity to O(m*n).

Solution

First, we calculate the sum of all elements in the matrix, denoted as s. If s is odd, it is impossible to divide the matrix into two parts with equal sums, so we directly return false.

If s is even, we can enumerate all possible partition lines to check if there exists a line that divides the matrix into two parts with equal sums.

We traverse each row from top to bottom, calculating the sum of all elements in the rows above the current row, denoted as pre. If pre times 2 = s and the current row is not the last row, it means we can perform a horizontal partition between the current row and the next row, so we return true.

If no such partition line is found, we traverse each column from left to right, calculating the sum of all elements in the columns to the left of the current column, denoted as pre. If pre times 2 = s and the current column is not the last column, it means we can perform a vertical partition between the current column and the next column, so we return true.

If no such partition line is found, we return false.

The time complexity is O(m times n), where m and n are the number of rows and columns in the matrix, respectively. The space complexity is O(1), as only constant extra space is used.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(m*n*(m+n))O(1)Useful for understanding the partition idea or when constraints are extremely small
Enumeration + Prefix SumO(m*n)O(m+n)Best general solution for large grids; avoids recomputing sums for every possible cut

Video Solution

Equal Sum Grid Partition I | Simplified Approach | Dry Run | Leetcode 3546 | codestorywithMIK • codestorywithMIK • 6,460 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Equal Sum Grid Partition I easy or hard?
Equal Sum Grid Partition I is typically categorized as a Medium problem. The challenge comes from recognizing that recomputing sums for every cut is inefficient and that prefix sums allow you to evaluate each partition in constant time.
Equal Sum Grid Partition I Python/Java solution
Most implementations follow the same structure across languages: compute the total grid sum, iterate through rows accumulating row sums, and check for half-sum equality. Then repeat the process for columns. The logic translates directly to Python, Java, C++, Go, TypeScript, and Rust.
How to solve Equal Sum Grid Partition I in O(n)?
Treat the grid as a matrix and compute its total sum first. Then accumulate prefix sums row by row for horizontal cuts and column by column for vertical cuts. If any prefix equals totalSum / 2, the remaining region automatically has the same sum. The entire process scans each cell once, giving O(m*n) time.
What is the best approach for Equal Sum Grid Partition I?
The most efficient approach uses enumeration combined with prefix sums. First compute the total sum of the grid, then scan rows and columns while maintaining cumulative sums. If any prefix region equals half of the total grid sum, the grid can be partitioned with a valid cut. This runs in O(m*n) time.
Is Equal Sum Grid Partition I asked at Google/Amazon/Meta?
Grid partitioning and prefix sum problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations that involve matrix prefix sums, region queries, or balanced partitions are common because they test both algorithmic reasoning and implementation accuracy.
What data structure is used in Equal Sum Grid Partition I?
The solution primarily relies on prefix sums computed from the matrix. Instead of additional complex structures, you maintain running totals for rows and columns to quickly evaluate whether a partition produces equal sums.
What is the time complexity of Equal Sum Grid Partition I?
The optimal solution runs in O(m*n) time, where m is the number of rows and n is the number of columns. You traverse the grid once to compute the total and prefix sums, then check potential horizontal and vertical cuts in constant time per step.

Ready to solve this problem?

Practice Equal Sum Grid Partition I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays