Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
You are given a 10×10 grid where `+` is a blocked cell and `-` is a blank to fill, plus a `;`-separated list of words. Find the maximal horizontal and vertical runs of `-` of length ≥ 2 (the 'slots'), then backtrack: assign an unused word to the first unfilled slot only if its length matches and every overlapping letter is consistent (cell is blank or already holds that letter), recurse, and undo on failure. Because the word count is tiny (≤ 10) and slots are few, the search is small in practice; the worst case is O(W! · L) where W is the number of words and L the slot length.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model the grid as a set of slots (maximal blank runs) and run consistent backtracking with proper undo, correctly handling the intersections where two words share a cell.
Where candidates slip
Restoring backtracked cells to `-` instead of their previous letter (erasing an already-placed crossing word), or placing words at arbitrary offsets without respecting `+` boundaries so a word overruns a blocked cell.
How to stand out
Separate slot-enumeration from search, state that the fit check must allow a cell that already holds the matching letter (the crossing), and note that the small word count keeps the factorial search cheap in practice.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision preview10x10 grid + word listall slots filled?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Cell Placement — Place a Word at Any Fitting Position
1Hint 1Explore hintHide hint
For the first remaining word, scan every cell and both orientations, and try to drop the word there.
2Hint 2Explore hintHide hint
A placement is valid only if the word stays in bounds, every covered cell is `-` or matches the letter, AND the cells just before the start and just after the end are `+` or the edge (so you land on a real slot, not the middle of one).
3Hint 3Explore hintHide hint
Recurse on the rest of the words; undo carefully on failure. The boundary check is what stops a word from overrunning a blocked cell.
A · Core idea
The most direct translation of the problem: take the next word and try to place it somewhere. For each grid cell and each of the two orientations, check whether the word fits.
What 'fits' must mean. It is not enough that the covered cells are blank or matching — you must also verify the boundaries. A horizontal word starting at (r, c) is only valid if c == 0 or grid[r][c-1] == '+', and c + len == C or grid[r][c + len] == '+'. Without these guards the word can start in the middle of a longer blank run or spill past a +, producing a grid that looks filled but violates the slot structure.
Why it is awkward. The boundary bookkeeping is exactly the information a slot already encodes. By re-deriving 'is this a real slot?' at every cell for every word, you do the same work repeatedly and invite off-by-one bugs at the edges. It also wastes effort trying thousands of positions that aren't slots at all.
Why we don't ship it. It works, but the slot-based version below precomputes the legal positions once, shrinks the branching factor to 'which word goes in this slot', and makes the undo logic trivial. Mention this approach to show you considered the brute force, then refine it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
single horizontal slot row 3 cols 1..5, word = DELHIInteractive diagram
Why boundaries matter
try (3,0) HWithout the left/right wall check, a word can start mid-run or overrun a '+'.
DELHI placed at row 3, cols 1..5C · Code with teaching comments
Reference implementation previewimport java.util.*; public List<String> crosswordPuzzle(List<String> gridIn, String wordStr) { char[][] grid = new char[10][10]; for (int r = 0; r < 10; r++) grid[r] = gridIn.get(r).toCharArray();Explore the full codeHide the full code
D · Why it works and complexityO(W! · R · C · L) timeO(R · C) spaceOpen the invariant and proofExplore the proofHide the proof
The brute version keeps rediscovering where the slots are. Computing slots once turns an O(R·C) position search per word into an O(1) 'next slot' lookup — the same speedup you get by indexing instead of scanning.
ComplexityO(W! · R · C · L) time, O(R · C) space — For each of W words you may try up to R·C starting cells × 2 orientations, each costing O(L) to validate, and the recursion multiplies these across words — roughly O(W! · R · C · L). The grid copy is O(R·C).
E · Edge cases and pitfalls3Forgetting the before/after boundary check — a word fills the middle of a longer blank run.Explore edge casesHide edge cases
Pitfalls
- Forgetting the before/after boundary check — a word fills the middle of a longer blank run.
- Restoring cells to `-` on undo instead of the saved prior contents — erases crossing words.
- Re-checking the same non-slot positions for every word — slow and bug-prone.
Approach 2 of 2 · Optimal
Slot Enumeration + Backtracking (Optimal)
1Hint 1Explore hintHide hint
First pass: scan each row for maximal `-` runs of length ≥ 2 → horizontal slots; scan each column the same way → vertical slots. Store each slot as its list of cells.
2Hint 2Explore hintHide hint
Backtrack over slots in order. For the current slot, try every unused word whose length matches; it fits if each cell is `-` or already equals the word's letter at that position.
3Hint 3Explore hintHide hint
Place the word (saving each cell's prior char), mark it used, recurse to the next slot; on failure restore the saved chars and unmark. Return the grid when all slots are filled.
A · Core idea
Split the work into 'find the empty slots' and 'fill them'.
Enumerate slots once. Walk each row left to right; whenever you see a -, extend to the end of the run, and if that run has length ≥ 2 record the list of its cells as a horizontal slot. Do the same down each column for vertical slots. Now every legal word position is captured exactly once — no boundary re-checking during the search.
Backtrack slot by slot. Process slots[i]. For each word not yet used whose length equals the slot length, test the fit: for every cell in the slot, the grid must hold - (free) or the same letter the word would place (a crossing already filled by an earlier word). If it fits, write the word's letters into the slot — but first save each cell's previous character into a backup, because some of those cells may already belong to a crossing word. Mark the word used and recurse to slots[i+1]. If the recursion fails, restore the saved characters and unmark, then try the next word.
Why the backup is the whole game. When two words cross, the second word to be placed must not disturb the shared letter, and if a branch later fails we must restore exactly what was there — which might be a letter from a crossing word, not a -. Blanket-resetting to - would silently delete an already-correct crossing. Saving and restoring per cell makes undo exact.
Termination. When i == len(slots) every slot holds a word and all crossings are consistent (each placement was checked), so the grid is the unique solution.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid rows = +-++++++++ / +-++++++++ / +-++++++++ / +-----++++ / +-+++-++++ / +-+++-++++ / +++++-++++ / ++------++ / +++++-++++ / +++++-++++, words = LONDON;DELHI;ICELAND;ANKARAHow to read it:Each crossing cell is shared by one horizontal and one vertical slot; the placed letter must satisfy both.
+L++++++++ / +O++++++++ / +N++++++++ / +DELHI++++ / +O+++C++++ / +N+++E++++ / +++++L++++ / ++ANKARA++ / +++++N++++ / +++++D++++C · Code with teaching comments
D · Why it works and complexityO(W! · L) timeO(S · L) spaceOpen the invariant and proofExplore the proofHide the proof
Modeling the grid as slots converts a 2-D placement puzzle into a 1-D constraint-satisfaction problem: assign words to slots so overlaps agree. The only stateful subtlety is undo — save each cell's prior contents so a failed branch restores crossing letters instead of erasing them.
ComplexityO(W! · L) time, O(S · L) space — Enumerating slots is one O(R·C) pass. The search assigns words to S slots; in the worst case it tries permutations of the W words, each fit/place/undo costing O(L) for slot length L → O(W! · L). Space is the slots (O(S·L)) plus recursion depth O(S).
E · Edge cases and pitfalls6Single slot, single word — No crossings; the word is placed and the base case `i == len(slots)` returns true immediately.Explore edge casesHide edge cases
Edge cases handled
Single slot, single wordNo crossings; the word is placed and the base case `i == len(slots)` returns true immediately.Two words of equal length, both fit a slotThe first is tried; if a later crossing fails the search backtracks and tries the other — order is resolved by the recursion.Word whose length matches no slotGuaranteed not to occur (counts match), but the length guard would simply skip it everywhere.
Pitfalls
- Resetting cells to `-` on undo instead of restoring the saved characters — wipes a crossing word.
- Treating single blanks as slots — only runs of length ≥ 2 qualify.
- Forgetting the 'cell already equals the letter' branch in the fit check — rejects valid crossings.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.util.*; public List<String> crosswordPuzzle(List<String> gridIn, String wordStr) { char[][] grid = new char[10][10]; for (int r = 0; r < 10; r++) grid[r] = gridIn.get(r).toCharArray();Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Undo that erases crossings
On backtrack the cells must be restored to exactly what they held before — which may be letters from a crossing word already placed. Blanket-resetting to `-` deletes that crossing and corrupts the grid.
Explore the code comparisonHide the code comparison
Undo that erases crossings
On backtrack the cells must be restored to exactly what they held before — which may be letters from a crossing word already placed. Blanket-resetting to `-` deletes that crossing and corrupts the grid.
Don't write this
for (r, c) in slot:
grid[r][c] = '-' # WRONG: wipes crossing letters tooWrite this instead
backup = [grid[r][c] for (r, c) in slot]
# ... place, recurse ...
for j, (r, c) in enumerate(slot):
grid[r][c] = backup[j] # restore exact prior contents2Fit check that ignores existing crossings
A cell already filled by a crossing word is not blank, but it's still a valid placement if it equals this word's letter. Requiring every cell to be `-` rejects all crossings.
Explore the code comparisonHide the code comparison
Fit check that ignores existing crossings
A cell already filled by a crossing word is not blank, but it's still a valid placement if it equals this word's letter. Requiring every cell to be `-` rejects all crossings.
Don't write this
fits = all(grid[r][c] == '-' for (r, c) in slot) # rejects valid crossingsWrite this instead
fits = all(grid[r][c] == '-' or grid[r][c] == w[j]
for j, (r, c) in enumerate(slot))3Missing boundary check in brute placement
Without verifying the cell before the start and after the end are `+`/edge, a word can begin mid-run or overrun a wall, filling a non-slot.
Explore the code comparisonHide the code comparison
Missing boundary check in brute placement
Without verifying the cell before the start and after the end are `+`/edge, a word can begin mid-run or overrun a wall, filling a non-slot.
Don't write this
// only checks bounds and matching letters
if (c + len <= 10 && lettersMatch) place();Write this instead
if (c + len <= 10
&& (c == 0 || g[r][c-1] == '+')
&& (c + len == 10 || g[r][c+len] == '+')
&& lettersMatch) place();Revise
Carry the pattern into the interview
Pattern to remember
Slot enumeration + backtracking with intersection consistency (place → recurse → un-place)
Code pattern to memorize
slots = all maximal runs of '-' (length >= 2), horizontal and vertical
def solve(i):
if i == len(slots): return True
for w in words:
if w used or len(w) != len(slot[i]): continue
if every cell is '-' or already == matching letter of w:
place w, mark used
if solve(i + 1): return True
un-place w, unmark used
return FalseRules to remember
- 1Build slots first: scan each row and column for maximal runs of
-with length ≥ 2 — single blanks are never slots. - 2A word fits a slot only if lengths match AND every cell is either blank (
-) or already equals the word's letter at that position (intersection consistency). - 3On backtrack restore exactly what each cell held before — save a per-cell backup, not a blanket reset to
-, because crossing words may have written letters first. - 4Track used words so the same word isn't placed twice.
- 5Place words into slots, not arbitrary positions — a brute placement that ignores
+boundaries will overrun a blocked cell.
Use this pattern when
- Fill a fixed grid from a finite word list with crossing constraints
- Constraint-satisfaction where each placement restricts later placements
- Small search space (few slots / few words) so exponential search is acceptable
- Any 'fit pieces into cells respecting overlaps' puzzle (Sudoku, word-fill, KenKen)
Choose another pattern when
- Huge word list / large grid → naive backtracking explodes; need constraint propagation or DLX
- Words can be reused unlimited times → the used-set bookkeeping changes
- No crossing constraints (independent placements) → it's just matching lengths, no search
- You only need to check if a single word fits → a simple scan, not backtracking
Interview takeaway
Crossword Puzzle is constraint-satisfaction backtracking on a grid: enumerate the empty slots, then choose → check overlaps → recurse → undo. The discipline that makes it correct is saving each cell's prior contents so a failed branch restores crossings rather than wiping them to blank.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternConstraint-satisfaction backtracking on a grid. Model the empty cells as slots, then assign words to slots with choose → check overlaps → recurse → undo. The defining detail is exact undo (save each cell's prior contents) so crossings survive a failed branch. The same shape powers Sudoku solvers and Word Search.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Word SearchFind whether one word exists in a grid via DFS — the same choose/explore/un-choose on a grid, without the slot bookkeeping.
- N-QueensConstraint-satisfaction backtracking where each placement restricts later rows — same skeleton, different constraints.
- Palindrome PartitioningBacktracking that commits a prefix and recurses on the rest, undoing on return.