You are given a 2D matrix grid of size m x n. You need to check if each cell grid[i][j] is:
grid[i][j] == grid[i + 1][j] (if it exists).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] <= 9Problem 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.
The idea is to iterate over each element and check its neighbors. We check for two conditions:
If any element violates these conditions, the function returns false. If all elements satisfy the conditions, we return true.
This C function uses nested loops to iterate over the grid. For each cell, it checks if the below or right conditions are violated. If so, it returns false. If all checks pass, it returns true.
Time Complexity: O(m*n) as each cell is visited once.
Space Complexity: O(1) as no additional space is used.
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.
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.
Python
JavaScript
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.
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)`.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
3142. Check if Grid Satisfies Conditions (Leetcode Easy) • Programming Live with Larry • 328 views views
Watch 4 more video solutions →Practice Check if Grid Satisfies Conditions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor