Valid Word Square - Practice Coding Problems

Valid Word Square - Problem

Array Matrix Easy

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).

In other words, for each position (i, j), the character at words[i][j] should equal the character at words[j][i] (if both positions exist).

Input & Output

Example 1 — Valid Word Square

$ Input: words = ["abcd","bnrt","crmy","dtye"]

› Output: true

💡 Note: Row 0: "abcd" matches Column 0: "abcd", Row 1: "bnrt" matches Column 1: "bnrt", etc. All rows equal their corresponding columns.

Example 2 — Invalid Word Square

$ Input: words = ["abcd","bnrt","crm","dt"]

› Output: false

💡 Note: Row 2 is "crm" but Column 2 would be "mrd" (reading vertically). They don't match, so it's not a valid word square.

Example 3 — Single Word

$ Input: words = ["a"]

› Output: true

💡 Note: Single character forms a valid 1×1 word square where row 0 equals column 0.

Constraints

1 ≤ words.length ≤ 500
1 ≤ words[i].length ≤ 500
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings representing potential word square

Process

Check if each row equals its corresponding column

Output

Return true if valid, false otherwise

Key Takeaway

🎯 Key Insight: A word square is valid when it's symmetric - each row must equal its corresponding column

Asked in

G Google 25 f Facebook 18

The key insight is that a valid word square must be symmetric: row i must equal column i. The optimized approach checks only the upper triangle to avoid redundant comparisons. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Single Pass	O(n²)	O(1)	Check only upper triangle to avoid redundant comparisons
Brute Force Character-by-Character	O(n²)	O(1)	Check every character against its mirror position with explicit bounds checking

Optimized Single Pass — Algorithm Steps

Iterate only through upper triangle (i <= j)
For each position, verify symmetry once
Handle boundary conditions efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Upper Triangle

Check only positions where i <= j

Symmetry Check

Verify words[i][j] == words[j][i] once

Result

Return true if all symmetric pairs match

Code -

solution.c — C

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

bool solution(char words[][100], int n) {
    if (n == 0) return true;
    
    // Check only upper triangle for efficiency
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int lenI = strlen(words[i]);
            int lenJ = strlen(words[j]);
            
            // Get character at (i,j)
            bool hasIJ = j < lenI;
            // Get character at (j,i) - symmetric position
            bool hasJI = i < lenJ;
            
            if (hasIJ != hasJI) {
                return false;
            }
            
            if (hasIJ && words[i][j] != words[j][i]) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for JSON array
    char words[50][100];
    int n = 0;
    
    char *start = strchr(line, '[');
    if (start) {
        start++;
        char *token = strtok(start, ",]");
        while (token && n < 50) {
            // Remove quotes and whitespace
            while (*token == ' ' || *token == '"') token++;
            char *end = token + strlen(token) - 1;
            while (end > token && (*end == ' ' || *end == '"' || *end == ']')) {
                *end = '\0';
                end--;
            }
            strcpy(words[n], token);
            n++;
            token = strtok(NULL, ",]");
        }
    }
    
    bool result = solution(words, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Still check O(n²) positions but only half the comparisons due to symmetry

⚠ Quadratic Growth

Space Complexity

O(1)

Only using loop variables and temporary characters

✓ Linear Space

15.6K Views

Medium Frequency

~15 min Avg. Time

428 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 Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler