Check if Grid Satisfies Conditions - Practice Coding Problems

Check if Grid Satisfies Conditions - Problem

Array Matrix Easy

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.

Input & Output

Example 1 — Valid Grid

$ Input: grid = [[1,0,2],[1,0,2]]

› Output: true

💡 Note: All cells in each column are equal (1,1), (0,0), (2,2). Adjacent columns differ: 1≠0, 0≠2. All conditions satisfied.

Example 2 — Invalid Vertical

$ Input: grid = [[1,1,1],[0,0,0]]

› Output: false

💡 Note: Column values are not uniform: grid[0][0]=1 but grid[1][0]=0. Also adjacent columns are same: grid[0][0]==grid[0][1]. Fails both conditions.

Example 3 — Invalid Horizontal

$ Input: grid = [[1],[2]]

› Output: true

💡 Note: Single column grid: grid[0][0]=1 equals grid[1][0]=2 is false, but there's no cell below grid[1][0], so vertical condition vacuously true. No right neighbors, so horizontal condition vacuously true.

Constraints

1 ≤ m, n ≤ 10
1 ≤ grid[i][j] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix with specific structure requirements

Check Conditions

Vertical equality and horizontal difference

Output

Boolean result of validation

Key Takeaway

🎯 Key Insight: Grid is valid if columns are uniform and adjacent columns differ

Asked in

G Google 12 f Meta 8 M Microsoft 6

The key insight is that each column must be uniform (all same values) and adjacent columns must differ. Best approach is single-pass validation checking both conditions per cell. Time: O(m×n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Column-wise Validation	O(m×n)	O(1)	Check columns first, then validate horizontal differences
Brute Force - Check Every Cell	O(m×n)	O(1)	Iterate through each cell and validate both conditions

Optimized - Column-wise Validation — Algorithm Steps

Step 1: For each column, check all elements are identical
Step 2: For each position, check adjacent columns differ
Step 3: Return false on first violation, true if all pass

Visualization

Tap to expand

Step-by-Step Walkthrough

Column Check

Verify each column has uniform values

Adjacent Check

Verify adjacent columns differ

Result

Return validation result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** grid, int m, int n) {
    // First pass: Check column uniformity
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m - 1; i++) {
            if (grid[i][j] != grid[i + 1][j]) {
                return false;
            }
        }
    }
    
    // Second pass: Check adjacent columns differ
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (grid[i][j] == grid[i][j + 1]) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** grid = malloc(100 * sizeof(int*));
    int m = 0, n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            grid[m] = malloc(100 * sizeof(int));
            int j = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[m][j++] = strtol(ptr, &ptr, 10);
                } else {
                    ptr++;
                }
            }
            if (m == 0) n = j;
            m++;
        }
        ptr++;
    }
    
    bool result = solution(grid, m, n);
    printf(result ? "true\n" : "false\n");
    
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Must check every cell at least once for validation

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for indices

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Column-wise Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler