Check if Grid Satisfies Conditions

Difficulty: Easy | Acceptance: 45.20% | Paid: No Topics: Array, Matrix

You are given a 2D grid of size m x n. You need to check if the grid satisfies the following conditions:

1. All cells in each row have the same value.
2. All cells in each column have different values.

Return true if the grid satisfies the conditions, otherwise return false.

• Examples
• Constraints
• Brute Force
• Single Pass
• Using Sets

Examples

Example 1

Input:

grid = [[1,0,2],[1,0,2]]

Output:

false

Explanation:

All cells in row 0 are not the same.

Example 2

Input:

grid = [[1,1],[2,2]]

Output:

true

Explanation:

All cells in each row are the same and all cells in each column are different.

Example 3

Input:

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

Output:

true

Explanation:

All cells in each row are the same (each row has only one cell) and all cells in the column are different.

Constraints

- 1 <= n, m <= 10
- 0 <= grid[i][j] <= 9

Brute Force

Intuition Check each row for uniform values and each column for unique values separately.

Steps

• Iterate through each row and verify all elements match the first element.
• Iterate through each column and use a set to detect duplicates.

from typing import List

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        for i in range(m):
            for j in range(1, n):
                if grid[i][j] != grid[i][0]:
                    return False
        
        for j in range(n):
            seen = set()
            for i in range(m):
                if grid[i][j] in seen:
                    return False
                seen.add(grid[i][j])
        
        return True

Complexity

• Time: O(m × n)
• Space: O(m)
• Notes: Simple and straightforward, but requires two passes through the grid.

Single Pass

Intuition Check both conditions simultaneously while traversing the grid once.

Steps

• Maintain a set for each column to track seen values.
• For each cell, verify row uniformity and column uniqueness.

from typing import List

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        col_values = [set() for _ in range(n)]
        
        for i in range(m):
            row_val = grid[i][0]
            for j in range(n):
                if grid[i][j] != row_val:
                    return False
                if grid[i][j] in col_values[j]:
                    return False
                col_values[j].add(grid[i][j])
        
        return True

Complexity

• Time: O(m × n)
• Space: O(m × n)
• Notes: Single pass through the grid, but uses more space to track column values.

Using Sets

Intuition Use sets to efficiently check row uniformity and column uniqueness.

Steps

• For each row, check if the set of elements has size 1.
• For each column, check if the set of elements has size equal to the number of rows.

from typing import List

class Solution:
    def satisfiesConditions(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        for i in range(m):
            if len(set(grid[i])) != 1:
                return False
        
        for j in range(n):
            col = [grid[i][j] for i in range(m)]
            if len(set(col)) != m:
                return False
        
        return True

Complexity

• Time: O(m × n)
• Space: O(m × n)
• Notes: Clean and readable, but uses more space for creating sets.