Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Choosing an allowed block for one pair does not guarantee the next row can support a complete pyramid. We must explore combinations across the whole row. Once a row is fixed, however, everything above it depends only on that row, not on the choices that produced it, so repeated row states can be skipped.

Approach

Map each ordered pair of lower colors to its allowed upper colors; reversing a pair is not equivalent.
Build the next row from left to right by trying each allowed color for the current adjacent pair. A pair with no allowed color ends that branch.
When the row is complete, recurse upward unless it is cached. Python records the completed row before descending; JavaScript records it only after failure. Rows strictly shorten, so the same row cannot recur during its own exploration, and success exits the entire search. Thus any cached row encountered later has already failed.
Return true when a row has length one, and propagate success immediately. Return false only after every available color choice fails.

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        n = len(bottom)
        map = defaultdict(list)

        for a, b, c in allowed:
            map[a + b].append(c)

        seen = set()

        def bt(bottom, row, i):
            n = len(bottom)
            if n == 1:
                return True
            if i == n:
                if row in seen:
                    return False
                seen.add(row)
                return bt(row, "", 1)

            pair = bottom[i - 1] + bottom[i]

            for curr in map[pair]:
                if bt(bottom, row + curr, i + 1):
                    return True

            return False

        return bt(bottom, "", 1)

Complexity analysis

Let b be the bottom length, a the number of allowed rules, and A the maximum number of tops allowed for a pair (zero if there are no rules). There are P = b(b - 1) / 2 positions above the bottom. A conservative bound including rule preprocessing, immutable-string copying and hashing is O(a + b^3 * max(1, A)^P) time; row memoization can prune much of this search. If M completed rows are retained, auxiliary space is O(a + Mb + b^3): cached strings cost O(Mb), while the active O(b^2) recursive frames can retain O(b^3) characters across all partial-row prefixes. With six colors, M is at most the sum of 6^r for row lengths 1 <= r < b, so memo storage can be exponential. These are generalized bounds; the actual problem restricts b <= 6.