Check if Grid Satisfies Conditions

EASY

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

Approaches

Checkout 2 different approaches to solve Check if Grid Satisfies Conditions. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:

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.
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.

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

Complexity Analysis

Time Complexity: 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 Complexity: O(1). No extra space proportional to the input size is used. The memory usage is constant.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check if Grid Satisfies Conditions. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Check if Grid Satisfies Conditions

Data Structures:

ArrayMatrix

Check if Grid Satisfies Conditions

Description

Approaches

Single-Pass Iteration

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Data Structures:

On this page

Subscribe to Scale Engineer newsletter