Arrays Pattern

Intro

I keep a small C# repo where I re-solve LeetCode problems grouped by pattern, and the “Arrays” bucket is really where 2D-grid DFS lives for me. Whenever a problem gives me a grid of characters or numbers and asks “does some path/shape exist in here”, my first instinct now is: DFS from every candidate starting cell, mark cells as visited while I’m standing on them, and unmark them the moment that branch fails. That’s it — that’s the whole pattern. It shows up under different names (grid traversal, backtracking on a matrix, flood-fill-with-a-twist) but the shape of the code barely changes between problems.

The problem that made this click for me is LeetCode 79 — Word Search.

The problem

You get a 2D grid of letters and a target word. You need to say whether the word can be traced out by moving between horizontally/vertically adjacent cells, using each cell at most once per path. So "ABCCED" might exist starting at the top-left corner and snaking down through the grid, but you can’t reuse a cell you’ve already stepped on earlier in that same path.

The naive idea — try every starting cell, and from each one try every direction, recursively — is exactly right. The only trick is bookkeeping which cells are “in use” for the current path, without allocating a separate visited array.

The code

Here’s the real implementation from my repo (Arrays/LeetCode.Arrays/WordSearch.cs), trimmed of using/namespace lines:

public class WordSearch
{
    public static bool Exist(char[][] board, string word)
    {
        var direction = new int[][] { [0, -1], [0, 1], [-1, 0], [1, 0] };

        bool Dfs(int i, int j, int s)
        {
            if (s == word.Length)
            {
                return true;
            }
            if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length || board[i][j] != word[s])
            {
                return false;
            }
            var temp = board[i][j];
            board[i][j] = '#'; // Mark as visited
            foreach (var d in direction)
            {
                if (Dfs(i + d[0], j + d[1], s + 1))
                {
                    return true;
                }
            }
            board[i][j] = temp; // Unmark
            return false;
        }

        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[0].Length; j++)
            {
                if (board[i][j] == word[0] && Dfs(i, j, 0))
                {
                    return true;
                }
            }
        }

        return false;
    }
}

The neat trick here is board[i][j] = '#'. Instead of carrying around a second bool[,] visited array, the algorithm just overwrites the cell in place with a sentinel character that can never match a real letter of the word. That means the very next bounds/char check (board[i][j] != word[s]) naturally rejects any attempt to step back onto a cell that’s already part of the current path — no extra lookup needed. Then, on the way back up the call stack, board[i][j] = temp restores the original letter so a different starting cell or a different branch can still use it later.

Walking through it:

• Dfs(i, j, s) asks: “can the substring word[s..] be traced starting at (i, j)?”
• Base case: if s already equals word.Length, we matched every character — success.
• Guard case: out of bounds, or this cell doesn’t hold the letter we need — fail, and importantly, fail before touching the board, so we never mark a cell we didn’t actually match.
• Otherwise: temporarily mark the cell visited, try all four directions for the next letter, and if none of them pan out, put the original letter back and report failure up to the caller.
• The outer double loop just tries every cell as a possible starting point for word[0].

Complexity-wise, in the worst case you fan out from up to N·M starting cells, and each DFS branches into up to 4 directions per character of the word, so it’s roughly O(N·M·4^L) where L is the word length. In practice it’s much better than that because most branches die immediately on a letter mismatch — the 4^L is a pessimistic ceiling, not what you actually see on typical inputs. Space is O(L) for the recursion stack (plus the in-place board mutation, which costs nothing extra).

Try it

Below is the same algorithm running on a tiny 3x3 board, searching for "ABCD". Watch the amber cell as it’s tested, the blue trail as cells get marked, and — this is the part that took me a minute to really internalize — a red flash and un-mark when a branch dead-ends and the recursion has to climb back up and try a different direction. Step through it or hit play.

Green = matched path. Amber = current cell being tried. Red = mismatch or backtrack. Play or step through with the controls above.

Notice the middle of the run: the DFS commits to (0,2), tries all three of its unvisited neighbors, finds none of them hold the letter D, and has to unmark (0,2) and hand control back to (0,1) — which then tries a completely different neighbor, (1,1), and that branch goes on to succeed. That unmark-and-retry is the entire “backtracking” part of the pattern in one frame.

Takeaways

• The '#' sentinel trick is the reusable idea here: when you need a “currently in this path” marker and you already have a mutable grid, overwrite in place instead of allocating a parallel visited structure — just remember to restore it before returning.
• Always check bounds/character-match before mutating the cell, so failed attempts never leave the grid in a wrong state.
• Complexity is bounded by O(N·M·4^L), but real inputs prune hard and fast because most letters just don’t match — don’t let the worst-case scare you off using this pattern.

Next up in this series: more patterns from the same repo, same format.