Check if Grid Satisfies Conditions solution and explanation
7 more videos on this problem
3142. Check if Grid Satisfies Conditions (Leetcode Easy)Programming Live with Larry · 2:45 · 333 views
Leetcode 3142 Check if Grid Satisfies ConditionsLuc Taylor · 1:40 · 175 views
3142. Check if Grid Satisfies Conditions | LeetCode EASY | MatrixLeet's Code · 7:19 · 174 views
3142. Check if Grid Satisfies Conditions #leetcodequestionandanswers #java #coding #array #2darrayCodeVia · 3:25 · 106 views
Leetcode 3142 - Check if Grid Satisfies ConditionsAzam Jawad · 8:16 · 33 views
Leetcode Biweekly Contest 130 Problem A Check if Grid Satisfies Conditions Solution | Leetcode A solcode conqueror · 0:07 · 23 views
【LeetCode Life 4/50】3142. Check if Grid Satisfies Conditions (~Easy) np.any, np.all for np.array()思臉AI · 1:58 · 8 views
Leetcode easy problem 3142. Check if Grid Satisfies Conditions | devops python practiceADevOpsEngineer · 3:15 · 8 views
The 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:
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 <= 100 <= grid[i][j] <= 9
Approach overview
Problem Overview: You are given a 2D grid. Each column must contain identical values vertically, while adjacent cells in the same row must contain different values horizontally. The task is to verify whether the entire matrix satisfies these two rules.
Approach 1: Iterative Grid Check (Time: O(m*n), Space: O(1))
The most direct way to solve this problem is to iterate through every cell in the matrix and verify both conditions locally. For each position (i, j), compare it with the cell above it (i-1, j) to ensure column values remain the same. Then compare it with the cell to the left (i, j-1) to ensure adjacent horizontal values are different. The moment a violation appears, return false. If the scan finishes without violations, the grid satisfies the constraints.
This approach uses a simple nested loop over the matrix. Each comparison is constant time, so the total runtime is O(m*n), where m is the number of rows and n is the number of columns. Since no additional data structures are required, the space complexity stays O(1). Problems like this commonly appear in array and matrix validation tasks where local adjacency rules determine correctness.
Approach 2: Recursive Grid Check (Time: O(m*n), Space: O(m*n) recursion stack)
A recursive version performs the same validation but moves through the grid using function calls instead of loops. The function checks the current cell against its top and left neighbors, then recursively processes the next cell (moving column by column and row by row). If any rule fails, the recursion immediately stops and returns false.
This approach demonstrates the same logical checks but expressed through recursion rather than iteration. Time complexity remains O(m*n) because every cell is visited once. Space complexity increases due to the recursion stack, potentially reaching O(m*n) in the worst case depending on traversal order. It is mainly useful for practicing recursive traversal of a matrix structure rather than for performance benefits.
Recommended for interviews: The iterative grid check is the expected solution. It is simple, runs in linear time over the matrix, and uses constant extra space. Interviewers typically want to see that you quickly translate the problem constraints into two adjacency checks during iteration. The recursive approach shows conceptual flexibility but does not improve complexity, so it is rarely preferred in production or interview settings.
Approach 1: Iterative Grid Check
The idea is to iterate over each element and check its neighbors. We check for two conditions:
- The element must equal the element directly below it, if one exists.
- The element must not equal the element directly to the right, if one exists.
If any element violates these conditions, the function returns false. If all elements satisfy the conditions, we return true.
def check_grid(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i < m - 1 and grid[i][j] != grid[i + 1][j]:
return False
if j < n - 1 and grid[i][j] == grid[i][j + 1]:
return False
return Truepublic class GridChecker {
public boolean checkGrid(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++) {
if (i < m - 1 && grid[i][j] != grid[i + 1][j]) {
return false;
}
if (j < n - 1 && grid[i][j] == grid[i][j + 1]) {
return false;
}
}
}
return true;
}
}#include <vector>
using namespace std;
bool checkGrid(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i < m - 1 && grid[i][j] != grid[i + 1][j]) return false;
if (j < n - 1 && grid[i][j] == grid[i][j + 1]) return false;
}
}
return true;
}function checkGrid(grid) {
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i < m - 1 && grid[i][j] != grid[i + 1][j]) {
return false;
}
if (j < n - 1 && grid[i][j] === grid[i][j + 1]) {
return false;
}
}
}
return true;
}#include <stdbool.h>
bool checkGrid(int** grid, int gridSize, int* gridColSize) {
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
// Check the cell below
if (i < gridSize - 1 && grid[i][j] != grid[i + 1][j]) {
return false;
}
// Check the cell to the right
if (j < gridColSize[i] - 1 && grid[i][j] == grid[i][j + 1]) {
return false;
}
}
}
return true;
}public class Solution {
public bool CheckGrid(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++) {
if (i < m - 1 && grid[i][j] != grid[i + 1][j]) return false;
if (j < n - 1 && grid[i][j] == grid[i][j + 1]) return false;
}
}
return true;
}
}The Python solution similarly iterates through the grid, checking each condition for bottom and right neighbors. If violations are found, it returns false.
Time Complexity: O(m*n) as each cell is visited once.
Space Complexity: O(1) as no additional space is used.
Approach 2: Recursive Grid Check
The recursive approach involves visiting each cell in the grid perform similar checks as in the iterative method. We use a recursive function to handle each cell and its neighbors, returning false when a condition is violated and true otherwise.
def check_cell(grid, i, j, m, n):
if i < m - 1 and grid[i][j] != grid[i + 1][j]:
return False
if j < n - 1 and grid[i][j] == grid[i][j + 1]:
return False
if i == m - 1 and j == n - 1:
return True
if j == n - 1:
return check_cell(grid, i + 1, 0, m, n)
return check_cell(grid, i, j + 1, m, n)
def check_grid_recursive(grid):
m, n = len(grid), len(grid[0])
return check_cell(grid, 0, 0, m, n)function checkCell(grid, i, j, m, n) {
if (i < m - 1 && grid[i][j] !== grid[i + 1][j]) return false;
if (j < n - 1 && grid[i][j] === grid[i][j + 1]) return false;
if (i === m - 1 && j === n - 1) return true;
if (j === n - 1) return checkCell(grid, i + 1, 0, m, n);
return checkCell(grid, i, j + 1, m, n);
}
function checkGridRecursive(grid) {
const m = grid.length;
const n = grid[0].length;
return checkCell(grid, 0, 0, m, n);
}The recursive Python function check_cell handles each condition for the given cell and moves through the grid using recursive calls, checking each cell one by one.
Time Complexity: O(m*n), each cell is visited once.
Space Complexity: O(1), although the recursion stack may lead to O(m*n) in extreme cases.
Approach 3: Simulation
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)`.
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Grid Check | Time Complexity: O(m*n) as each cell is visited once. |
| Recursive Grid Check | Time Complexity: O(m*n), each cell is visited once. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Grid Check | O(m*n) | O(1) | Best general solution; simple validation using nested loops |
| Recursive Grid Check | O(m*n) | O(m*n) | Useful for practicing recursive traversal of a matrix |
Frequently asked questions
Is Check if Grid Satisfies Conditions easy or hard?
Check if Grid Satisfies Conditions is classified as an Easy problem on LeetCode. The challenge mainly involves translating the problem rules into simple neighbor comparisons while iterating through a matrix.
Check if Grid Satisfies Conditions Python/Java solution
In Python or Java, the solution uses two nested loops to iterate through the grid. For each position (i, j), compare with the cell above for equality and the cell to the left for inequality. If any condition fails, return false; otherwise return true after scanning the entire matrix.
How to solve Check if Grid Satisfies Conditions in O(n)?
Treat the grid as m*n total elements and scan it once using nested loops. For each cell, check vertical equality with grid[i-1][j] and horizontal inequality with grid[i][j-1]. Because each cell is processed once, the overall complexity becomes O(m*n) with constant extra memory.
What is the best approach for Check if Grid Satisfies Conditions?
The iterative grid check is the best approach. Iterate through each cell and verify two rules: the value must match the cell above it and must differ from the cell to its left. This approach runs in O(m*n) time and O(1) extra space, making it optimal for this matrix validation problem.
Is Check if Grid Satisfies Conditions asked at Google/Amazon/Meta?
Matrix validation and adjacency constraint problems frequently appear in coding interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of checking neighboring cells in a grid is a common interview concept.
What data structure is used in Check if Grid Satisfies Conditions?
The primary data structure is a 2D array (matrix). The algorithm performs direct index access to compare neighboring cells vertically and horizontally without requiring additional structures like hash maps or stacks.
What is the time complexity of Check if Grid Satisfies Conditions?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is visited once and only constant-time comparisons with neighboring cells are performed.