Skip to main content
Talentd

Valid Word Square - Solution & Explanation

EasyPremiumFree on FleetCodeArrayMatrix6 min readAsked at: Google
Practice this problem

Problem Statement

Given an array of strings words, return true if it forms a valid word square.

A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).

 

Example 1:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

Example 2:

Input: words = ["abcd","bnrt","crm","dt"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crm".
The 4th row and 4th column both read "dt".
Therefore, it is a valid word square.

Example 3:

Input: words = ["ball","area","read","lady"]
Output: false
Explanation:
The 3rd row reads "read" while the 3rd column reads "lead".
Therefore, it is NOT a valid word square.

 

Constraints:

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 500
  • words[i] consists of only lowercase English letters.

Approach Overview

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.

Solution

We observe that if words[i][j] neq words[j][i], we can directly return false.

Therefore, we only need to iterate through each row, and then check whether each row satisfies words[i][j] = words[j][i]. Note that if the index is out of bounds, we also directly return false.

The time complexity is O(n^2), where n is the length of words. The space complexity is $O(1)`.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Build and Compare Matrix (Brute Force)O(n^2)O(n^2)When modeling the problem explicitly as a 2D grid or explaining the concept of row-column symmetry
Iterative Index CheckO(n^2)O(1)Best general solution. Directly compares words[i][j] and words[j][i] without building extra structures

Video Solution

LeetCode 422. Valid Word Square • coderZ • 814 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Valid Word Square easy or hard?
Valid Word Square is classified as an Easy problem on LeetCode with an acceptance rate around 43%. The main challenge is handling uneven word lengths and index bounds while verifying the row-column symmetry condition.
Valid Word Square Python/Java solution
Both Python and Java implementations follow the same logic: nested iteration over indices and a comparison between words[i][j] and words[j][i]. The code includes boundary checks to ensure the column word exists and contains the required index.
How to solve Valid Word Square in O(n^2)?
Iterate through every character in the word list using two indices i and j. For each words[i][j], verify that word j exists, that its length is greater than i, and that words[j][i] matches the character. If any condition fails, return false immediately.
What is the best approach for Valid Word Square?
The iterative index comparison approach is the most efficient. For each position (i, j), check whether words[i][j] equals words[j][i] while ensuring the indices exist. This avoids building a matrix and runs in O(n^2) time with O(1) extra space.
Is Valid Word Square asked at Google/Amazon/Meta?
Valid Word Square appears in interview preparation sets and has been reported in interviews at companies like Google and Amazon. The problem tests attention to edge cases, bounds checking, and understanding of matrix symmetry using arrays of strings.
What data structure is used in Valid Word Square?
The solution mainly uses an array (or list) of strings and treats it conceptually like a matrix. No additional data structures such as hash maps or stacks are required. The algorithm relies on direct index access for row-column comparisons.
What is the time complexity of Valid Word Square?
The typical solution runs in O(n^2) time in the worst case, where n is the maximum word length or number of words. Each character position is checked once against its symmetric counterpart. Space complexity is O(1) because the validation uses only index comparisons.

Ready to solve this problem?

Practice Valid Word Square with our built-in code editor and test cases.

Practice on FleetCode
Previous

Toeplitz Matrix

Next

Word Squares