Skip to main content
Talentd

Check if Word Can Be Placed In Crossword - Solution & Explanation

MediumArrayMatrixEnumeration28 min readAsked at: Google
Practice this problem

Problem Statement

You are given an m x n matrix board, representing the current state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), ' ' to represent any empty cells, and '#' to represent any blocked cells.

A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) in the board if:

  • It does not occupy a cell containing the character '#'.
  • The cell each letter is placed in must either be ' ' (empty) or match the letter already on the board.
  • There must not be any empty cells ' ' or other lowercase letters directly left or right of the word if the word was placed horizontally.
  • There must not be any empty cells ' ' or other lowercase letters directly above or below the word if the word was placed vertically.

Given a string word, return true if word can be placed in board, or false otherwise.

 

Example 1:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
Output: true
Explanation: The word "abc" can be placed as shown above (top to bottom).

Example 2:

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
Output: false
Explanation: It is impossible to place the word because there will always be a space/letter above or below it.

Example 3:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
Output: true
Explanation: The word "ca" can be placed as shown above (right to left).

 

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m * n <= 2 * 105
  • board[i][j] will be ' ', '#', or a lowercase English letter.
  • 1 <= word.length <= max(m, n)
  • word will contain only lowercase English letters.

Approach Overview

Problem Overview: You are given a crossword board containing letters, blank cells, and blocked cells (#). The task is to check whether a given word can be placed horizontally or vertically so that it fits exactly between blocks while matching existing letters.

Approach 1: Greedy Check for Each Row and Column (O(m * n * k) time, O(1) space)

Scan every row and column and treat each segment between # characters as a potential placement slot. If the segment length equals the word length k, try matching the word character by character. A match is valid when the board cell is either blank or already contains the same character. Perform this check for both forward and reversed versions of the word to support placements in either direction. This method relies on straightforward enumeration of segments in the array and matrix, making it easy to implement but slightly redundant because each slot is checked twice.

Approach 2: Advanced Optimized Inline Check (O(m * n) time, O(1) space)

Instead of extracting segments first, iterate through each cell and detect valid starting points of a word. A cell is a valid start if it is not a block and the previous cell in that direction is either out of bounds or #. From this start position, verify whether the next k cells can host the word while ensuring the cell after the segment is a boundary or block. During the scan, check both forward and reverse character alignment inline without building temporary strings. This removes redundant segment scans and keeps the traversal strictly linear across the grid. The approach uses direct index checks on the matrix while enumerating candidates using enumeration.

Recommended for interviews: The greedy row and column scan clearly demonstrates the constraints of the crossword slots and is easy to reason about, so it works well as an initial explanation. Interviewers usually expect the optimized inline scan afterward because it eliminates unnecessary segment creation and achieves a clean O(m * n) traversal while maintaining constant extra space.

Approach 1: Greedy Check for Each Row and Column

This approach involves scanning each row and each column of the board to check if the word can fit. We examine potential start positions and ensure constraints are satisfied, such as boundary conditions and adjacent cell checks.

The C solution involves two main functions: checkRow checks if a word can be placed in a specified row, and checkCol does the same for a specified column. Each function checks both directions (left-to-right/right-to-left or top-to-bottom/bottom-to-top). Boundary conditions and matching constraints are validated for a successful placement.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1) since we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Advanced Optimized Inline Check

This method involves an inline checking process where we simultaneously explore the suitability of a position for rows and columns while moving through the board, optimizing early exits and reducing redundant checks.

C code optimizes word checks by combining inline checks for word placement in rows and columns, leveraging bridging checks based on initial cell values to minimize evaluations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Enumeration

We can enumerate each position (i, j) in the matrix, and judge whether we can place the word word from left to right or from right to left, or from top to bottom or from bottom to top, starting from this position.

The following conditions must be met for this position to be used as a starting point:

  1. If the word word is to be placed from left to right, then this position must be the left boundary, or the cell board[i][j - 1] to the left of this position is '#'.
  2. If the word word is to be placed from right to left, then this position must be the right boundary, or the cell board[i][j + 1] to the right of this position is '#'.
  3. If the word word is to be placed from top to bottom, then this position must be the upper boundary, or the cell board[i - 1][j] above this position is '#'.
  4. If the word word is to be placed from bottom to top, then this position must be the lower boundary, or the cell board[i + 1][j] below this position is '#'.

Under the above conditions, we can start from this position and judge whether the word word can be placed. We design a function check(i, j, a, b), which represents whether it is legal to place the word word from the position (i, j) in the direction (a, b). If it is legal, return true, otherwise return false.

The implementation of the function check(i, j, a, b) is as follows:

We first get the other boundary position (x, y) in the current direction, i.e., (x, y) = (i + a times k, j + b times k), where k is the length of the word word. If (x, y) is in the matrix and the cell at (x, y) is not '#', it means that the other boundary position in the current direction is not '#', so the word word cannot be placed, and false is returned.

Otherwise, we start from the position (i, j) and traverse the word word in the direction (a, b). If we encounter a cell board[i][j] that is not a space or not the current character of the word word, it means that the word word cannot be placed, and false is returned. If the word word is traversed, it means that the word word can be placed, and true is returned.

The time complexity is O(m times n), and the space complexity is O(1). Here, m and n are the number of rows and columns in the matrix, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Check for Each Row and Column

Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1) since we are using a constant amount of extra space.

Advanced Optimized Inline Check

Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1).

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Check for Each Row and ColumnO(m * n * k)O(1)Clear and straightforward implementation when explaining the slot matching idea
Advanced Optimized Inline CheckO(m * n)O(1)Preferred interview solution when you want a single linear traversal of the grid

Video Solution

Leetcode:Check if Word Can Be Placed In Crossword • Coding For Dummies • 1,962 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Check if Word Can Be Placed In Crossword easy or hard?
The problem is rated Medium because the logic is simple but edge cases can break naive solutions. Handling boundaries, reversed placement, and ensuring the word fits exactly between '#' blocks requires careful condition checks.
Check if Word Can Be Placed In Crossword Python/Java solution
Python, Java, C++, and other languages implement the same idea: iterate through the grid, detect valid starting positions, and check character matches inline. Because the algorithm only uses index traversal and simple comparisons, the code remains short and language independent.
How to solve Check if Word Can Be Placed In Crossword in O(n)?
Treat the board as a matrix scan and detect valid starting points for horizontal and vertical placements. Ensure the previous cell is a boundary or '#', then verify the next k cells match the word or are blank. Also ensure the cell immediately after the segment is blocked or out of bounds. This eliminates repeated segment scanning and keeps traversal linear across the grid.
What is the best approach for Check if Word Can Be Placed In Crossword?
The optimized inline scan is the best approach. Traverse the grid and treat each valid cell as a potential start of a word if the previous cell in that direction is a boundary or '#'. Then check exactly k cells for a forward or reversed match. This keeps the complexity at O(m * n) with O(1) extra space.
Is Check if Word Can Be Placed In Crossword asked at Google/Amazon/Meta?
Matrix scanning and constraint validation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests grid traversal, boundary checks, and careful handling of edge cases rather than complex data structures.
What data structure is used in Check if Word Can Be Placed In Crossword?
The main data structure is a 2D matrix (grid). The algorithm performs direct index checks and enumeration across rows and columns while comparing characters with the target word.
What is the time complexity of Check if Word Can Be Placed In Crossword?
The optimized solution runs in O(m * n) time where m and n are the grid dimensions. Each cell is considered as a possible starting point at most once per direction. Space complexity remains O(1) because the algorithm only performs inline checks without additional data structures.

Ready to solve this problem?

Practice Check if Word Can Be Placed In Crossword with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays