Abstract / Summary

Two fingers type a word on a keyboard grid minimizing total movement distance between keystrokes.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (70k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the smallest total Manhattan distance required for two hands to type a given word on a virtual 6 × 5 keyboard grid. Each character is mapped to a coordinate on the grid, and the algorithm explores all possible assignments of characters to the left or right hand while accumulating movement costs. The result is the minimal sum of distances that the two hands must travel to type the entire word.

Key Steps

The algorithm begins by defining a sentinel value +inf that represents an undefined initial hand position. This sentinel is used throughout the distance calculation to indicate that a hand has not yet been placed on the board.

def distance(x1, y1, x2, y2):
    if x1 == +inf:
        return 0
    return abs(x1 - x2) + abs(y1 - y2)

The distance helper returns zero when the source hand has never been used, effectively treating the first movement of each hand as cost-free. For any subsequent move it returns the Manhattan distance between two grid points.

The core of the solution is a recursive function deeper that is memoized with @cache. Memoization guarantees that each distinct state-defined by the current positions of both hands and the index of the next character-is evaluated at most once.

@cache
def deeper(x1, y1, x2, y2, pos):
    if pos == len(word):
        return 0

The base case terminates recursion when all characters have been processed, returning a zero contribution for the remaining distance.

Inside the recursion, the current character is translated from its alphabetical index to grid coordinates. The keyboard layout is imagined as a 6-column grid, so the column is the remainder of division by six and the row is the integer quotient.

c = ord(word[pos]) - ord("A")
x = c % 6
y = c // 6

Two recursive branches are then explored: assigning the current character to the left hand or to the right hand. Each branch updates the corresponding hand’s coordinates, adds the movement cost for that hand, and proceeds to the next character.

left  = deeper(x,  y,  x2, y2, pos + 1) + distance(x1, y1, x, y)
right = deeper(x1, y1, x,  y,  pos + 1) + distance(x2, y2, x, y)
return min(left, right)

The min operation selects the cheaper of the two possibilities, ensuring that the overall path remains optimal.

Finally, the public method minimumDistance invokes deeper with both hands positioned at the sentinel value and starts processing from the first character.

return deeper(+inf, +inf, +inf, +inf, 0)

Edge Cases Handled

The use of the sentinel +inf allows the algorithm to treat the first movement of each hand as having zero cost. Consequently, the function correctly handles words where one hand never moves, such as a single-character word or a word that can be typed entirely with one hand. When the input string is empty, the base case pos == len(word) is true immediately, and the function returns zero, representing no movement required. Repeated characters are also managed gracefully: the distance between identical coordinates evaluates to zero, so typing the same key consecutively incurs no additional cost for the hand that remains on that key.

Performance Optimizations

Memoization via @cache is the primary optimization. By caching the result of each unique state (x1, y1, x2, y2, pos), the algorithm avoids exponential recomputation of overlapping subproblems. This dramatically reduces the number of recursive calls, especially for longer words where many hand position combinations recur.

The distance calculation is performed only when needed, and the early return for undefined hand positions eliminates unnecessary arithmetic for the initial steps. The min selection between the two hand assignments ensures that only the optimal path is propagated upward, preventing the accumulation of suboptimal costs.

Together, these techniques keep the execution efficient while exploring the full combinatorial space of hand assignments.

Imagine you are playing a game where you have to type letters on a big grid using two hands. This code acts like a tiny brain that wants to find the best way to type a whole word while moving your hands as little as possible.

The computer starts by looking at every letter in the word one by one. For each letter, it asks a simple question. Should the left hand move to type this letter, or should the right hand move instead?

To solve this, the code calculates the distance for both options. It checks where each hand is currently sitting and figures out how far it needs to travel to reach the new letter. If a hand has not been used yet, it shows up as an infinity symbol, which just means it can jump to the first letter for free without any travel cost.

Because the word might be very long, the code keeps track of every possibility it has already calculated so it does not waste time doing the same work twice. It constantly compares the cost of moving the left hand versus moving the right hand for every single step of the way. By the time it reaches the end of the word, it has explored every path and picked the smoothest, shortest way to finish typing.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	gouthampradhan			Java
	JoshCrozier		JS
	lkwq007				Python
	lzl124631x	C++
	suxrobGM					C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality