LeetCode 3142 - Check if Grid Satisfies Conditions

The problem gives us a two dimensional matrix called grid with m rows and n columns. We must verify whether every cell satisfies two separate rules. The first rule applies vertically. For every cell, if there is a cell directly below it, both values must be equal.

leetcodeeasyarraymatrix

LeetCode Problem 3142

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional matrix called grid with m rows and n columns. We must verify whether every cell satisfies two separate rules.

The first rule applies vertically. For every cell, if there is a cell directly below it, both values must be equal. In other words:

grid[i][j] == grid[i + 1][j]

The second rule applies horizontally. For every cell, if there is a cell directly to its right, the two values must be different. In other words:

grid[i][j] != grid[i][j + 1]

We return true only if every valid cell in the matrix satisfies both conditions. If even one condition fails anywhere in the grid, we immediately return false.

The input represents a small matrix of integers. The constraints are very small:

  • 1 <= m, n <= 10
  • 0 <= grid[i][j] <= 9

Since the matrix can contain at most 100 cells, performance is not a concern. Even a straightforward scan through the matrix is more than fast enough.

There are several important edge cases to consider.

A grid with only one row has no cells below any position, so only the horizontal condition matters.

A grid with only one column has no cells to the right, so only the vertical condition matters.

A 1 x 1 grid automatically satisfies both conditions because neither neighboring cell exists.

Another possible source of bugs is accidentally accessing out of bounds indices when checking the bottom or right neighbor. A correct implementation must verify that the neighbor exists before comparing values.

Approaches

Brute Force Approach

The brute force solution checks every cell individually and validates both conditions whenever the neighboring cells exist.

For each position (i, j):

  • If i + 1 < m, compare the current value with the value below it.
  • If j + 1 < n, compare the current value with the value to the right.

If any comparison violates the required rule, we return false immediately. Otherwise, after checking the entire matrix, we return true.

This approach is already efficient because the constraints are tiny. Every cell is visited once, and each visit performs at most two comparisons.

Key Insight Behind the Optimal Solution

The optimal solution is essentially the same as the brute force solution because the problem itself only requires local neighbor validation.

There is no need for additional preprocessing, dynamic programming, graph traversal, or auxiliary data structures. The conditions depend only on adjacent cells, so a direct scan of the matrix is sufficient.

The key observation is that each column must contain identical values from top to bottom, while adjacent cells within a row must alternate between different values.

Because each rule only involves neighboring cells, one pass through the matrix is enough to verify the entire structure.

Approach Time Complexity Space Complexity Notes
Brute Force O(m × n) O(1) Directly checks every cell and its neighbors
Optimal O(m × n) O(1) Single traversal with immediate validation

Algorithm Walkthrough

  1. Determine the dimensions of the matrix.

Let m be the number of rows and n be the number of columns. We will iterate through every cell in the grid. 2. Traverse every cell in row-major order.

Use nested loops:

  • Outer loop iterates through rows using index i
  • Inner loop iterates through columns using index j
  1. Check the vertical condition.

If a bottom neighbor exists, meaning i + 1 < m, compare:

grid[i][j] == grid[i + 1][j]

If the values are different, the condition fails immediately, so return false. 4. Check the horizontal condition.

If a right neighbor exists, meaning j + 1 < n, compare:

grid[i][j] != grid[i][j + 1]

If the values are equal, the condition fails immediately, so return false. 5. Continue scanning until all cells are processed.

If no violations are found after checking the entire matrix, return true.

Why it works

The algorithm explicitly verifies every condition required by the problem. Every valid vertical neighbor pair is checked exactly once, and every valid horizontal neighbor pair is checked exactly once.

If the algorithm returns false, then at least one rule was violated, so the grid does not satisfy the conditions.

If the algorithm finishes without finding a violation, then every neighbor relationship satisfies the required constraints, so the grid is valid.

Python Solution

from typing import List

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):
                # Check cell below
                if row + 1 < rows:
                    if grid[row][col] != grid[row + 1][col]:
                        return False

                # Check cell to the right
                if col + 1 < cols:
                    if grid[row][col] == grid[row][col + 1]:
                        return False

        return True

The implementation starts by determining the number of rows and columns in the matrix.

The nested loops iterate through every cell exactly once. For each cell, the code performs two conditional checks.

The first conditional ensures that a bottom neighbor exists before comparing values vertically. If the values differ, the function immediately returns False.

The second conditional ensures that a right neighbor exists before comparing values horizontally. If the values are equal, the function immediately returns False.

If the loops complete without finding any invalid pair, the function returns True, meaning the grid satisfies all conditions.

Go Solution

func satisfiesConditions(grid [][]int) bool {
    rows := len(grid)
    cols := len(grid[0])

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {

            // Check cell below
            if row+1 < rows {
                if grid[row][col] != grid[row+1][col] {
                    return false
                }
            }

            // Check cell to the right
            if col+1 < cols {
                if grid[row][col] == grid[row][col+1] {
                    return false
                }
            }
        }
    }

    return true
}

The Go implementation follows the same logic as the Python version.

Go slices are used to represent the matrix. Since the constraints guarantee at least one row and one column, accessing grid[0] is always safe.

No special handling for integer overflow is required because all values are small single digit integers.

The algorithm uses constant extra space and performs direct neighbor comparisons exactly as in the Python solution.

Worked Examples

Example 1

grid = [
    [1, 0, 2],
    [1, 0, 2]
]

We iterate through each cell.

Position Current Value Bottom Check Right Check Result
(0,0) 1 1 == 1 1 != 0 Valid
(0,1) 0 0 == 0 0 != 2 Valid
(0,2) 2 2 == 2 No right cell Valid
(1,0) 1 No bottom cell 1 != 0 Valid
(1,1) 0 No bottom cell 0 != 2 Valid
(1,2) 2 No bottom cell No right cell Valid

No condition fails, so the answer is true.

Example 2

grid = [
    [1, 1, 1],
    [0, 0, 0]
]

Start scanning from the top-left cell.

Position Current Value Bottom Check Right Check Result
(0,0) 1 1 != 0 Not checked further Invalid

The vertical condition fails immediately because the cell below contains 0 instead of 1.

The algorithm returns false.

Example 3

grid = [
    [1],
    [2],
    [3]
]

Only vertical checks exist because there is one column.

Position Current Value Bottom Check Result
(0,0) 1 1 != 2 Invalid

The first vertical comparison fails, so the algorithm returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every cell is visited once
Space O(1) Only a few variables are used

The algorithm processes each matrix cell exactly one time. Each iteration performs at most two constant time comparisons, so the total runtime is proportional to the number of cells in the grid.

No auxiliary data structures are used. The implementation only stores loop indices and dimension variables, so the extra space usage is constant.

Test Cases

from typing import List

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):

                if row + 1 < rows:
                    if grid[row][col] != grid[row + 1][col]:
                        return False

                if col + 1 < cols:
                    if grid[row][col] == grid[row][col + 1]:
                        return False

        return True

sol = Solution()

# Provided examples
assert sol.satisfiesConditions([[1, 0, 2], [1, 0, 2]]) is True  # valid grid
assert sol.satisfiesConditions([[1, 1, 1], [0, 0, 0]]) is False  # horizontal equality violation
assert sol.satisfiesConditions([[1], [2], [3]]) is False  # vertical mismatch

# Single cell grid
assert sol.satisfiesConditions([[5]]) is True  # no neighbors exist

# Single row valid
assert sol.satisfiesConditions([[1, 2, 1, 2]]) is True  # adjacent cells differ

# Single row invalid
assert sol.satisfiesConditions([[1, 1, 2]]) is False  # equal horizontal neighbors

# Single column valid
assert sol.satisfiesConditions([[7], [7], [7]]) is True  # all vertical values equal

# Single column invalid
assert sol.satisfiesConditions([[7], [8], [7]]) is False  # vertical mismatch

# Larger valid grid
assert sol.satisfiesConditions([
    [1, 0, 1],
    [1, 0, 1],
    [1, 0, 1]
]) is True  # valid repeating columns

# Larger invalid grid
assert sol.satisfiesConditions([
    [1, 0, 1],
    [1, 1, 1],
    [1, 0, 1]
]) is False  # middle row breaks horizontal rule
Test Why
[[1,0,2],[1,0,2]] Valid example from the problem
[[1,1,1],[0,0,0]] Tests horizontal equality violation
[[1],[2],[3]] Tests vertical mismatch
[[5]] Smallest possible grid
[[1,2,1,2]] Valid single row case
[[1,1,2]] Invalid adjacent horizontal values
[[7],[7],[7]] Valid single column case
[[7],[8],[7]] Invalid vertical consistency
Larger repeating grid Confirms correct handling of multiple rows and columns
Grid with broken middle row Tests mixed valid and invalid relationships

Edge Cases

A very important edge case is a 1 x 1 grid. Since there are no neighboring cells either below or to the right, no comparisons need to be made. A careless implementation might incorrectly assume neighbors always exist and access invalid indices. This implementation safely checks boundary conditions before every comparison.

Another important case is a single row matrix. In this scenario, vertical comparisons never occur because no cell has a bottom neighbor. Only horizontal inequality matters. The implementation handles this naturally because the vertical check only runs when row + 1 < rows.

A single column matrix is also important. Here, horizontal comparisons never occur because no right neighbors exist. Only vertical equality matters. The implementation correctly skips horizontal checks whenever col + 1 >= cols.

A subtle edge case occurs when the grid is almost valid but fails late in the traversal. For example:

[
    [1, 0, 1],
    [1, 0, 1],
    [1, 1, 1]
]

Most comparisons succeed until the final row introduces a horizontal equality violation. The algorithm continues scanning until it finds the exact violation and immediately returns false.

Another possible bug source is checking the same neighbor pair multiple times or mixing up the conditions. The implementation avoids this by only checking downward and rightward neighbors, ensuring every relevant pair is validated exactly once.