Check if Grid Satisfies Conditions - Solution & Explanation

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.