LeetCode 756: Pyramid Transition Matrix

Problem Restatement

We are given a bottom row of blocks.

Each block has a color represented by one letter.

We are also given a list of allowed triples. A triple has length 3.

For example:

"ABC"

means:

A B
 C

If two adjacent blocks are A and B, then we may place C on top of them.

Starting from the given bottom row, we need to decide whether it is possible to build the pyramid all the way to one block at the top.

Input and Output

Example function shape:

def pyramidTransition(bottom: str, allowed: list[str]) -> bool:
    ...

Examples

Example 1:

bottom = "BCD"
allowed = ["BCG", "CDE", "GEA", "FFF"]

Output:

True

We can build:

  A
 G E
B C D

The pair "BC" can produce "G" because "BCG" is allowed.

The pair "CD" can produce "E" because "CDE" is allowed.

Then the pair "GE" can produce "A" because "GEA" is allowed.

So the pyramid can reach the top.

Example 2:

bottom = "AABA"
allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]

Output:

False

There is no way to choose blocks above each row so that the pyramid reaches a single top block.

First Thought: Try All Possible Rows

Each row depends on the row below it.

For a row like:

AABA

we need to build a row of length 3.

The adjacent pairs are:

AA
AB
BA

For each pair, there may be zero, one, or many possible top blocks.

So we need to try all combinations for the next row.

After building one possible next row, we repeat the same process until the row length becomes 1.

This is a natural backtracking problem.

Key Insight

Instead of thinking about the whole pyramid at once, ask this smaller question:

Given the current row, can we build a valid pyramid above it?

If the row has length 1, the answer is True.

Otherwise, we generate every possible row above the current row. If any generated row can reach the top, the current row is also possible.

This gives a recursive solution.

Preprocessing Allowed Triples

We should not scan the full allowed list every time we see a pair.

Instead, build a map from each bottom pair to all possible top blocks.

For example:

allowed = ["BCG", "BCD", "CDE"]

Then the map is:

{
    "BC": ["G", "D"],
    "CD": ["E"],
}

Code:

from collections import defaultdict

top_blocks = defaultdict(list)

for triple in allowed:
    pair = triple[:2]
    top = triple[2]
    top_blocks[pair].append(top)

Now we can quickly answer:

What blocks can go above this pair?

Generating the Next Row

Suppose the current row is:

row = "AABA"

We need one block above each adjacent pair.

The pairs are:

AA, AB, BA

If:

AA -> ["A", "B"]
AB -> ["A", "B"]
BA -> ["C"]

then possible next rows include:

AAC
ABC
BAC
BBC

We can generate these rows with DFS.

There are two levels of recursion:

1. Build one next row from left to right.
2. Recursively check whether that next row can reach the top.

Algorithm

1. Build a dictionary top_blocks:
   1. key: two-letter bottom pair
   2. value: list of possible top letters
2. Define can_build(row):
   1. If len(row) == 1, return True.
   2. Generate every possible row above row.
   3. If any generated row satisfies can_build(next_row), return True.
   4. Otherwise return False.
3. Use memoization so the same row is not solved repeatedly.
4. Return can_build(bottom).

Correctness

The dictionary top_blocks stores exactly the allowed moves from each adjacent pair to a possible upper block.

For any row of length greater than 1, a valid next row must choose one allowed top block for every adjacent pair in that row. The generation step tries every such choice. Therefore, it produces exactly all valid rows that can be placed directly above the current row.

The recursive function returns True for a row of length 1, because a one-block row is already the top of a complete pyramid.

For a longer row, the function returns True if at least one valid next row can itself reach the top. This matches the definition of being able to build a pyramid above the current row.

If no generated next row can reach the top, then every possible immediate choice fails, so no valid pyramid exists from that row.

By induction on row length, can_build(row) returns True exactly when a valid pyramid can be built above row. Therefore, can_build(bottom) gives the correct answer.

Complexity

Let m = len(bottom).

The maximum row length is at most 8, and letters come from a small fixed set. In the worst case, many possible rows may be generated.

With the problem constraints, DFS with memoization is efficient enough.

Implementation

from collections import defaultdict
from functools import lru_cache

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

        for triple in allowed:
            pair = triple[:2]
            top = triple[2]
            top_blocks[pair].append(top)

        @lru_cache(None)
        def can_build(row: str) -> bool:
            if len(row) == 1:
                return True

            candidates = []

            def build_next(index: int, path: list[str]) -> bool:
                if index == len(row) - 1:
                    next_row = "".join(path)
                    return can_build(next_row)

                pair = row[index:index + 2]

                if pair not in top_blocks:
                    return False

                for top in top_blocks[pair]:
                    path.append(top)

                    if build_next(index + 1, path):
                        return True

                    path.pop()

                return False

            return build_next(0, [])

        return can_build(bottom)

Code Explanation

We first group allowed triples by their bottom pair:

top_blocks = defaultdict(list)

for triple in allowed:
    pair = triple[:2]
    top = triple[2]
    top_blocks[pair].append(top)

If triple = "BCG", then:

pair = "BC"
top = "G"

So "G" is one possible block above "BC".

The main recursive function is:

@lru_cache(None)
def can_build(row: str) -> bool:

It answers whether a full pyramid can be built from row.

The base case is:

if len(row) == 1:
    return True

A single block means the pyramid is complete.

Inside can_build, we define another helper:

def build_next(index: int, path: list[str]) -> bool:

This helper builds the next row one character at a time.

The variable index tells us which adjacent pair in row we are processing.

The list path stores the partial next row.

When index == len(row) - 1, we have placed one block above every adjacent pair:

next_row = "".join(path)
return can_build(next_row)

If a pair has no possible top block, this path cannot work:

if pair not in top_blocks:
    return False

Otherwise, we try every allowed top block:

for top in top_blocks[pair]:
    path.append(top)

    if build_next(index + 1, path):
        return True

    path.pop()

If any choice succeeds, we immediately return True.

If every choice fails, we return False.

The final answer is:

return can_build(bottom)

Testing

def run_tests():
    s = Solution()

    assert s.pyramidTransition(
        "BCD",
        ["BCG", "CDE", "GEA", "FFF"],
    ) is True

    assert s.pyramidTransition(
        "AABA",
        ["AAA", "AAB", "ABA", "ABB", "BAC"],
    ) is False

    assert s.pyramidTransition(
        "AA",
        ["AAB"],
    ) is True

    assert s.pyramidTransition(
        "AA",
        [],
    ) is False

    assert s.pyramidTransition(
        "ABC",
        ["ABD", "BCE", "DEF"],
    ) is True

    print("all tests passed")

run_tests()

Test meaning: