Abstract / Summary

Given a string of 'I' and 'D', build the smallest possible number by placing digits so that 'I' means the next digit is larger and 'D' means the next is smaller.

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 86% (200k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Greedy
• Stack
• String

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 classic “minimum number from pattern” problem. Given a string consisting of the characters I (increase) and D (decrease), the goal is to construct the smallest possible integer that respects the relative ordering of its digits. The algorithm explores digit assignments recursively, pruning impossible branches early, and returns the first complete construction that satisfies the pattern.

Core Logic

Recursive Builder

The heart of the solution is the nested function deeper. It receives a partial string have that already satisfies the prefix of the pattern and attempts to extend it by one digit.

@cache
def deeper(have):
    if len(have) == len(pattern) + 1:
        return have

    previous = int(have[-1])
    if pattern[len(have) - 1] == "I":
        low  = previous + 1
        high = 10
    else:
        low  = 1
        high = previous

    for i in range(low, high):
        if str(i) not in have:
            result = deeper(have + str(i))
            if result:
                return result
    return None

The function first checks whether the length of the built string matches the required length (len(pattern) + 1). If so, a valid solution is found and returned.

The next step determines the admissible range for the next digit based on the current pattern character:

• For an I, the next digit must be strictly larger than the previous digit, so the lower bound is previous + 1 and the upper bound is 10 (exclusive of 10, because digits are 1-9).
• For a D, the next digit must be strictly smaller, so the lower bound is 1 and the upper bound is previous.

The loop iterates through this range, skipping digits already present in have. For each candidate digit, the function recurses with the extended string. The first recursive call that yields a non-null result is immediately returned, guaranteeing the smallest lexicographic solution.

Entry Point

The outer loop initiates the recursion by trying each possible first digit from 1 to 9. The moment a complete solution is discovered, it is returned.

for i in range(1, 10):
    result = deeper(str(i))
    if result:
        return result

Because the recursion is memoized with @cache, repeated sub-problems are avoided, and the search terminates as soon as the minimal valid number is found.

Edge Cases Handled

When the pattern begins with an I, the algorithm correctly forces the second digit to be larger than the first, respecting the lower bound previous + 1. Conversely, a leading D forces the second digit to be smaller, using the upper bound previous.

If the pattern contains consecutive identical symbols (e.g., “II” or “DD”), the range calculation naturally narrows the permissible digits at each step, ensuring that the monotonic relationship is preserved across multiple positions.

The code also gracefully handles the situation where no digit in the current admissible range is available because all have been used earlier in the partial string. In that case, the loop finishes without finding a candidate, and the function returns None, causing the caller to backtrack and try alternative digits.

When the pattern length is zero (empty string), the required output is a single digit. The outer loop tries digits 1 through 9; the first call to deeper immediately satisfies the length condition (len(have) == 1) and returns that digit, yielding the smallest possible number, which is 1.

Performance Optimizations

The use of @cache (Python’s built-in memoization decorator) eliminates redundant exploration of identical sub-states. Since the state is fully described by the string have, any recursive call with the same prefix reuses the previously computed result, dramatically reducing the number of recursive invocations.

The range limits (low and high) are computed before the loop, preventing unnecessary checks for digits that would violate the pattern. By iterating only over digits that could possibly satisfy the next relational constraint, the algorithm avoids a full 1-9 scan at each depth.

Skipping already-used digits (if str(i) not in have) ensures that each digit appears at most once, which is a requirement of the problem and also prunes branches that would inevitably fail later due to duplication.

Finally, the outer loop stops as soon as a valid solution is found. Because the recursion explores digits in increasing order, the first complete number encountered is guaranteed to be the smallest, allowing the algorithm to terminate without exhaustively enumerating all permutations.

Imagine building a tall tower out of number blocks. Each block has a digit from one to nine on it. The code looks for a secret pattern to help it decide which number block to pick next.

It starts by picking a first number to place at the very bottom of the tower. After that, it looks at the instructions to decide whether the next block needs to be bigger or smaller than the one that came before it. A letter I means the next number must be bigger, and a letter D means the next number must be smaller.

The code keeps testing different numbers to see if they fit the rule. If a number is already used in the tower, the code skips it and tries a different one. It follows this path deep into the list of instructions until the tower is the perfect height. When every spot is filled following the pattern, the tower is finished and all the numbers are together in a row.

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

not analyzed yet

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		Java	C++		Python			TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++		Python		Go	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fartem				Ruby
	fsq			C++
	JoshCrozier	JS
	lkwq007					Python
	Shamik07						Dart
	varunu28		Java
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
varunu28	Java
wisdompeak	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