Equal Sum Grid Partition I

Intuition #

A valid partition exists if a cut can divide the grid such that both resulting sections have equal sums. By converting rows or columns into their individual sums, the 2D problem reduces to finding a partition point in a 1D array where the left sum equals the right sum.

Approach #

The solution checks both horizontal and vertical partitions:

• Calculate row sums: Sum each row to create an array representing potential horizontal cuts.

• Create canPartitionArray helper function to check whether we can partition a 1D array.

• Check row partition: Use canPartitionArray to find if any cut point divides the row sums equally.

• Calculate column sums: Sum each column to create an array representing potential vertical cuts.

• Check column partition: Use canPartitionArray to find if any cut point divides the column sums equally.

• Return true if either partition works.

Complexity #

• Time complexity: $O(M × N)$

  • Computing row sums is $O(M × N)$. Computing column sums is $O(M × N)$. Checking partitions is $O(M) + O(N)$. Total: $O(M × N)$.

• Space complexity: $O(M+N)$

  • Storage for rowSum ($O(M)$) and colSum ($O(N)$), plus prefix arrays of the same sizes. Overall: $O(M + N)$.

Code #

 1func canPartitionGrid(grid [][]int) bool {
 2	rowSum := make([]int, len(grid))
 3	for y, row := range grid {
 4		sum := 0
 5		for _, num := range row {
 6			sum += num
 7		}
 8		rowSum[y] = sum
 9	}
10
11	if canPartitionArray(rowSum) {
12		return true
13	}
14
15	colSum := make([]int, len(grid[0]))
16	for x := range grid[0] {
17		sum := 0
18		for y := range grid {
19			sum += grid[y][x]
20		}
21		colSum[x] = sum
22	}
23
24	return canPartitionArray(colSum)
25}
26
27func canPartitionArray(nums []int) bool {
28	prefix := make([]int, len(nums))
29	prefix[0] = nums[0]
30	for i := 1; i < len(nums); i++ {
31		prefix[i] = prefix[i-1] + nums[i]
32	}
33
34	for i := range prefix {
35		if prefix[i] == prefix[len(prefix)-1]-prefix[i] {
36			return true
37		}
38	}
39
40	return false
41}

Improving canPartitionArray() #

Space complexity can be improved from $O(N)$ to $O(1)$ by using a single variable instead of storing the entire prefix array.

First, calculate the total sum of the array. Then, instead of saving all prefix sums in an array, keep track of just the left sum using one variable as you go through the array. At each step, check if the left sum equals the right sum (the total minus the left sum). When they’re equal, a partition exists. This saves memory by not needing an array, while still taking the same amount of time to check all possible cuts.

 1func canPartitionArray(nums []int) bool {
 2	total := 0
 3	for _, num := range nums {
 4		total += num
 5	}
 6
 7	prefix := 0
 8	for i := 1; i < len(nums); i++ {
 9		prefix += nums[i-1]
10		if total-prefix == prefix {
11			return true
12		}
13	}
14
15	return false
16}