Equal Sum Grid Partition I - Practice Coding Problems

Equal Sum Grid Partition I - Problem

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.

Input & Output

Example 1 — Equal Horizontal Partition

$ Input: grid = [[2,4],[2,4]]

› Output: true

💡 Note: Horizontal cut after row 0: top section sum = 2+4 = 6, bottom section sum = 2+4 = 6. Both equal, so return true.

Example 2 — No Equal Partition

$ Input: grid = [[1,2],[3,4]]

› Output: false

💡 Note: Total sum = 10. No horizontal or vertical cut creates equal partitions of 5 each.

Example 3 — Equal Vertical Partition

$ Input: grid = [[1,3],[2,4]]

› Output: true

💡 Note: Vertical cut after column 0: left section sum = 1+2 = 3, right section sum = 3+4 = 7. Not equal. But horizontal cut after row 0: top = 4, bottom = 6. Still not equal. Actually, let's check: left=[1,2]=3, right=[3,4]=7. No equal partition exists.

Constraints

1 ≤ m, n ≤ 100
1 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix with positive integers

Try Cuts

Test horizontal and vertical cuts

Check Equality

Return true if any cut creates equal sums

Key Takeaway

🎯 Key Insight: Check if total sum is even first, then use prefix sums to efficiently test all cuts

Asked in

G Google 25 a Amazon 18 M Microsoft 15 A Apple 12

The key insight is that if the total sum is odd, no equal partition exists. For even sums, use prefix sums to efficiently check all possible cuts. Best approach uses prefix sum optimization with Time: O(mn), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Cuts	O(m²n + mn²)	O(1)	Try every possible horizontal and vertical cut, calculate sums for each partition
Prefix Sum Optimization	O(mn)	O(m + n)	Use prefix sums to calculate partition sums in O(1) time

Brute Force - Try All Cuts — Algorithm Steps

Step 1: Try all horizontal cuts between rows
Step 2: For each cut, sum elements above and below
Step 3: Try all vertical cuts between columns
Step 4: For each cut, sum elements left and right

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Horizontal Cuts

Cut between each pair of rows

Calculate Sums

Sum elements above and below each cut

Try Vertical Cuts

Cut between each pair of columns

Check Equality

Return true if any cut creates equal sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** grid, int m, int n) {
    // Try horizontal cuts
    for (int cutRow = 1; cutRow < m; cutRow++) {
        int topSum = 0, bottomSum = 0;
        
        // Sum top part
        for (int i = 0; i < cutRow; i++) {
            for (int j = 0; j < n; j++) {
                topSum += grid[i][j];
            }
        }
        
        // Sum bottom part
        for (int i = cutRow; i < m; i++) {
            for (int j = 0; j < n; j++) {
                bottomSum += grid[i][j];
            }
        }
        
        if (topSum == bottomSum) return true;
    }
    
    // Try vertical cuts
    for (int cutCol = 1; cutCol < n; cutCol++) {
        int leftSum = 0, rightSum = 0;
        
        // Sum left part
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < cutCol; j++) {
                leftSum += grid[i][j];
            }
        }
        
        // Sum right part
        for (int i = 0; i < m; i++) {
            for (int j = cutCol; j < n; j++) {
                rightSum += grid[i][j];
            }
        }
        
        if (leftSum == rightSum) return true;
    }
    
    return false;
}

int main() {
    char buffer[10000];
    fgets(buffer, sizeof(buffer), stdin);
    
    // Simple parsing for 2D array
    int** grid = NULL;
    int m = 0, n = 0;
    
    // Count rows by counting '],' patterns
    for (int i = 0; buffer[i]; i++) {
        if (buffer[i] == ']' && buffer[i+1] == ',') m++;
    }
    m++; // Last row doesn't have comma
    
    // Allocate grid
    grid = (int**)malloc(m * sizeof(int*));
    
    // Parse numbers
    char* ptr = buffer + 1; // Skip first '['
    for (int i = 0; i < m; i++) {
        ptr++; // Skip '['
        
        // Count numbers in this row
        char* temp = ptr;
        int cols = 1;
        while (*temp != ']') {
            if (*temp == ',') cols++;
            temp++;
        }
        n = cols;
        
        grid[i] = (int*)malloc(n * sizeof(int));
        
        // Parse numbers
        for (int j = 0; j < n; j++) {
            grid[i][j] = strtol(ptr, &ptr, 10);
            if (*ptr == ',') ptr++;
        }
        ptr += 2; // Skip '],' or ']'
    }
    
    bool result = solution(grid, m, n);
    printf(result ? "true\n" : "false\n");
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n + mn²)

For each of m-1 horizontal cuts, sum O(mn) elements. For each of n-1 vertical cuts, sum O(mn) elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to store sums, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Cuts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler