Hard — Dynamic Programming | Digit DP | Math

The Problem

Given integers l, r, and a string directions of 'D' (down) and 'R' (right), trace a path on a 4x4 grid starting at (0,0). Each cell maps to a digit position in a 16-digit number. Count how many integers in [l, r] have non-decreasing digits along the path.

Approach

First, convert the path directions into a set of 1D indices on the 16-digit number. Then use digit DP to count valid numbers up to a limit. The DP tracks three states:

• idx — current digit position (0–15)
• is_tight — whether we’re still bounded by the limit
• last_val — the last digit placed at a path position (next path digit must be ≥ this)

For positions on the path, enforce non-decreasing order. For positions off the path, place any valid digit freely. The final answer is count_valid(r) - count_valid(l - 1).

Time: O(16 × 2 × 10 × 10) · Space: O(16 × 2 × 10)

Code

class Solution:
    def countGoodIntegersOnPath(self, l: int, r: int, directions: str) -> int:
        path_set = set()
        row, col = 0, 0
        path_set.add(0)
        for d in directions:
            if d == 'D':
                row += 1
            else:
                col += 1
            path_set.add(row * 4 + col)

        def count_valid(limit: int) -> int:
            limit_str = str(limit).zfill(16)
            memo = {}
            def dp(idx, is_tight, last_val):
                if idx == 16:
                    return 1
                state = (idx, is_tight, last_val)
                if state in memo:
                    return memo[state]
                res = 0
                upper_bound = int(limit_str[idx]) if is_tight else 9
                for d in range(upper_bound + 1):
                    if idx in path_set:
                        if d >= last_val:
                            res += dp(idx + 1, is_tight and (d == upper_bound), d)
                    else:
                        res += dp(idx + 1, is_tight and (d == upper_bound), last_val)
                memo[state] = res
                return res
            return dp(0, True, 0)

        return count_valid(r) - count_valid(l - 1)

Watch It Run

Try it yourself: Open TraceLit and step through every line. Set breakpoints to watch the memo dict build up.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment