3906. Count Good Integers on a Grid Path

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integers l and r, along with a string directions that contains exactly three 'D' characters and three 'R' characters. The goal is to count how many integers in the range [l, r] (inclusive) qualify as good, based on a specific path-tracing rule applied to each number.

For every integer x in the range [l, r], the following process is carried out:

Pad the number: If x has fewer than 16 digits, add leading zeros on the left so that it becomes a 16-digit string.
Build a grid: Arrange the 16 digits into a 4 × 4 grid in row-major order. This means the first 4 digits form the first row (left to right), the next 4 digits form the second row, and so on until all 16 digits fill the grid.
Trace a path: Begin at the top-left cell (row = 0, column = 0), then follow the 6 characters in directions one by one:
- A 'D' moves down by increasing the row by 1.
- An 'R' moves right by increasing the column by 1.
Record the digits: Collect the digits of every cell visited along the path, including the starting cell. Since you begin at one cell and make 6 moves, this produces a sequence of exactly 7 digits.

An integer x is considered good if the recorded sequence of 7 digits is non-decreasing (each digit is greater than or equal to the one before it).

Your task is to return an integer representing the total count of good integers within the range [l, r].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

The optimal solution decomposes into overlapping subproblems solved with DP.

Open in Flowchart

Intuition

The first thing to notice is that the directions string is fixed, and the starting point is always the top-left cell. This means the path through the 4 × 4 grid is completely determined before we even look at any number. No matter which integer x we examine, the same 7 cells get visited in the same order.

Because the digits are placed into the grid in row-major order, each cell maps directly to a position in the 16-digit string. A cell at row and column corresponds to index row * 4 + column. So instead of physically building a grid for every number, we can precompute exactly which of the 16 string positions lie on the path. We store this in a boolean array key of length 16, where key[i] is true if position i is visited by the path.

Once we know the key positions, being "good" simply means: the digits sitting at those key positions, read in the order they are visited, must be non-decreasing. Since the path moves only down and right, the visited positions naturally increase in index order, so we can check the non-decreasing condition while scanning the 16 digits from left to right.

Now the challenge becomes counting how many numbers in [l, r] satisfy this digit constraint. The range can be enormous (up to 16 digits), so checking each number one by one is far too slow. This is the classic signal for digit DP: we count valid numbers by building them digit by digit, keeping track of just enough state to know whether the constraint still holds.

To handle the range [l, r], we use the standard trick of computing the count over [0, r] and subtracting the count over [0, l - 1]. Each of these is found by treating the upper bound as a 16-digit string s and counting valid 16-digit sequences that do not exceed it.

For the DP state, we track three things:

pos: the current digit position we are filling.
last: the digit value placed at the previous key cell, so we can enforce that the next key cell's digit is at least this value (keeping the sequence non-decreasing).
lim: whether the prefix built so far still matches s exactly, which controls the maximum digit we may place at the current position.

At each position, if it is a key cell, the digit must be at least last and we update last to the chosen digit. If it is not a key cell, the digit is unconstrained (it can be anything from 0 to its upper bound) and last stays the same. The upper bound is s[pos] when we are still tight against the limit, otherwise it is 9. Summing over all valid choices at every position gives the total count, and memoization on the state makes this efficient.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

We use Digit DP to count the valid integers efficiently.

Step 1: Precompute the key positions.

Since the path is fixed by directions, we first build a boolean array key of length 16. We start at the top-left cell, so row = 0, col = 0, and mark key[0] = True. Then we walk through each character of directions:

If the character is 'D', increment row.
Otherwise ('R'), increment col.

After each move, the visited cell corresponds to string index row * 4 + col, so we set key[row * 4 + col] = True. After processing all 6 characters, exactly 7 positions in key are marked as True, representing the cells visited along the path.

Step 2: Define the recursive DP function.

We define dfs(pos, last, lim):

pos — the current digit position being filled (from 0 to 16).
last — the digit placed at the most recently visited key cell, used to enforce the non-decreasing rule.
lim — whether the prefix is still tight against the upper-bound string s.

The logic inside the function works as follows:

Base case: if pos == 16, all digits have been placed successfully, so return 1.
Determine the digit range:
- The lower bound start is last if key[pos] is True (the digit must not be smaller than the previous key digit), otherwise it is 0.
- The upper bound end is int(s[pos]) if lim is True, otherwise it is 9.
Enumerate digits from start to end. For each choice i, we recurse into the next position:
- The new last becomes i if the current cell is a key cell (key[pos]), otherwise it stays as last.
- The new lim is lim and (i == end), staying tight only when we pick the maximum allowed digit.
We accumulate the results of all branches into res and return it.

The @cache decorator memoizes results based on (pos, last, lim), avoiding recomputation of identical subproblems.

Step 3: Count over a prefix range with calc(x).

The helper calc(x) returns the number of good integers in [0, x]:

If x < 0, return 0.
Convert x into a 16-digit string using str(x).zfill(16) and store it in s.
Clear the cache with dfs.cache_clear() since s has changed, then call dfs(0, 0, True).

Step 4: Combine results for the range [l, r].

Using the standard prefix-subtraction technique, the final answer is:

calc(r) - calc(l - 1)

This subtracts the count of good integers in [0, l - 1] from the count in [0, r], leaving exactly the count in [l, r].

Complexity Analysis:

Time complexity: O(16 × 10 × 10 × 2) per calc call, since pos has 16 values, last has 10 possible digits, lim has 2 states, and each state enumerates up to 10 digits. This is effectively constant, so the overall time is O(1) with respect to the magnitude of the inputs.
Space complexity: O(16 × 10 × 2) for the memoization cache plus the key array, which is also effectively constant.

Example Walkthrough

Let's trace through a small example to see how the solution approach works.

Setup: Suppose directions = "DDRRRD" and we want to check whether the number x = 1234567890123456 is good.

Step 1: Precompute the key positions.

We start at row = 0, col = 0, and mark key[0] = True (position 0 * 4 + 0 = 0).

Now we process each character of "DDRRRD":

Char	Action	row	col	Index `row*4+col`	Mark
`D`	row+1	1	0	4	`key[4] = True`
`D`	row+1	2	0	8	`key[8] = True`
`R`	col+1	2	1	9	`key[9] = True`
`R`	col+1	2	2	10	`key[10] = True`
`R`	col+1	2	3	11	`key[11] = True`
`D`	row+1	3	3	15	`key[15] = True`

So the key positions (in path order) are: 0, 4, 8, 9, 10, 11, 15 — exactly 7 positions.

Step 2: Map the number onto the grid.

The digits of x = 1234567890123456 already have 16 digits, so no padding is needed. Filling row-major into the 4 × 4 grid:

Index:  0  1  2  3      Digits:  1  2  3  4
        4  5  6  7               5  6  7  8
        8  9 10 11               9  0  1  2
       12 13 14 15               3  4  5  6

The path visits cells (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (3,3), which corresponds to digits at indices 0, 4, 8, 9, 10, 11, 15:

index 0 → 1
index 4 → 5
index 8 → 9
index 9 → 0
index 10 → 1
index 11 → 2
index 15 → 6

Recorded sequence: 1, 5, 9, 0, 1, 2, 6.

Is it non-decreasing? Going from 9 to 0 drops, so the sequence is not non-decreasing. Therefore x = 1234567890123456 is not good.

(If instead the third row started higher, e.g. digits 1 5 9 9 9 9 ... 9, the sequence 1,5,9,9,9,9,9 would be non-decreasing and the number would be good.)

Step 3: How the DP counts numbers in a range.

Now imagine we want calc(r) where r = 0000000000000019 (i.e. count good numbers in [0, 19]). We set s = "0000000000000019" and call dfs(0, 0, True).

Because the only key positions among the first 15 indices are 0, 4, 8, 9, 10, 11 — and for small numbers like 0–19 those leading positions are all 0 — the constraint effectively forces the early key digits to be 0, then last carries that 0 forward. The final key position is index 15 (the last digit).

Walking the DP conceptually for [0, 19]:

Positions 0–14 are forced to 0 while staying tight (lim = True) since s has zeros there. Every key cell among them places 0, so last = 0.
At position 15 (a key cell), start = last = 0 and, when tight, end = int(s[15]) = 9. So the last digit may be 0 through 9, all satisfying "≥ 0".
The tens digit at index 14 (not a key cell) could also be 0 or 1 depending on tightness, expanding the count up to 19.

Every number from 0 to 19 ends up with a recorded sequence of six 0s followed by the final digit, which is always non-decreasing. So calc(19) returns 20.

Step 4: Combine for [l, r].

If the original range were [l, r] = [5, 19], we compute:

answer = calc(19) - calc(4)
       = 20 - 5
       = 15

which correctly counts the 15 good integers 5, 6, 7, ..., 19.

This shows how precomputing the fixed key path reduces "goodness" to a simple non-decreasing check on selected digit positions, and how digit DP counts all qualifying numbers without iterating over the entire range.

Solution Implementation

1from functools import cache
2
3
4class Solution:
5    def countGoodIntegersOnPath(self, l: int, r: int, directions: str) -> int:
6        # Mark which of the 16 grid cells (4x4, flattened row-major) lie on the path.
7        on_path = [False] * 16
8        row, col = 0, 0
9        on_path[0] = True  # The start cell (0, 0) is always on the path.
10        for ch in directions:
11            if ch == "D":
12                row += 1
13            else:  # "R"
14                col += 1
15            on_path[row * 4 + col] = True
16
17        # Holds the current upper-bound number as a 16-char, zero-padded string.
18        bound = ""
19
20        @cache
21        def dfs(pos: int, last: int, tight: bool) -> int:
22            """
23            Count valid completions starting from digit index `pos`.
24
25            pos   : current digit position (0..16) in the flattened grid.
26            last  : the most recent digit placed on a path cell (path digits
27                    must be non-decreasing).
28            tight : whether the prefix so far equals the upper bound's prefix,
29                    constraining the current digit's max value.
30            """
31            if pos == 16:
32                return 1
33
34            total = 0
35            # Path cells must be >= the previous path digit; others start from 0.
36            start = last if on_path[pos] else 0
37            # If tight, the digit cannot exceed the bound's digit at this position.
38            end = int(bound[pos]) if tight else 9
39
40            for digit in range(start, end + 1):
41                # Update `last` only when this cell is on the path.
42                next_last = digit if on_path[pos] else last
43                # Remain tight only if we picked the maximal allowed digit.
44                next_tight = tight and digit == end
45                total += dfs(pos + 1, next_last, next_tight)
46
47            return total
48
49        def count_up_to(x: int) -> int:
50            """Count valid integers in [0, x] (0 if x < 0)."""
51            nonlocal bound
52            if x < 0:
53                return 0
54            bound = str(x).zfill(16)
55            dfs.cache_clear()  # Cache depends on `bound`, so reset per call.
56            return dfs(0, 0, True)
57
58        # Inclusion-exclusion over the range [l, r].
59        return count_up_to(r) - count_up_to(l - 1)
60

1class Solution {
2    // Marks which positions (grid cells) lie on the path; on-path digits must be non-decreasing
3    private boolean[] onPath;
4    // Memoization table: memo[pos][last] caches results when not bounded by the upper limit
5    private long[][] memo;
6    // The current upper-bound number, left-padded to 16 digits
7    private String upperBound;
8
9    public long countGoodIntegersOnPath(long l, long r, String directions) {
10        // 4x4 grid flattened into 16 positions
11        onPath = new boolean[16];
12        int row = 0, col = 0;
13
14        // The starting cell (top-left) is always on the path
15        onPath[0] = true;
16
17        // Walk the directions: 'D' moves down a row, otherwise move right a column.
18        // Each visited cell is marked as on the path.
19        for (char c : directions.toCharArray()) {
20            if (c == 'D') {
21                row++;
22            } else {
23                col++;
24            }
25            onPath[row * 4 + col] = true;
26        }
27
28        // Count valid integers in [l, r] using inclusion-exclusion: f(r) - f(l-1)
29        return calc(r) - calc(l - 1);
30    }
31
32    /**
33     * Digit DP traversal over the 16 positions.
34     *
35     * @param pos   current digit position (0..16)
36     * @param last  the previous digit chosen at an on-path cell (used to enforce non-decreasing order)
37     * @param limit whether the digits so far are still tight against the upper bound
38     * @return number of valid completions from this state
39     */
40    private long dfs(int pos, int last, boolean limit) {
41        // All 16 positions filled: one valid number formed
42        if (pos == 16) {
43            return 1;
44        }
45
46        // Use cached result only when free of the upper-bound constraint
47        if (!limit && memo[pos][last] != -1) {
48            return memo[pos][last];
49        }
50
51        long res = 0;
52
53        // On-path cells must be >= last (non-decreasing); other cells can start from 0
54        int start = onPath[pos] ? last : 0;
55        // When tight, the max digit is bounded by the corresponding digit of upperBound
56        int end = limit ? (upperBound.charAt(pos) - '0') : 9;
57
58        for (int i = start; i <= end; i++) {
59            // Update 'last' only when the current cell is on the path
60            res += dfs(pos + 1, onPath[pos] ? i : last, limit && (i == end));
61        }
62
63        // Cache the unconstrained result
64        if (!limit) {
65            memo[pos][last] = res;
66        }
67        return res;
68    }
69
70    /**
71     * Counts valid integers in the range [0, x].
72     *
73     * @param x inclusive upper bound
74     * @return number of valid integers not exceeding x
75     */
76    private long calc(long x) {
77        if (x < 0) {
78            return 0;
79        }
80
81        // Left-pad x with zeros to a fixed width of 16 digits
82        String t = String.valueOf(x);
83        StringBuilder sb = new StringBuilder();
84        for (int i = 0; i < 16 - t.length(); i++) {
85            sb.append('0');
86        }
87        upperBound = sb.append(t).toString();
88
89        // Reset memoization table for this bound
90        memo = new long[16][10];
91        for (long[] row : memo) {
92            Arrays.fill(row, -1);
93        }
94
95        // Start the DP from position 0, no previous digit (0), tightly bounded
96        return dfs(0, 0, true);
97    }
98}
99

1class Solution {
2public:
3    long long countGoodIntegersOnPath(long long l, long long r, string directions) {
4        // onPath[c] marks whether cell c (in a flattened 4x4 grid) lies on the path.
5        bool onPath[16];
6        memset(onPath, 0, sizeof(onPath));
7
8        int row = 0, col = 0;
9        onPath[0] = true;            // path always starts at the top-left cell (0,0)
10        for (char c : directions) {
11            if (c == 'D') {
12                ++row;               // move down
13            } else {
14                ++col;               // move right
15            }
16            onPath[row * 4 + col] = true;   // mark the visited cell
17        }
18
19        // memo[pos][last]: number of ways to fill cells from index `pos` to the end,
20        // given the last digit chosen on the path so far was `last`,
21        // valid only when there is no tight (upper-bound) limit.
22        long long memo[16][10];
23
24        // The padded 16-digit string of the current upper bound being counted.
25        string upperBound;
26
27        // Digit DP traversal.
28        //   pos : current cell index (0..16)
29        //   last: the most recent digit placed on a path cell (enforces non-decreasing)
30        //   tight: whether the prefix is still equal to the upper bound (limit active)
31        auto dfs = [&](this auto&& dfs, int pos, int last, bool tight) -> long long {
32            // All 16 cells filled: one valid configuration counted.
33            if (pos == 16) {
34                return 1;
35            }
36            // Reuse memoized result only when not bounded by the upper limit.
37            if (!tight && memo[pos][last] != -1) {
38                return memo[pos][last];
39            }
40
41            long long res = 0;
42            // On a path cell the digit must be >= last; off-path cells start from 0.
43            int start = onPath[pos] ? last : 0;
44            // When tight, the digit cannot exceed the corresponding upper-bound digit.
45            int end = tight ? (upperBound[pos] - '0') : 9;
46
47            for (int digit = start; digit <= end; ++digit) {
48                res += dfs(pos + 1,
49                           onPath[pos] ? digit : last,      // update last only on path cells
50                           tight && (digit == end));        // stay tight only on the boundary digit
51            }
52
53            if (!tight) {
54                memo[pos][last] = res;
55            }
56            return res;
57        };
58
59        // Count valid configurations whose 16-digit value is <= x.
60        auto countUpTo = [&](long long x) -> long long {
61            if (x < 0) {
62                return 0LL;
63            }
64            string num = to_string(x);
65            // Left-pad to a fixed 16-digit representation.
66            upperBound = string(16 - num.length(), '0') + num;
67            memset(memo, -1, sizeof(memo));
68            return dfs(0, 0, true);
69        };
70
71        // Inclusive range count: f(r) - f(l - 1).
72        return countUpTo(r) - countUpTo(l - 1);
73    }
74};
75

1/**
2 * Counts "good integers" along a path traced through a 4x4 grid.
3 *
4 * The grid has 16 cells, each cell mapped to a digit position in a 16-digit number.
5 * The `directions` string traces a path: 'D' moves down a row, otherwise moves right a column.
6 * Cells visited on the path are "key" cells, where digits must be non-decreasing
7 * relative to the previous key cell's digit.
8 *
9 * @param l - Lower bound of the range (inclusive).
10 * @param r - Upper bound of the range (inclusive).
11 * @param directions - String of moves ('D' for down, otherwise right) describing the path.
12 * @returns The number of valid integers in the range [l, r].
13 */
14function countGoodIntegersOnPath(l: number, r: number, directions: string): number {
15    // Marks which of the 16 grid cells (positions) lie on the traced path.
16    const isKeyCell: boolean[] = new Array(16).fill(false);
17
18    // Start tracing from the top-left cell (row 0, col 0).
19    let row = 0;
20    let col = 0;
21    isKeyCell[0] = true;
22
23    // Walk through the directions, marking each visited cell as a key cell.
24    // The cell index in the flattened 4x4 grid is (row * 4 + col).
25    for (const move of directions) {
26        if (move === 'D') {
27            row++; // Move down one row.
28        } else {
29            col++; // Move right one column.
30        }
31        isKeyCell[row * 4 + col] = true;
32    }
33
34    // Padded string form of the current upper bound being processed by the digit DP.
35    let upperBound: string;
36
37    // Memoization table: memo[position][lastDigit] caches results when not tightly bounded.
38    let memo: number[][];
39
40    /**
41     * Digit DP that counts valid numbers position by position.
42     *
43     * @param position - Current digit position (0 to 15).
44     * @param lastDigit - The digit chosen at the previous key cell (constraint for current key cell).
45     * @param isLimited - Whether we are still tightly bounded by the upper bound's digits.
46     * @returns The count of valid completions from this state.
47     */
48    const dfs = (position: number, lastDigit: number, isLimited: boolean): number => {
49        // All 16 positions filled: this forms one valid number.
50        if (position === 16) {
51            return 1;
52        }
53
54        // Use cached result only when not tightly bounded (free choice of digits).
55        if (!isLimited && memo[position][lastDigit] !== -1) {
56            return memo[position][lastDigit];
57        }
58
59        let result = 0;
60
61        // For key cells, the digit must be >= lastDigit (non-decreasing along the path).
62        // For non-key cells, any digit starting from 0 is allowed.
63        const start = isKeyCell[position] ? lastDigit : 0;
64
65        // The maximum allowed digit: bounded by the upper bound when tightly limited.
66        const end = isLimited ? parseInt(upperBound[position]) : 9;
67
68        for (let digit = start; digit <= end; digit++) {
69            // Propagate lastDigit only when the current cell is a key cell.
70            const nextLast = isKeyCell[position] ? digit : lastDigit;
71            // Remain limited only if still bounded and we picked the maximum allowed digit.
72            const nextLimited = isLimited && digit === end;
73            result += dfs(position + 1, nextLast, nextLimited);
74        }
75
76        // Cache results for unbounded states to enable reuse.
77        if (!isLimited) {
78            memo[position][lastDigit] = result;
79        }
80        return result;
81    };
82
83    /**
84     * Counts valid integers in the range [0, x].
85     *
86     * @param x - The upper bound to count up to.
87     * @returns The count of valid integers from 0 to x, or 0 if x is negative.
88     */
89    const calc = (x: number): number => {
90        if (x < 0) {
91            return 0;
92        }
93
94        // Represent x as a 16-digit zero-padded string for positional processing.
95        upperBound = x.toString().padStart(16, '0');
96
97        // Reset the memoization table (16 positions x 10 possible last digits).
98        memo = Array.from({ length: 16 }, () => new Array(10).fill(-1));
99
100        // Begin the DP from position 0, no previous digit, fully bounded.
101        return dfs(0, 0, true);
102    };
103
104    // Count in [0, r] minus count in [0, l - 1] gives the count in [l, r].
105    return calc(r) - calc(l - 1);
106}
107

Time and Space Complexity

Time Complexity: O(D² × log r)

The core of the algorithm is the digit DP implemented by the dfs function, which is memoized via @cache.

The state of dfs is defined by three parameters: pos, last, and lim.
- pos ranges over the number of digit positions, which is 16 here, but more generally is O(log r) (the number of digits in r).
- last represents the previous digit on the path constraint and ranges over 0 to 9, giving O(D) distinct values where D = 10.
- lim is a boolean flag with only 2 possible values, contributing a constant factor.
Therefore, the number of distinct states is O(log r × D × 2) = O(D × log r).
For each state, the dfs function iterates through a loop from start to end, which can run up to D = 10 times.
Thus, the total work is O(D × log r) × O(D) = O(D² × log r).

The two calls calc(r) and calc(l - 1) each clear the cache and rerun the DP, but this only adds a constant factor and does not change the asymptotic complexity.

Space Complexity: O(D × log r)

The space is dominated by the memoization cache, which stores one entry per distinct dfs state. As analyzed above, the number of states is O(D × log r). The recursion stack depth is bounded by the number of positions, O(log r), which is subsumed by the cache size. The key array and string s use O(log r) space. Hence the overall space complexity is O(D × log r).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Forgetting to clear the memoization cache between `calc(r)` and `calc(l - 1)`

The most common and subtle bug in this Digit DP solution comes from the interaction between the @cache decorator and the mutable shared state bound.

Why this happens:

The recursive function dfs(pos, last, tight) does not include bound in its parameter list. Instead, bound is captured as a closure variable that changes between calls to count_up_to. The cache, however, only keys on (pos, last, tight).

Consider the execution order:

count_up_to(r) sets bound = str(r).zfill(16) and populates the cache.
count_up_to(l - 1) sets bound = str(l - 1).zfill(16) — a different upper bound.

If the cache is not cleared between these two calls, then any cached result computed for r will be incorrectly reused for l - 1. The danger is concentrated in states where tight=False: those results genuinely don't depend on bound, so they're valid to reuse. But states with tight=True depend directly on the digits of bound. Mixing them produces silently wrong answers — no crash, no error, just an incorrect count.

The fix (already present in the code):

def count_up_to(x: int) -> int:
    nonlocal bound
    if x < 0:
        return 0
    bound = str(x).zfill(16)
    dfs.cache_clear()  # ← Critical: cache depends on `bound`, reset per call.
    return dfs(0, 0, True)

The line dfs.cache_clear() invalidates all previously memoized results so each count_up_to call starts fresh with its own bound.

A more robust alternative — make tight results safe to cache across bounds:

A cleaner design avoids the hidden dependency entirely. Notice that when tight=True, results genuinely cannot be shared across different bounds, but when tight=False, they always can. You can exploit this by only caching the non-tight states, which lets you keep the cache across both count_up_to calls without clearing:

def countGoodIntegersOnPath(self, l: int, r: int, directions: str) -> int:
    on_path = [False] * 16
    row = col = 0
    on_path[0] = True
    for ch in directions:
        if ch == "D":
            row += 1
        else:
            col += 1
        on_path[row * 4 + col] = True

    bound = ""

    @cache
    def dfs_free(pos: int, last: int) -> int:
        """Count completions when NOT tight — independent of `bound`."""
        if pos == 16:
            return 1
        start = last if on_path[pos] else 0
        total = 0
        for digit in range(start, 10):
            next_last = digit if on_path[pos] else last
            total += dfs_free(pos + 1, next_last)
        return total

    def dfs_tight(pos: int, last: int) -> int:
        """Walk the tight prefix; delegate to the cached free function."""
        if pos == 16:
            return 1
        start = last if on_path[pos] else 0
        end = int(bound[pos])
        total = 0
        for digit in range(start, end + 1):
            next_last = digit if on_path[pos] else last
            if digit == end:
                total += dfs_tight(pos + 1, next_last)   # still tight
            else:
                total += dfs_free(pos + 1, next_last)    # now free, cacheable
        return total

    def count_up_to(x: int) -> int:
        nonlocal bound
        if x < 0:
            return 0
        bound = str(x).zfill(16)
        return dfs_tight(0, 0)  # No cache_clear needed!

    return count_up_to(r) - count_up_to(l - 1)

Here dfs_free never references bound, so its cache stays valid across both count_up_to(r) and count_up_to(l - 1) calls. This eliminates the repeated cache rebuilding and removes the fragile requirement to remember cache_clear(), making the solution both faster and harder to break.

Secondary Pitfall: Initial `last = 0` is correct but easy to misjudge

It might look suspicious to start with last = 0, since one could worry it forces the first path digit to be ≥ 0. In practice this is harmless because every digit is already ≥ 0 — the very first path cell (on_path[0] is always True) effectively has no lower constraint. Just be careful not to "fix" this by initializing last to some other value (like -1), which would break the @cache key domain and complicate the digit range logic without any benefit.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: