Problem

A typical American-style crossword puzzle grid is an N x N matrix with black and white squares, which obeys the following rules:

  • Every white square must be part of an “across” word and a “down” word.
  • No word can be fewer than three letters long.
  • Every white square must be reachable from every other white square.
  • The grid is rotationally symmetric (for example, the colors of the top left and bottom right squares must match).

Write a program to determine whether a given matrix qualifies as a crossword grid.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: 
grid = [
  [1, 1, 1],
  [1, 0, 1], 
  [1, 1, 1]
]
(1 = white, 0 = black)
Output: true
Explanation:
- All white squares form valid across and down words of length 3
- Grid is rotationally symmetric around center
- All white squares are connected
- All words are at least 3 letters long

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input:
grid = [
  [1, 1, 0],
  [1, 0, 1],
  [0, 1, 1]
]
Output: false
Explanation:
- Grid is not rotationally symmetric
- Top-left is white (1) but bottom-right is white (1) - should match
- Top-right is black (0) but bottom-left is black (0) - this matches
- But when rotated 180°, pattern doesn't match original

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input:
grid = [
  [1, 1, 1, 1],
  [1, 0, 0, 1],
  [1, 0, 0, 1], 
  [1, 1, 1, 1]
]
Output: false
Explanation:
- Rotationally symmetric: ✓
- Contains words shorter than 3 letters: the isolated corner squares form 1-letter "words"
- Middle white squares don't form valid across/down words of length ≥3

Example 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input:
grid = [
  [1, 1, 1, 0, 1],
  [1, 0, 1, 0, 1],
  [1, 1, 1, 1, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 1, 1, 1]
]
Output: true
Explanation:
- Rotationally symmetric: ✓
- All white squares reachable from each other: ✓
- All words are at least 3 letters long: ✓
- Each white square part of valid across and down words: ✓

Example 5

1
2
3
4
5
6
7
8
9

Input:
grid = [
  [1, 1],
  [1, 1]
]
Output: false
Explanation:
- Although rotationally symmetric and all squares connected
- Words are only 2 letters long, violating minimum length requirement

Solution

Method 1 - Comprehensive Rule Validation

Intuition

We need to validate each rule systematically: check rotational symmetry first (quick elimination), then verify connectivity using DFS/BFS, and finally ensure all words meet the minimum length requirement. Each white square must be part of both horizontal and vertical words of at least 3 letters.

Approach

  1. Check rotational symmetry by comparing grid[i][j] with grid[n-1-i][n-1-j] for all positions
  2. Find all white squares and verify connectivity using DFS from any white square
  3. Extract all horizontal and vertical words from the grid
  4. Ensure every white square belongs to words of length ≥ 3 in both directions
  5. Validate that isolated segments don’t create invalid short words

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

class Solution {
private:
    vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    bool isValidPosition(int r, int c, int n) {
        return r >= 0 && r < n && c >= 0 && c < n;
    }
    
    bool checkRotationalSymmetry(vector<vector<int>>& grid) {
        int n = grid.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != grid[n-1-i][n-1-j]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool checkConnectivity(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        
        // Find first white square
        int startR = -1, startC = -1;
        int whiteCount = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    whiteCount++;
                    if (startR == -1) {
                        startR = i;
                        startC = j;
                    }
                }
            }
        }
        
        if (whiteCount == 0) return true; // No white squares
        
        // DFS from first white square
        function<void(int, int)> dfs = [&](int r, int c) {
            visited[r][c] = true;
            for (auto& dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (isValidPosition(nr, nc, n) && !visited[nr][nc] && grid[nr][nc] == 1) {
                    dfs(nr, nc);
                }
            }
        };
        
        dfs(startR, startC);
        
        // Check if all white squares visited
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    bool checkWordLengths(vector<vector<int>>& grid) {
        int n = grid.size();
        
        // Check horizontal words
        for (int i = 0; i < n; i++) {
            vector<int> wordLengths;
            int currentLength = 0;
            
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    currentLength++;
                } else {
                    if (currentLength > 0) {
                        wordLengths.push_back(currentLength);
                        currentLength = 0;
                    }
                }
            }
            if (currentLength > 0) {
                wordLengths.push_back(currentLength);
            }
            
            for (int len : wordLengths) {
                if (len < 3) return false;
            }
        }
        
        // Check vertical words
        for (int j = 0; j < n; j++) {
            vector<int> wordLengths;
            int currentLength = 0;
            
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    currentLength++;
                } else {
                    if (currentLength > 0) {
                        wordLengths.push_back(currentLength);
                        currentLength = 0;
                    }
                }
            }
            if (currentLength > 0) {
                wordLengths.push_back(currentLength);
            }
            
            for (int len : wordLengths) {
                if (len < 3) return false;
            }
        }
        
        return true;
    }
    
public:
    bool isValidCrossword(vector<vector<int>>& grid) {
        if (grid.empty()) return false;
        
        int n = grid.size();
        if (n < 3) return false; // Minimum size for 3-letter words
        
        // Rule 4: Check rotational symmetry
        if (!checkRotationalSymmetry(grid)) {
            return false;
        }
        
        // Rule 3: Check connectivity
        if (!checkConnectivity(grid)) {
            return false;
        }
        
        // Rule 2: Check word lengths
        if (!checkWordLengths(grid)) {
            return false;
        }
        
        return true;
    }
};
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

func isValidCrossword(grid [][]int) bool {
    if len(grid) == 0 {
        return false
    }
    
    n := len(grid)
    if n < 3 {
        return false
    }
    
    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    
    isValidPosition := func(r, c, n int) bool {
        return r >= 0 && r < n && c >= 0 && c < n
    }
    
    // Check rotational symmetry
    checkRotationalSymmetry := func() bool {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if grid[i][j] != grid[n-1-i][n-1-j] {
                    return false
                }
            }
        }
        return true
    }
    
    // Check connectivity
    checkConnectivity := func() bool {
        visited := make([][]bool, n)
        for i := range visited {
            visited[i] = make([]bool, n)
        }
        
        startR, startC := -1, -1
        whiteCount := 0
        
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if grid[i][j] == 1 {
                    whiteCount++
                    if startR == -1 {
                        startR, startC = i, j
                    }
                }
            }
        }
        
        if whiteCount == 0 {
            return true
        }
        
        var dfs func(r, c int)
        dfs = func(r, c int) {
            visited[r][c] = true
            for _, dir := range dirs {
                nr, nc := r+dir[0], c+dir[1]
                if isValidPosition(nr, nc, n) && !visited[nr][nc] && grid[nr][nc] == 1 {
                    dfs(nr, nc)
                }
            }
        }
        
        dfs(startR, startC)
        
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if grid[i][j] == 1 && !visited[i][j] {
                    return false
                }
            }
        }
        
        return true
    }
    
    // Check word lengths
    checkWordLengths := func() bool {
        // Check horizontal words
        for i := 0; i < n; i++ {
            var wordLengths []int
            currentLength := 0
            
            for j := 0; j < n; j++ {
                if grid[i][j] == 1 {
                    currentLength++
                } else {
                    if currentLength > 0 {
                        wordLengths = append(wordLengths, currentLength)
                        currentLength = 0
                    }
                }
            }
            if currentLength > 0 {
                wordLengths = append(wordLengths, currentLength)
            }
            
            for _, length := range wordLengths {
                if length < 3 {
                    return false
                }
            }
        }
        
        // Check vertical words
        for j := 0; j < n; j++ {
            var wordLengths []int
            currentLength := 0
            
            for i := 0; i < n; i++ {
                if grid[i][j] == 1 {
                    currentLength++
                } else {
                    if currentLength > 0 {
                        wordLengths = append(wordLengths, currentLength)
                        currentLength = 0
                    }
                }
            }
            if currentLength > 0 {
                wordLengths = append(wordLengths, currentLength)
            }
            
            for _, length := range wordLengths {
                if length < 3 {
                    return false
                }
            }
        }
        
        return true
    }
    
    // Validate all rules
    if !checkRotationalSymmetry() {
        return false
    }
    
    if !checkConnectivity() {
        return false
    }
    
    if !checkWordLengths() {
        return false
    }
    
    return true
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

class Solution {
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    private boolean isValidPosition(int r, int c, int n) {
        return r >= 0 && r < n && c >= 0 && c < n;
    }
    
    private boolean checkRotationalSymmetry(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != grid[n-1-i][n-1-j]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean checkConnectivity(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        
        int startR = -1, startC = -1;
        int whiteCount = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    whiteCount++;
                    if (startR == -1) {
                        startR = i;
                        startC = j;
                    }
                }
            }
        }
        
        if (whiteCount == 0) return true;
        
        dfs(grid, visited, startR, startC, n);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private void dfs(int[][] grid, boolean[][] visited, int r, int c, int n) {
        visited[r][c] = true;
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (isValidPosition(nr, nc, n) && !visited[nr][nc] && grid[nr][nc] == 1) {
                dfs(grid, visited, nr, nc, n);
            }
        }
    }
    
    private boolean checkWordLengths(int[][] grid) {
        int n = grid.length;
        
        // Check horizontal words
        for (int i = 0; i < n; i++) {
            List<Integer> wordLengths = new ArrayList<>();
            int currentLength = 0;
            
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    currentLength++;
                } else {
                    if (currentLength > 0) {
                        wordLengths.add(currentLength);
                        currentLength = 0;
                    }
                }
            }
            if (currentLength > 0) {
                wordLengths.add(currentLength);
            }
            
            for (int len : wordLengths) {
                if (len < 3) return false;
            }
        }
        
        // Check vertical words
        for (int j = 0; j < n; j++) {
            List<Integer> wordLengths = new ArrayList<>();
            int currentLength = 0;
            
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    currentLength++;
                } else {
                    if (currentLength > 0) {
                        wordLengths.add(currentLength);
                        currentLength = 0;
                    }
                }
            }
            if (currentLength > 0) {
                wordLengths.add(currentLength);
            }
            
            for (int len : wordLengths) {
                if (len < 3) return false;
            }
        }
        
        return true;
    }
    
    public boolean isValidCrossword(int[][] grid) {
        if (grid == null || grid.length == 0) return false;
        
        int n = grid.length;
        if (n < 3) return false;
        
        if (!checkRotationalSymmetry(grid)) {
            return false;
        }
        
        if (!checkConnectivity(grid)) {
            return false;
        }
        
        if (!checkWordLengths(grid)) {
            return false;
        }
        
        return true;
    }
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

class Solution:
    def __init__(self):
        self.dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def _is_valid_position(self, r: int, c: int, n: int) -> bool:
        return 0 <= r < n and 0 <= c < n
    
    def _check_rotational_symmetry(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if grid[i][j] != grid[n-1-i][n-1-j]:
                    return False
        return True
    
    def _check_connectivity(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        visited = [[False] * n for _ in range(n)]
        
        start_r, start_c = -1, -1
        white_count = 0
        
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    white_count += 1
                    if start_r == -1:
                        start_r, start_c = i, j
        
        if white_count == 0:
            return True
        
        def dfs(r: int, c: int) -> None:
            visited[r][c] = True
            for dr, dc in self.dirs:
                nr, nc = r + dr, c + dc
                if (self._is_valid_position(nr, nc, n) and 
                    not visited[nr][nc] and grid[nr][nc] == 1):
                    dfs(nr, nc)
        
        dfs(start_r, start_c)
        
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    return False
        
        return True
    
    def _check_word_lengths(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        
        # Check horizontal words
        for i in range(n):
            word_lengths = []
            current_length = 0
            
            for j in range(n):
                if grid[i][j] == 1:
                    current_length += 1
                else:
                    if current_length > 0:
                        word_lengths.append(current_length)
                        current_length = 0
            
            if current_length > 0:
                word_lengths.append(current_length)
            
            for length in word_lengths:
                if length < 3:
                    return False
        
        # Check vertical words
        for j in range(n):
            word_lengths = []
            current_length = 0
            
            for i in range(n):
                if grid[i][j] == 1:
                    current_length += 1
                else:
                    if current_length > 0:
                        word_lengths.append(current_length)
                        current_length = 0
            
            if current_length > 0:
                word_lengths.append(current_length)
            
            for length in word_lengths:
                if length < 3:
                    return False
        
        return True
    
    def is_valid_crossword(self, grid: List[List[int]]) -> bool:
        if not grid or len(grid) == 0:
            return False
        
        n = len(grid)
        if n < 3:
            return False
        
        if not self._check_rotational_symmetry(grid):
            return False
        
        if not self._check_connectivity(grid):
            return False
        
        if not self._check_word_lengths(grid):
            return False
        
        return True

Complexity

  • ⏰ Time complexity: O(n²), where n is the grid size. Each validation step requires O(n²) time to examine all cells
  • 🧺 Space complexity: O(n²) for the visited array during connectivity check and recursion stack for DFS

Method 2 - Optimized Early Termination

Intuition

We can optimize by reordering checks for early termination and combining some validation steps. Since rotational symmetry is quickest to check and most likely to fail, we do it first. We can also combine connectivity and word length validation in a single pass.

Approach

  1. Quick validation: check minimum grid size and basic constraints
  2. Fast symmetry check with early termination on first mismatch
  3. Combined connectivity and word validation in single traversal
  4. Use iterative DFS to avoid recursion overhead
  5. Cache word segments during connectivity check for length validation

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

class Solution {
public:
    bool isValidCrosswordOptimized(vector<vector<int>>& grid) {
        if (grid.empty() || grid.size() < 3) return false;
        
        int n = grid.size();
        
        // Quick symmetry check with early termination
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != grid[n-1-i][n-1-j]) {
                    return false;
                }
            }
        }
        
        // Combined connectivity and word length check
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        vector<pair<int, int>> whiteSquares;
        
        // Collect all white squares
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    whiteSquares.push_back({i, j});
                }
            }
        }
        
        if (whiteSquares.empty()) return true;
        
        // Check connectivity using iterative DFS
        stack<pair<int, int>> stk;
        stk.push(whiteSquares[0]);
        visited[whiteSquares[0].first][whiteSquares[0].second] = true;
        int visitedCount = 1;
        
        vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!stk.empty()) {
            auto [r, c] = stk.top();
            stk.pop();
            
            for (auto& dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && 
                    !visited[nr][nc] && grid[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    stk.push({nr, nc});
                    visitedCount++;
                }
            }
        }
        
        if (visitedCount != whiteSquares.size()) {
            return false;
        }
        
        // Check word lengths efficiently
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    len++;
                } else {
                    if (len > 0 && len < 3) return false;
                    len = 0;
                }
            }
            if (len > 0 && len < 3) return false;
        }
        
        for (int j = 0; j < n; j++) {
            int len = 0;
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    len++;
                } else {
                    if (len > 0 && len < 3) return false;
                    len = 0;
                }
            }
            if (len > 0 && len < 3) return false;
        }
        
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

func isValidCrosswordOptimized(grid [][]int) bool {
    if len(grid) == 0 || len(grid) < 3 {
        return false
    }
    
    n := len(grid)
    
    // Quick symmetry check
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] != grid[n-1-i][n-1-j] {
                return false
            }
        }
    }
    
    // Collect white squares
    var whiteSquares [][2]int
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                whiteSquares = append(whiteSquares, [2]int{i, j})
            }
        }
    }
    
    if len(whiteSquares) == 0 {
        return true
    }
    
    // Check connectivity with iterative DFS
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    
    stack := [][2]int{whiteSquares[0]}
    visited[whiteSquares[0][0]][whiteSquares[0][1]] = true
    visitedCount := 1
    
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    
    for len(stack) > 0 {
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        r, c := curr[0], curr[1]
        
        for _, dir := range dirs {
            nr, nc := r+dir[0], c+dir[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < n &&
                !visited[nr][nc] && grid[nr][nc] == 1 {
                visited[nr][nc] = true
                stack = append(stack, [2]int{nr, nc})
                visitedCount++
            }
        }
    }
    
    if visitedCount != len(whiteSquares) {
        return false
    }
    
    // Check word lengths efficiently
    for i := 0; i < n; i++ {
        length := 0
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                length++
            } else {
                if length > 0 && length < 3 {
                    return false
                }
                length = 0
            }
        }
        if length > 0 && length < 3 {
            return false
        }
    }
    
    for j := 0; j < n; j++ {
        length := 0
        for i := 0; i < n; i++ {
            if grid[i][j] == 1 {
                length++
            } else {
                if length > 0 && length < 3 {
                    return false
                }
                length = 0
            }
        }
        if length > 0 && length < 3 {
            return false
        }
    }
    
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

class Solution {
    public boolean isValidCrosswordOptimized(int[][] grid) {
        if (grid == null || grid.length == 0 || grid.length < 3) {
            return false;
        }
        
        int n = grid.length;
        
        // Quick symmetry check
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != grid[n-1-i][n-1-j]) {
                    return false;
                }
            }
        }
        
        // Collect white squares
        List<int[]> whiteSquares = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    whiteSquares.add(new int[]{i, j});
                }
            }
        }
        
        if (whiteSquares.isEmpty()) return true;
        
        // Check connectivity with iterative DFS
        boolean[][] visited = new boolean[n][n];
        Stack<int[]> stack = new Stack<>();
        int[] start = whiteSquares.get(0);
        stack.push(start);
        visited[start[0]][start[1]] = true;
        int visitedCount = 1;
        
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!stack.isEmpty()) {
            int[] curr = stack.pop();
            int r = curr[0], c = curr[1];
            
            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                    !visited[nr][nc] && grid[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    stack.push(new int[]{nr, nc});
                    visitedCount++;
                }
            }
        }
        
        if (visitedCount != whiteSquares.size()) {
            return false;
        }
        
        // Check word lengths efficiently
        for (int i = 0; i < n; i++) {
            int len = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    len++;
                } else {
                    if (len > 0 && len < 3) return false;
                    len = 0;
                }
            }
            if (len > 0 && len < 3) return false;
        }
        
        for (int j = 0; j < n; j++) {
            int len = 0;
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    len++;
                } else {
                    if (len > 0 && len < 3) return false;
                    len = 0;
                }
            }
            if (len > 0 && len < 3) return false;
        }
        
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

class Solution:
    def is_valid_crossword_optimized(self, grid: List[List[int]]) -> bool:
        if not grid or len(grid) < 3:
            return False
        
        n = len(grid)
        
        # Quick symmetry check
        for i in range(n):
            for j in range(n):
                if grid[i][j] != grid[n-1-i][n-1-j]:
                    return False
        
        # Collect white squares
        white_squares = []
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    white_squares.append((i, j))
        
        if not white_squares:
            return True
        
        # Check connectivity with iterative DFS
        visited = [[False] * n for _ in range(n)]
        stack = [white_squares[0]]
        visited[white_squares[0][0]][white_squares[0][1]] = True
        visited_count = 1
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while stack:
            r, c = stack.pop()
            
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n and 
                    not visited[nr][nc] and grid[nr][nc] == 1):
                    visited[nr][nc] = True
                    stack.append((nr, nc))
                    visited_count += 1
        
        if visited_count != len(white_squares):
            return False
        
        # Check word lengths efficiently
        for i in range(n):
            length = 0
            for j in range(n):
                if grid[i][j] == 1:
                    length += 1
                else:
                    if length > 0 and length < 3:
                        return False
                    length = 0
            if length > 0 and length < 3:
                return False
        
        for j in range(n):
            length = 0
            for i in range(n):
                if grid[i][j] == 1:
                    length += 1
                else:
                    if length > 0 and length < 3:
                        return False
                    length = 0
            if length > 0 and length < 3:
                return False
        
        return True

Complexity

  • ⏰ Time complexity: O(n²), same as Method 1 but with better constant factors due to early termination and reduced function call overhead
  • 🧺 Space complexity: O(n²) for visited array and white squares collection, but uses iterative approach to avoid recursion stack

Notes

  • Method 1 provides a clear, systematic validation of each crossword rule with separate helper functions
  • Method 2 optimizes performance through early termination, iterative algorithms, and combined validation steps
  • Both methods handle edge cases like empty grids, small grids, and grids with no white squares
  • The rotational symmetry check is the fastest elimination test and should be performed first
  • Connectivity verification ensures all white squares form a single connected component
  • Word length validation prevents invalid short words that would make the puzzle unsolvable
  • The 180-degree rotational symmetry is a key aesthetic and structural requirement for American crosswords
  • Real crossword construction involves additional constraints like word quality and theme coherence
  • The algorithm can be extended to support rectangular grids or different symmetry patterns
  • Consider optimizing further with bit manipulation for very large grids or real-time validation