Alphabet Board Path: Grid Coordinate Navigation

You are given a string target. You have a pointer starting at 'a' on an alphabet board arranged like this:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z

You can move the pointer up ('U'), down ('D'), left ('L'), or right ('R'). After navigating to a letter, you append '!' to select it. Return the shortest sequence of moves that spells out the entire target string.

This is LeetCode 1138: Alphabet Board Path, and it is a great problem for practicing coordinate-based grid navigation. The core idea is simple, but the letter 'z' sitting alone on the last row introduces a subtle trap that catches many first attempts.

Why this problem matters

Grid coordinate navigation is a recurring theme in coding interviews. Any time you need to move between positions on a 2D board, the fundamental question is the same: how do you convert a position into (row, column) coordinates, compute the difference, and translate that difference into a sequence of directional moves?

This problem distills that idea into a clean setting. The board has a fixed layout, so you can precompute every letter's position. The challenge is not algorithmic complexity. It is careful handling of a special case that arises from the board's irregular shape.

The key insight

Every letter from 'a' to 'z' maps to a (row, col) coordinate. Since the board has 5 columns, the letter at position i (where a = 0, b = 1, and so on) lives at row i // 5 and column i % 5. This gives you a hash map from character to coordinate in constant time.

To move from one letter to another, you compute the row difference and column difference, then output the corresponding 'U'/'D' and 'L'/'R' characters. After reaching the target position, you append '!'.

The catch is 'z'. It sits at position (5, 0), the only letter in row 5. If you try to move right while on row 5, you go off the board. Similarly, if you try to move down to row 5 while your column is greater than 0, you land outside the grid.

The fix is to always move up and left before moving down and right. This ensures that when you are heading toward 'z', you first move left to column 0 (while still on a full row), and then move down to row 5. When leaving 'z', you first move up to row 4 (a full row), and then move right to the target column. This ordering guarantees you never land on an invalid cell.

The solution

def alphabet_board_path(target: str) -> str:
    def pos(ch):
        i = ord(ch) - ord('a')
        return i // 5, i % 5

    result = []
    r, c = 0, 0

    for ch in target:
        tr, tc = pos(ch)
        if tr < r:
            result.append('U' * (r - tr))
        if tc < c:
            result.append('L' * (c - tc))
        if tr > r:
            result.append('D' * (tr - r))
        if tc > c:
            result.append('R' * (tc - c))
        result.append('!')
        r, c = tr, tc

    return ''.join(result)

Let's walk through the logic.

The pos helper converts a character into its (row, col) position using integer division and modulo by 5. This is the coordinate mapping at the heart of the solution.

The main loop processes each character in target. For the current letter, we compute its target row and column. Then we output moves in a specific order: up first, then left, then down, then right. This ordering is critical for handling 'z' correctly. By moving up/left before down/right, we avoid stepping onto row 5 with a non-zero column, or stepping right while already on row 5.

After appending all directional moves, we add '!' to select the letter, then update our current position.

Visual walkthrough

Let's trace through target = "leet" step by step. Watch how the pointer moves from letter to letter, building up the path string.

Each step computes the row and column difference between the current position and the target letter. The directional characters are generated from those differences, and '!' locks in the selection. The path accumulates across all steps.

Complexity analysis

Time: for each of the n characters in target, we compute the coordinate difference and generate at most 9 move characters (at most 5 rows + 4 columns of movement). Since max_distance is bounded by a constant (the board is 6x5), this simplifies to O(n).

Space: the result string has length proportional to n times the average number of moves per character. With the board size being constant, this is O(n).

The building blocks

1. Coordinate mapping

The pattern of converting a 1D index into 2D (row, col) coordinates:

def pos(ch):
    i = ord(ch) - ord('a')
    return i // 5, i % 5

This is the same idea you use whenever you flatten or unflatten a 2D grid. Given a total of cols columns, element i lives at row i // cols and column i % cols. You see this in problems like Search a 2D Matrix, Spiral Matrix, and any grid problem that stores data in a flat array. Once this conversion is automatic, you can move freely between 1D and 2D representations.

2. Special case handling for 'z'

The pattern of ordering moves to avoid invalid positions:

if tr < r:
    result.append('U' * (r - tr))
if tc < c:
    result.append('L' * (c - tc))
if tr > r:
    result.append('D' * (tr - r))
if tc > c:
    result.append('R' * (tc - c))

By processing up/left before down/right, you ensure the pointer always stays on a valid cell. This is a general technique for irregular grids: when the grid has holes or missing cells, you control the traversal order so the intermediate positions are always valid. The same idea applies in problems where you need to avoid obstacles during a multi-step movement.

Edge cases

Before submitting, verify your solution handles these scenarios:

• Target starts with 'a': the pointer is already at 'a', so the first move is just '!'.
• Target contains 'z': the pointer must reach (5, 0). If coming from a column greater than 0, you need to move left first, then down.
• Consecutive identical letters: no movement needed, just '!'.
• Moving from 'z' to another letter: move up first to leave row 5, then move right if needed.
• Single character target: outputs just the moves to reach that character plus '!'.
• Target is "az" or "za": tests the transition between a normal row and the irregular last row in both directions.

From understanding to recall

You have seen how coordinate mapping turns this problem into simple arithmetic: compute the row and column for each letter, find the differences, and output the corresponding moves. The only subtlety is the move ordering to handle 'z'. None of this is conceptually difficult.

But under interview pressure, the details matter. Do you move up before left, or left before up? Do you update the position before or after appending '!'? Which direction of movement do you prioritize? These are the small decisions that turn a correct idea into a correct implementation.

Spaced repetition helps you internalize these details. You practice writing the coordinate conversion, the move ordering, and the position update from scratch. After a few rounds, the pattern is automatic. You see a grid navigation problem and the coordinate arithmetic flows out without hesitation.

Related posts

• Spiral Matrix - Another grid traversal problem where careful boundary management and direction ordering are essential
• Search a 2D Matrix - Uses the same row/column coordinate mapping from a 1D index to navigate a sorted 2D grid
• Group Anagrams - A hash map pattern problem where you map inputs to canonical keys, similar to mapping characters to coordinates

CodeBricks breaks Alphabet Board Path into its coordinate-mapping and move-ordering building blocks, then drills them independently with spaced repetition. You type the position calculation and the directional output from scratch until the pattern is automatic. When a grid navigation problem shows up in your interview, you do not think about it. You just write it.