Scale Engineer

Check if Grid Satisfies Conditions

Easy
#2791Time: 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.
Data structures
ArrayMatrix

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem