# Check if Grid Satisfies Conditions
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-grid-satisfies-conditions)
Canonical: https://scaleengineer.com/dsa/problems/check-if-grid-satisfies-conditions
**Data structures:** Array, Matrix
---
## Problem
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:**

**![](https://assets.glich.co/dsa/check-if-grid-satisfies-conditions/image0.png)**

All the cells in the grid satisfy the conditions.

**Example 2:**

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

**Output:** false

**Explanation:**

**![](https://assets.glich.co/dsa/check-if-grid-satisfies-conditions/image1.png)**

All cells in the first row are equal.

**Example 3:**

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

**Output:** false

**Explanation:**

![](https://assets.glich.co/dsa/check-if-grid-satisfies-conditions/image2.png)

Cells in the first column have different values.

**Constraints:**

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

# Approaches
## Two-Pass Iteration
This approach breaks down the problem into two separate subproblems. First, it iterates through the grid to verify the vertical condition (all elements in a column must be the same). If this condition holds for all columns, it performs a second iteration to verify the horizontal condition (adjacent elements in a row must be different).
**Time:** O(m * n). In the worst-case scenario, the algorithm iterates through the grid twice. The first pass takes O(m * n) time, and the second pass also takes O(m * n) time. The total time complexity is O(m * n) + O(m * n) = O(m * n). · **Space:** O(1). The algorithm uses only a few variables to store the dimensions and loop counters, so the space required is constant and does not depend on the size of the input grid.
**Pros:** The logic is separated into two distinct parts, which can make the code easier to read and understand.; Each part handles exactly one of the problem's conditions.
**Cons:** It is potentially less efficient than a single-pass approach. If a horizontal condition fails (e.g., `grid[0][0] == grid[0][1]`), this approach will still complete the entire vertical check before finding the failure, leading to unnecessary computations.
### Explanation
The algorithm first focuses on the column-wise constraint. It iterates through each column and, within each column, checks if every element is equal to the one directly below it.
The outer loop runs from `j = 0` to `n-1` (columns), and the inner loop runs from `i = 0` to `m-2` (rows, excluding the last).
Inside the inner loop, it checks `if (grid[i][j] != grid[i + 1][j])`. If this condition is ever true, it means a column has different values, so we can immediately return `false`.
If the first set of loops completes successfully, it means all columns satisfy the first condition.
Next, the algorithm checks the row-wise constraint. It iterates through each row and, within each row, checks if any element is equal to the one to its right.
The outer loop runs from `i = 0` to `m-1` (rows), and the inner loop runs from `j = 0` to `n-2` (columns, excluding the last).
Inside this second inner loop, it checks `if (grid[i][j] == grid[i][j + 1])`. If this is true, it violates the second condition, and we return `false`.
If both sets of loops complete without returning `false`, it means all conditions are met for all cells, and we can safely return `true`.
```java
class Solution {
    public boolean satisfiesConditions(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Pass 1: Check vertical condition (grid[i][j] == grid[i + 1][j])
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m - 1; i++) {
                if (grid[i][j] != grid[i + 1][j]) {
                    return false;
                }
            }
        }

        // Pass 2: Check horizontal condition (grid[i][j] != grid[i][j + 1])
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (grid[i][j] == grid[i][j + 1]) {
                    return false;
                }
            }
        }

        return true;
    }
}
```
### Algorithm
*   Get the dimensions of the grid, `m` (rows) and `n` (columns).
*   **First Pass (Vertical Check):**
    *   Iterate through each column `j` from `0` to `n-1`.
    *   Iterate through each row `i` from `0` to `m-2`.
    *   If `grid[i][j]` is not equal to `grid[i+1][j]`, return `false`.
*   **Second Pass (Horizontal Check):**
    *   Iterate through each row `i` from `0` to `m-1`.
    *   Iterate through each column `j` from `0` to `n-2`.
    *   If `grid[i][j]` is equal to `grid[i][j+1]`, return `false`.
*   If both passes complete, return `true`.

## Single-Pass Iteration
This is the most efficient approach. It involves iterating through the grid just once. For each cell, it checks both the vertical and horizontal conditions simultaneously. If any condition is violated at any point, the function immediately returns `false`, which avoids unnecessary checks.
**Time:** O(m * n). The algorithm iterates through each cell of the grid at most once. In the worst case, it visits all `m * n` cells. In the best case, if a condition is violated at `grid[0][0]`, the complexity is O(1). · **Space:** O(1). No extra space proportional to the input size is used. The memory usage is constant.
**Pros:** This is the most time-efficient approach as it combines both checks into a single pass.; It supports 'early exit', meaning it terminates as soon as a condition is violated, which can save significant time on large grids where a violation occurs early.
**Cons:** The logic within the loop is slightly more complex due to handling two conditions and their respective boundary checks simultaneously.
### Explanation
The algorithm iterates through every cell of the grid using nested loops, with the outer loop for rows (`i`) and the inner loop for columns (`j`).
For each cell `grid[i][j]`, it performs two checks:
1.  **Vertical Condition:** It checks if the cell is equal to the one below it. This check is only necessary if there is a cell below, i.e., `i < m - 1`. If `grid[i][j] != grid[i + 1][j]`, the condition is violated, and the function returns `false`.
2.  **Horizontal Condition:** It checks if the cell is different from the one to its right. This check is only necessary if there is a cell to the right, i.e., `j < n - 1`. If `grid[i][j] == grid[i][j + 1]`, the condition is violated, and the function returns `false`.
These checks are performed for each cell. The boundary conditions (`i < m - 1` and `j < n - 1`) are crucial to prevent out-of-bounds errors when accessing `grid[i + 1][j]` and `grid[i][j + 1]`.
If the loops complete without finding any violations, it means all cells in the grid satisfy the given conditions, and the function returns `true`.
```java
class Solution {
    public boolean satisfiesConditions(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Check condition 1: Equal to the cell below
                if (i < m - 1) {
                    if (grid[i][j] != grid[i + 1][j]) {
                        return false;
                    }
                }
                // Check condition 2: Different from the cell to its right
                if (j < n - 1) {
                    if (grid[i][j] == grid[i][j + 1]) {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
}
```
### Algorithm
*   Get the dimensions of the grid, `m` (rows) and `n` (columns).
*   Iterate through each row `i` from `0` to `m-1`.
*   Iterate through each column `j` from `0` to `n-1`.
*   For the current cell `grid[i][j]`:
    *   If a cell below exists (`i < m - 1`), check if `grid[i][j] != grid[i+1][j]`. If true, return `false`.
    *   If a cell to the right exists (`j < n - 1`), check if `grid[i][j] == grid[i][j+1]`. If true, return `false`.
*   If the loops complete without returning `false`, it means all conditions are satisfied. Return `true`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
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;
  }
};

```