Skip to content

3142. Check if Grid Satisfies Conditions

Description

You are given a 2D matrix grid of size m x n. You need to check if each cell grid[i][j] is:

  • Equal to the cell below it, i.e. grid[i][j] == grid[i + 1][j] (if it exists).
  • Different from the cell to its right, i.e. grid[i][j] != grid[i][j + 1] (if it exists).

Return true if all the cells satisfy these conditions, otherwise, return false.

 

Example 1:

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

Output: true

Explanation:

All the cells in the grid satisfy the conditions.

Example 2:

Input: grid = [[1,1,1],[0,0,0]]

Output: false

Explanation:

All cells in the first row are equal.

Example 3:

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

Output: false

Explanation:

Cells in the first column have different values.

 

Constraints:

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

Solutions

Solution 1: Simulation

Thinking

Cells must equal the one below and differ from the one to the right. The definition is already a local check.

A single violation rejects the grid, so the scan may exit early.

Walk every cell, compare it with its bottom and right neighbors, and return true only if all pairs obey the rule.

We can iterate through each cell and determine whether it meets the conditions specified in the problem. If there is a cell that does not meet the conditions, we return false, otherwise, we return true.

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix grid respectively. The space complexity is $O(1)`.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if i + 1 < m and x != grid[i + 1][j]:
                    return False
                if j + 1 < n and x == grid[i][j + 1]:
                    return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean satisfiesConditions(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i + 1 < m && grid[i][j] != grid[i + 1][j]) {
                    return false;
                }
                if (j + 1 < n && grid[i][j] == grid[i][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool satisfiesConditions(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i + 1 < m && grid[i][j] != grid[i + 1][j]) {
                    return false;
                }
                if (j + 1 < n && grid[i][j] == grid[i][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func satisfiesConditions(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    for i, row := range grid {
        for j, x := range row {
            if i+1 < m && x != grid[i+1][j] {
                return false
            }
            if j+1 < n && x == grid[i][j+1] {
                return false
            }
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function satisfiesConditions(grid: number[][]): boolean {
    const [m, n] = [grid.length, grid[0].length];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i + 1 < m && grid[i][j] !== grid[i + 1][j]) {
                return false;
            }
            if (j + 1 < n && grid[i][j] === grid[i][j + 1]) {
                return false;
            }
        }
    }
    return true;
}

Comments