3142. Check if Grid Satisfies Conditions

EasyArrayMatrix

Problem Description

You are given a 2D matrix grid of size m x n. You need to check if each cell grid[i][j] satisfies the following conditions:

It should be equal to the cell below it, i.e., grid[i][j] == grid[i + 1][j] (if a cell below exists).
It should be different from the cell to its right, i.e., grid[i][j] != grid[i][j + 1] (if a cell to the right exists).

Return true if all the cells satisfy these conditions; otherwise, return false.

Intuition

To determine if the grid satisfies the given conditions, we traverse each cell and check its relations to the adjacent cells below and to the right.

For each cell, check if it has a cell directly below it (i + 1 < m). If it does, confirm that it is equal to this below cell (grid[i][j] == grid[i + 1][j]).
For the cell to the right (j + 1 < n), ensure that it is different (grid[i][j] != grid[i][j + 1]).

If we find any cell where these rules are violated, we can immediately conclude that the grid does not satisfy the conditions and return false. If all cells adhere to the rules, true is returned, indicating compliance.

This method efficiently checks the relations by iterating over each cell, minimizing redundant work, and utilizing straightforward comparisons to determine compliance.

Solution Approach

The solution employs a straightforward simulation to verify each cell's compliance with the specified conditions. Here's how the implementation works:

Initialize Dimensions: Determine the number of rows m and columns n of the grid using len(grid) and len(grid[0]), respectively.
Iterate Over Each Cell: Use a nested loop to traverse through each cell in the grid. The outer loop iterates over each row, and the inner loop processes each element within the row.
Check Cell Below: For every cell grid[i][j], check whether it has a neighboring cell directly below it by evaluating i + 1 < m. If true, ensure the current cell is equal to this below cell. If grid[i][j] != grid[i + 1][j], return False immediately, as it violates the condition.
Check Cell to the Right: Similarly, verify if a cell exists to the right by confirming j + 1 < n. If the condition is satisfied, the current cell must be different from this right cell. Should grid[i][j] == grid[i][j + 1], return False, as this condition is not met.
Return True: If the loop completes without returning False, all cells successfully met the conditions, so return True.

This approach efficiently processes the grid by using index-based checks and immediate returns to minimize unnecessary computations, ensuring optimal performance.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a small 3 x 3 grid for illustration:

grid = [
  [1, 2, 3],
  [1, 3, 4],
  [1, 4, 5]
]

Step-by-step Walkthrough

Initialize Dimensions:
- The grid has m = 3 rows and n = 3 columns.
Iterate Over Each Cell:
- Start traversing each cell using a nested loop.
Check Conditions:
- Cell (0,0): Value is 1
  - Below: Cell (1,0) has value 1. Condition satisfied (1 == 1).
  - Right: Cell (0,1) has value 2. Condition satisfied (1 != 2).
- Cell (0,1): Value is 2
  - Below: Cell (1,1) has value 3. Condition violated (2 != 3). However, they don't need to be equal, so this check is skipped.
  - Right: Cell (0,2) has value 3. Condition satisfied (2 != 3).
- Cell (0,2): Value is 3
  - Below: Cell (1,2) has value 4. Condition satisfied (3 != 4). However, they don't need to be equal, so this check is skipped.
  - No cell to the right, so skip this check.
- Cell (1,0): Value is 1
  - Below: Cell (2,0) has value 1. Condition satisfied (1 == 1).
  - Right: Cell (1,1) has value 3. Condition satisfied (1 != 3).
- Cell (1,1): Value is 3
  - Below: Cell (2,1) has value 4. Condition satisfied (3 != 4). However, they don't need to be equal, so this check is skipped.
  - Right: Cell (1,2) has value 4. Condition satisfied (3 != 4).
- Cell (1,2): Value is 4
  - Below: Cell (2,2) has value 5. Condition satisfied (4 != 5). However, they don't need to be equal, so this check is skipped.
  - No cell to the right, so skip this check.
- Cell (2,0): Value is 1
  - No cell below, so skip this check.
  - Right: Cell (2,1) has value 4. Condition satisfied (1 != 4).
- Cell (2,1): Value is 4
  - No cell below, so skip this check.
  - Right: Cell (2,2) has value 5. Condition satisfied (4 != 5).
- Cell (2,2): Value is 5
  - No cell below or to the right, so skip these checks.
Return Result:
- The traversal completes without finding any cell violating the conditions. Therefore, the function returns True.

This walkthrough shows that each cell was checked for compliance with the conditions, leading to a valid grid.

Solution Implementation

1from typing import List
2
3class Solution:
4    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
5        # Obtain the number of rows (m) and columns (n) in the grid
6        m, n = len(grid), len(grid[0])
7      
8        # Iterate over each element in the grid by rows and columns
9        for i, row in enumerate(grid):
10            for j, value in enumerate(row):
11                # Check if there's a row below and the current element is not equal to the element directly below
12                if i + 1 < m and value != grid[i + 1][j]:
13                    return False
14                # Check if there's a column to the right and the current element equals the element to the right
15                if j + 1 < n and value == grid[i][j + 1]:
16                    return False
17      
18        # If all conditions are satisfied, return True
19        return True
20

1class Solution {
2    public boolean satisfiesConditions(int[][] grid) {
3        int rows = grid.length; // Number of rows in the grid
4        int columns = grid[0].length; // Number of columns in the grid
5      
6        // Iterate through each cell in the grid
7        for (int row = 0; row < rows; ++row) {
8            for (int col = 0; col < columns; ++col) {
9              
10                // Check the condition between the current cell and the cell directly below it
11                if (row + 1 < rows && grid[row][col] != grid[row + 1][col]) {
12                    return false; // Condition fails, return false
13                }
14              
15                // Check the condition between the current cell and the cell directly to its right
16                if (col + 1 < columns && grid[row][col] == grid[row][col + 1]) {
17                    return false; // Condition fails, return false
18                }
19            }
20        }
21      
22        // All conditions are satisfied, return true
23        return true;
24    }
25}
26

1#include <vector>
2
3class Solution {
4public:
5    // Method to check if the grid satisfies certain conditions
6    bool satisfiesConditions(std::vector<std::vector<int>>& grid) {
7        int rows = grid.size();    // Number of rows in the grid
8        int cols = grid[0].size(); // Number of columns in the grid
9
10        // Iterate over each element in the grid
11        for (int row = 0; row < rows; ++row) {
12            for (int col = 0; col < cols; ++col) {
13                // Check if the current element is different from the element directly below it
14                if (row + 1 < rows && grid[row][col] != grid[row + 1][col]) {
15                    return false;
16                }
17                // Check if the current element is the same as the element to its right
18                if (col + 1 < cols && grid[row][col] == grid[row][col + 1]) {
19                    return false;
20                }
21            }
22        }
23        // All conditions are satisfied
24        return true;
25    }
26};
27

1function satisfiesConditions(grid: number[][]): boolean {
2    // Determine the dimensions of the grid
3    const [rows, cols] = [grid.length, grid[0].length];
4
5    // Traverse the grid row-wise and column-wise
6    for (let row = 0; row < rows; ++row) {
7        for (let col = 0; col < cols; ++col) {
8
9            // Check the condition for vertical neighbors
10            // Ensure current cell is not the last row before checking below
11            if (row + 1 < rows && grid[row][col] !== grid[row + 1][col]) {
12                return false; // Return false if vertical neighbors are not equal
13            }
14
15            // Check the condition for horizontal neighbors
16            // Ensure current cell is not the last column before checking right
17            if (col + 1 < cols && grid[row][col] === grid[row][col + 1]) {
18                return false; // Return false if horizontal neighbors are equal
19            }
20        }
21    }
22
23    // Return true if all conditions are satisfied
24    return true;
25}
26

Time and Space Complexity

The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the matrix grid. This is because the algorithm iterates over each element of the grid once.

The space complexity is O(1) as the solution does not utilize any additional data structures whose size grows with the input.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know