LeetCode 756: Pyramid Transition Matrix Solution

by

December Daily Challenge – Solution Article (Backtracking + Memoization)

Problem recap

You’re given:

  • A bottom row string (e.g., "XYZ"), representing blocks in the lowest layer.
  • A list allowed, where each string has length 3, like "ABC", meaning:

If two adjacent blocks are A and B in the current row, you may place C directly above them.

You build the pyramid upward by repeatedly forming the next row:

  • If current row length is k, next row length will be k-1
  • Each character in the next row depends on a pair of adjacent characters below it
  • You succeed if you can reach a single block at the top

Return true if any valid pyramid can be built; otherwise return false.

Key observation

At any row, each adjacent pair (like "AB") can potentially produce multiple top blocks (like {"C","D","E"}).

So the task becomes:

  1. For each row, generate all possible next rows consistent with allowed rules.
  2. Recursively try to build the pyramid from each generated next row.
  3. Use memoization so you don’t recompute the same row state multiple times.

This is a classic “search + prune” problem.

Step 1: Preprocess the allowed transitions

Build a mapping:

  • Key: two-character pair "AB"
  • Value: list (or set) of possible top characters ['C', 'D', ...]

Example:

allowed = ["ABC", "ABD", "BCE"]
map["AB"] = ["C", "D"]
map["BC"] = ["E"]

This makes transitions O(1) to look up.

Step 2: DFS (backtracking) to build the pyramid

Define a function:

  • canBuild(row) returns whether you can build a pyramid from this row up to the top.

Base case:

  • If len(row) == 1, you’ve reached the top → return True

Recursive case:

  • Generate all possible next rows using backtracking:
    • At position i in the next row, look at pair row[i:i+2]
    • Try every possible top character from the map

Important pruning:

  • If any pair does not exist in the map, this row is impossible → return False immediately

Step 3: Memoization

Many different paths can produce the same intermediate row.

Example:

  • One way generates "BCD"
  • Another way also generates "BCD"

From that point onward, the result is identical.
So store results in memo[row] = True/False.

This drastically reduces repeated work.

Python solution (clean + fast enough for constraints)

from collections import defaultdict
from functools import lru_cache

class Solution:
    def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
        # Map pair -> list of possible top blocks
        nxt = defaultdict(list)
        for triple in allowed:
            nxt[triple[:2]].append(triple[2])

        @lru_cache(None)
        def can_build(row: str) -> bool:
            # If we reached the top
            if len(row) == 1:
                return True

            # Early prune: if any required pair has no transitions
            for i in range(len(row) - 1):
                if row[i:i+2] not in nxt:
                    return False

            # Backtracking to generate the next row
            def build_next(i: int, path: list[str]) -> bool:
                if i == len(row) - 1:
                    return can_build("".join(path))

                pair = row[i:i+2]
                for ch in nxt[pair]:
                    path.append(ch)
                    if build_next(i + 1, path):
                        return True
                    path.pop()

                return False

            return build_next(0, [])

        return can_build(bottom)

Complexity discussion

Let n = len(bottom).

  • Pyramid height is n
  • Next-row branching depends on how many tops each pair can produce
    (in worst case it’s large), so brute force can be exponential.

However:

  • In LeetCode 756, n is small (commonly ≤ 8 in many versions of the problem)
  • Memoization means each distinct intermediate row is solved once
  • Early pruning cuts dead branches quickly

So this approach is the standard accepted solution for the problem.

Common pitfalls and how this solution avoids them

1) Forgetting to prune impossible pairs

If any pair "AB" has no allowed top, the entire row fails immediately.

✅ We check this early.

2) Recomputing the same row many times

Without memoization, the recursion can explode.

✅ We use @lru_cache to memoize can_build(row).

3) Building next rows incorrectly

You must build len(row)-1 characters, each from row[i:i+2].

✅ The helper builds exactly one character per adjacent pair.

Optional optimization idea

If the block alphabet is limited (e.g., letters A-G), you can store transitions as bitmasks and generate next rows faster. It’s not necessary for typical constraints, but it’s a good performance trick.

Final takeaway

LeetCode 756 is best solved with:

  • pair → possible tops preprocessing
  • DFS + backtracking to generate candidate upper rows
  • memoization to avoid repeated work

This combination makes the solution both clean and efficient.