Valid Word Square - Solution & Explanation

Problem Overview: You receive a list of words. The list forms a valid word square if the k-th row reads the same as the k-th column. In other words, character words[i][j] must equal words[j][i] whenever both indices exist. If any mismatch appears or an index goes out of bounds, the square is invalid.

Approach 1: Build and Compare Matrix (Brute Force) (Time: O(n^2), Space: O(n^2))

A direct way is to treat the input like a grid. First construct a 2D character matrix from the words. If words have different lengths, fill missing cells with a placeholder or stop early. Then compare the matrix with its transpose: for every pair of indices (i, j), check whether matrix[i][j] == matrix[j][i]. If all pairs match, the structure is a valid square.

This approach mirrors how symmetric matrices work in a matrix. It is easy to reason about but allocates extra memory for the grid and performs unnecessary comparisons when the words already provide the needed structure.

Approach 2: Iterative Index Check (Optimal) (Time: O(n^2), Space: O(1))

The optimal solution skips building a matrix and directly validates the square using index comparisons. Iterate through each character position (i, j) in the list of words. For every character, verify three conditions: the column word j must exist, the column word must be long enough to contain index i, and the characters must match (words[i][j] == words[j][i]).

If j exceeds the number of words or i exceeds the length of words[j], the column cannot mirror the row, so return false immediately. This early exit keeps the check efficient. The algorithm only scans characters that actually appear in the input.

This pattern is essentially a symmetric check across rows and columns in a array of strings. Since each character is visited at most once, the runtime is O(n^2) in the worst case where each word length is about n. No additional data structures are required, so the space complexity stays O(1).

Recommended for interviews: The iterative index check is what interviewers expect. It shows you recognize the symmetry property of the square and can validate it with simple index logic instead of constructing an explicit matrix. Mentioning the brute-force matrix idea first demonstrates understanding, but implementing the constant-space check signals stronger problem-solving skill.