Pyramid Transition Matrix: Backtracking with Allowed Triples

You are given a bottom row of a pyramid as a string and a list of allowed triples. Each triple "XYZ" means that block X adjacent to block Y can support block Z on top. Your job is to determine whether you can build the entire pyramid, row by row, all the way up to a single block at the top. This is LeetCode 756: Pyramid Transition Matrix.

The key insight is that you build the pyramid row by row from bottom to top. For each adjacent pair in the current row, you look up which letters are allowed on top. If a pair has multiple options, you try each one. If a choice eventually leads to a dead end, you backtrack and try a different letter. This is a classic recursive backtracking problem where the search space is the product of choices at each position.

Problem statement

You are given a string bottom representing the bottom row of the pyramid and a list of strings allowed where each string is exactly three characters. The triple "XYZ" means: when block X is left-adjacent to block Y, block Z can sit on top of them. Given the bottom row, determine if you can build the pyramid all the way up to a single top block by repeatedly forming the next row from valid triples.

Each row has one fewer block than the row below it. A row of length n produces a row of length n - 1. You succeed when you reach a row of length 1. You fail if at any point there is no valid letter for some adjacent pair, and no alternative backtracking path leads to a solution.

Approach: recursive backtracking

The algorithm has two phases:

1. Preprocess the allowed triples. Build a dictionary that maps each (left, right) pair to the set of possible top blocks. For example, if the allowed list contains "BCG" and "BCE", then the pair (B, C) maps to {G, E}. This gives you O(1) lookup when building each row.

2. Build row by row with backtracking. Starting from the bottom row, try to construct the next row. For each adjacent pair at positions i and i + 1, look up the set of valid top blocks. Try placing each valid letter and recurse to fill the next position. Once the entire next row is built, recurse again to build the row above it. Continue until you reach a row of length 1, which means success. If you ever reach a pair with no valid options, backtrack.

The recursion has two levels: an outer recursion that moves from one complete row to the next, and an inner recursion that fills positions within a single row. The inner recursion is where the real backtracking happens, because each position may have multiple valid choices.

def pyramidTransition(bottom: str, allowed: list[str]) -> bool:
    from collections import defaultdict

    lookup = defaultdict(set)
    for triple in allowed:
        lookup[(triple[0], triple[1])].add(triple[2])

    def build_row(current_row, next_row, idx):
        if idx == len(current_row) - 1:
            if len(next_row) == 1:
                return True
            return build_row(next_row, "", 0)

        left = current_row[idx]
        right = current_row[idx + 1]
        for top in lookup.get((left, right), set()):
            if build_row(current_row, next_row + top, idx + 1):
                return True
        return False

    return build_row(bottom, "", 0)

Visual walkthrough

Let's trace through the algorithm with bottom = "BCD" and allowed = ["BCG", "CDE", "GEA", "FFF"]. This is a clean example where each pair has exactly one valid triple, so no backtracking is needed. The real power of the algorithm shows when pairs have multiple options and you need to try alternatives.

In this example, the path was linear: each pair mapped to exactly one letter, and that letter worked all the way up. In harder cases, a pair like (B, C) might map to {G, F}. You would try G first, and if the resulting pyramid fails, you would backtrack to this position and try F instead. The algorithm systematically explores all combinations until it finds one that works or exhausts all options.

Complexity analysis

The worst case happens when every adjacent pair has k valid options. Building one row requires choosing among k options at each of n - 1 positions, giving k^(n-1) combinations per row. There are n - 1 rows to build. In practice, most pairs have far fewer options, and failed branches are pruned quickly when a pair has no valid top blocks at all.

The space is O(n^2) because the recursion can go n - 1 levels deep (one per row), and at each level you hold a partial row of decreasing length.

Building blocks

1. Preprocessing constraints into a lookup map

This is the same pattern you see in many constraint problems: convert a flat list of rules into a fast-access structure before you start searching.

lookup = defaultdict(set)
for triple in allowed:
    lookup[(triple[0], triple[1])].add(triple[2])

The key (triple[0], triple[1]) is the adjacent pair. The value is the set of valid top blocks. Using a defaultdict(set) means missing pairs return an empty set, which naturally triggers backtracking with no special handling.

2. Row-by-row backtracking

The inner recursion fills one row left to right. At each position, it looks up valid top blocks for the current adjacent pair and tries each one. When the row is complete, it recurses to build the next row.

def build_row(current_row, next_row, idx):
    if idx == len(current_row) - 1:
        if len(next_row) == 1:
            return True
        return build_row(next_row, "", 0)

    left = current_row[idx]
    right = current_row[idx + 1]
    for top in lookup.get((left, right), set()):
        if build_row(current_row, next_row + top, idx + 1):
            return True
    return False

The base case len(next_row) == 1 means you have built a single top block and the pyramid is complete. The for top in ... loop is the branching point: each valid letter is a choice, and returning False from deeper calls triggers backtracking to try the next letter.

Edge cases

• Single character bottom: If bottom has length 1, the pyramid is already complete. Return True immediately.
• No valid triple for some pair: If any adjacent pair in the bottom row (or any intermediate row) has no entry in the lookup map, that branch fails. Backtracking tries alternative choices at earlier positions.
• All same character: If bottom = "AAA" and allowed = ["AAA"], the pair (A, A) maps to (A), so every row is a string of A's. The pyramid fills trivially.
• Multiple valid tops per pair: This is where backtracking matters. If (B, C) maps to (G, F, E), the algorithm tries each and recurses. The first one that leads to a complete pyramid wins.
• Large bottom row: With bottom up to length 7 (per the constraints), the worst case is manageable. But if every pair has many options, the exponential branching can still be expensive.

From understanding to recall

You see the pattern: preprocess constraints into a map, then backtrack through choices position by position. But can you write it from scratch in two minutes? The tricky part is getting the two-level recursion right, where the inner level fills one row and the outer level chains rows together. Under interview pressure, it is easy to mix up the indices or forget to check the base case when the next row has length 1.

Spaced repetition locks in both the preprocessing step and the two-level recursion structure. You practice writing the build_row function from memory at increasing intervals until the pattern is automatic. The lookup map, the position-by-position fill, the base case check... all of it becomes muscle memory.

CodeBricks breaks this problem into its core building blocks (constraint preprocessing, row-by-row backtracking) and drills each one independently. When a backtracking problem shows up that uses layered recursion, you do not need to re-derive the approach. You just write it.

Related posts

• N-Queens - Classic constraint-based backtracking where each row placement must satisfy column and diagonal constraints, similar to how each pyramid position must satisfy the allowed triple rules.
• Combination Sum - Recursive exploration with pruning, where the choose-explore-unchoose skeleton is the same backbone used in the pyramid row-filling logic.
• Word Search - Grid-based backtracking where each step checks validity against neighbors, paralleling how each pyramid position checks its pair against the allowed map.