Validate grid balanced

Question

Given a 2D grid of integers, write a function to determine if the grid is balanced, meaning that the sum of each row is equal to the sum of each corresponding column. The function should return a boolean value: true if the grid is balanced, and false otherwise.

Codemia · Accepted Answer

To determine if a 2D grid is balanced, we need to compare the sum of each row with the corresponding column sum. This suggests a straightforward approach where we can utilize two separate accumulators for row sums and column sums. The two-pointer technique is not directly applicable here, but we can think of this problem in terms of iterating over the grid and collecting sums, which is a direct comparison of data structures (rows vs. columns).

1. Initialize two lists: `row_sums` to store the sum of each row and `col_sums` to store the sum of each column.  
2. Loop through each element of the grid using nested loops (outer loop for rows and inner loop for columns).  
3. For each element at position `(i, j)`, add its value to `row_sums[i]` and `col_sums[j]`.  
4. After populating both lists, compare `row_sums` and `col_sums`. If they are equal, return `True`; otherwise, return `False`.  
**Example:** For a grid like `[[1, 2, 3], [4, 5, 6], [7, 8, 9]]`:  
- Row sums would be `[6, 15, 24]` and column sums would be `[12, 15, 18]`, thus returning `False`.

```python
def is_grid_balanced(grid):
    if not grid or not grid[0]:  # Handle empty grid
        return True
    row_count = len(grid)
    col_count = len(grid[0])
    row_sums = [0] * row_count
    col_sums = [0] * col_count

for i in range(row_count):
        for j in range(col_count):
            row_sums[i] += grid[i][j]
            col_sums[j] += grid[i][j]

return row_sums == col_sums
```

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we iterate through each element of the grid exactly once. The space complexity is O(m + n) due to the storage of the `row_sums` and `col_sums` lists, which are proportional to the number of rows and columns.

1. **Empty Input:** If the grid is empty (`[]`), the function should return `True` since there are no sums to compare.  
2. **Single Element:** A grid with a single element like `[[5]]` should return `True` because the row and column sums are equal (both are 5).  
3. **Unequal Dimensions:** A grid like `[[1, 2], [3]]` (non-rectangular) should be handled gracefully — the function should ensure each row has the same number of columns.  
4. **Negative Numbers:** The function should also handle negative sums correctly, e.g. `[[1, -1], [-1, 1]]` should return `True`.

Validate grid balanced

OpenAI

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

OpenAI Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string