Problem Description

The Pyramid Transition Matrix problem asks you to determine if you can build a pyramid from a given bottom row of blocks, using a list of allowed triples that specify which block can be placed atop every pair of blocks.

Specifically, given a string bottom representing the bottom row (where each character is a block), and a list of strings allowed (each a length-3 string like "ABC", meaning "if A and B are adjacent, you can put C above them"), determine if you can build the pyramid all the way up to a single block at the top.

• You can only place a block C atop two adjacent blocks A and B if "ABC" is in allowed.
• Each level of the pyramid has one fewer block than the level below.
• You must use only the allowed triples—no other combinations are permitted.
• The goal is to return true if at least one way exists to build the pyramid to the top, else false.

Thought Process

At first glance, the problem seems to involve checking all possible ways to stack blocks, given the constraints. For each level, every pair of adjacent blocks determines which blocks could possibly go above them. This suggests a recursive or backtracking approach: try all possible combinations, and see if any lead to a completed pyramid.

A brute-force solution would try every possible combination for every level, but this can quickly become infeasible as the pyramid grows taller and the number of allowed triples increases. Therefore, we look for ways to optimize:

• Mapping pairs to possible tops: Rather than scanning the allowed list every time, we can preprocess it into a mapping from each pair (A, B) to all possible C.
• Memoization: Since many subproblems repeat (the same sub-row may appear in different recursive branches), we can cache results to avoid redundant work.
• Recursion/backtracking: For each level, try all possible combinations for the next level up, using the mapping, and recurse.

Solution Approach

Let's break down the solution into clear steps:

1. Build a mapping:
   • For each allowed triple "ABC", store that for the pair (A, B), C is a possible block above.
   • This can be implemented as a dictionary mapping (A, B) to a set of possible C.
2. Recursive function:
   • Given the current row, generate all possible next rows by looking up every adjacent pair and trying all their possible "top" blocks.
   • For each possible next row, recursively try to build the pyramid from it.
   • If we ever reach a row of length 1, we've successfully built the pyramid.
3. Backtracking:
   • Since multiple choices may exist for each pair, we must try all combinations, backtracking if a path leads to a dead end.
4. Memoization:
   • Use a cache to store the result for each row string. If we've already determined whether a given row can lead to a pyramid, reuse that result.

This approach ensures we efficiently explore all valid paths, while avoiding redundant computation.

Example Walkthrough

Let's use the following example:

• bottom = "BCD"
• allowed = ["BCC", "CDE", "CEA", "FFF"]

Step-by-step:

1. Start with BCD. The pairs are ["B", "C"] and ["C", "D"].
2. For ("B", "C"), allowed top is 'C' (from "BCC").
3. For ("C", "D"), allowed top is 'E' (from "CDE").
4. So, possible next row is "CE".
5. Now, for "CE", the only pair is ("C", "E").
6. For ("C", "E"), allowed top is 'A' (from "CEA").
7. So, the next row is "A" (length 1).
8. We've reached the top; thus, building the pyramid is possible, so we return true.

If at any point no allowed top exists for a pair, or no next row can be formed, that path fails and we backtrack.

Time and Space Complexity

Brute-force approach:

• For each level, the number of possible rows can grow exponentially, since for each pair there may be multiple choices.
• If the bottom has length n, and each pair allows up to k possible tops, the total number of possible rows at a level is up to k^{n-1}.
• The total number of recursive calls is thus roughly O(k^{n^2}).

Optimized approach (with memoization):

• By caching results for each row, we avoid recomputation. Since there are at most O(k^n) unique rows of length n, and each is computed once, the total number of subproblems is much smaller.
• Each subproblem processes up to k^{n-1} possible next rows, but memoization keeps the total manageable for small n.
• Time complexity: In the worst case, still exponential in the length of the bottom row, but much faster than brute-force.
• Space complexity: The cache may hold up to O(k^n) entries, and the mapping uses O(|allowed|) space.

Summary

The Pyramid Transition Matrix problem is a classic example of recursive backtracking with memoization. By mapping pairs to possible tops, and caching subproblem results, we efficiently explore all valid ways to build the pyramid from the bottom up. The key insight is to treat the problem as constructing all possible next rows for each level, and to use memoization to avoid redundant work. This makes the solution both elegant and practical for reasonable input sizes.

Code Implementation

from collections import defaultdict
from functools import lru_cache

class Solution:
    def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
        mapping = defaultdict(set)
        for triplet in allowed:
            a, b, c = triplet
            mapping[(a, b)].add(c)
        
        @lru_cache(None)
        def can_build(row):
            if len(row) == 1:
                return True
            # For each pair, get possible tops
            candidates = []
            for i in range(len(row) - 1):
                pair = (row[i], row[i+1])
                if pair not in mapping:
                    return False
                candidates.append(mapping[pair])
            # Try all combinations for next row
            def dfs(idx, path):
                if idx == len(candidates):
                    return can_build(''.join(path))
                for c in candidates[idx]:
                    if dfs(idx + 1, path + [c]):
                        return True
                return False
            return dfs(0, [])
        
        return can_build(bottom)
      

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    unordered_map<string, unordered_set<char>> mapping;
    unordered_map<string, bool> memo;

    bool canBuild(const string& row) {
        if (row.size() == 1) return true;
        if (memo.count(row)) return memo[row];
        vector<unordered_set<char>> candidates;
        for (int i = 0; i < row.size() - 1; ++i) {
            string pair = row.substr(i, 2);
            if (!mapping.count(pair)) return memo[row] = false;
            candidates.push_back(mapping[pair]);
        }
        return memo[row] = dfs(candidates, 0, "", row);
    }

    bool dfs(const vector<unordered_set<char>>& candidates, int idx, string path, const string& orig) {
        if (idx == candidates.size()) {
            return canBuild(path);
        }
        for (char c : candidates[idx]) {
            if (dfs(candidates, idx + 1, path + c, orig)) return true;
        }
        return false;
    }

    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (const string& triplet : allowed) {
            string key = triplet.substr(0, 2);
            mapping[key].insert(triplet[2]);
        }
        return canBuild(bottom);
    }
};
      

import java.util.*;

class Solution {
    Map<String, Set<Character>> mapping = new HashMap<>();
    Map<String, Boolean> memo = new HashMap<>();

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        for (String triplet : allowed) {
            String key = triplet.substring(0, 2);
            char val = triplet.charAt(2);
            mapping.computeIfAbsent(key, k -> new HashSet<>()).add(val);
        }
        return canBuild(bottom);
    }

    private boolean canBuild(String row) {
        if (row.length() == 1) return true;
        if (memo.containsKey(row)) return memo.get(row);
        List<Set<Character>> candidates = new ArrayList<>();
        for (int i = 0; i < row.length() - 1; ++i) {
            String pair = row.substring(i, i + 2);
            if (!mapping.containsKey(pair)) {
                memo.put(row, false);
                return false;
            }
            candidates.add(mapping.get(pair));
        }
        boolean result = dfs(candidates, 0, new StringBuilder());
        memo.put(row, result);
        return result;
    }

    private boolean dfs(List<Set<Character>> candidates, int idx, StringBuilder path) {
        if (idx == candidates.size()) {
            return canBuild(path.toString());
        }
        for (char c : candidates.get(idx)) {
            path.append(c);
            if (dfs(candidates, idx + 1, path)) return true;
            path.deleteCharAt(path.length() - 1);
        }
        return false;
    }
}
      

/**
 * @param {string} bottom
 * @param {string[]} allowed
 * @return {boolean}
 */
var pyramidTransition = function(bottom, allowed) {
    const mapping = {};
    for (const triplet of allowed) {
        const key = triplet.slice(0, 2);
        if (!mapping[key]) mapping[key] = new Set();
        mapping[key].add(triplet[2]);
    }
    const memo = new Map();

    function canBuild(row) {
        if (row.length === 1) return true;
        if (memo.has(row)) return memo.get(row);
        const candidates = [];
        for (let i = 0; i < row.length - 1; ++i) {
            const pair = row[i] + row[i+1];
            if (!mapping[pair]) {
                memo.set(row, false);
                return false;
            }
            candidates.push(Array.from(mapping[pair]));
        }
        function dfs(idx, path) {
            if (idx === candidates.length) {
                return canBuild(path.join(''));
            }
            for (const c of candidates[idx]) {
                path.push(c);
                if (dfs(idx + 1, path)) return true;
                path.pop();
            }
            return false;
        }
        const res = dfs(0, []);
        memo.set(row, res);
        return res;
    }
    return canBuild(bottom);
};