# Pyramid Transition Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/pyramid-transition-matrix)
Canonical: https://scaleengineer.com/dsa/problems/pyramid-transition-matrix
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb)
---
## Problem
You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains **one less block** than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific **triangular patterns** that are allowed. A triangular pattern consists of a **single block** stacked on top of **two blocks**. The patterns are given as a list of three-letter strings `allowed`, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

* For example, `"ABC"` represents a triangular pattern with a `'C'` block stacked on top of an `'A'` (left) and `'B'` (right) block. Note that this is different from `"BAC"` where `'B'` is on the left bottom and `'A'` is on the right bottom.

You start with a bottom row of blocks `bottom`, given as a single string, that you **must** use as the base of the pyramid.

Given `bottom` and `allowed`, return `true` _if you can build the pyramid all the way to the top such that **every triangular pattern** in the pyramid is in_ `allowed`_, or_ `false` _otherwise_.

**Example 1:**

![](https://assets.glich.co/dsa/pyramid-transition-matrix/image0.jpg) 

**Input:** bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
**Output:** true
**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.
There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.

**Example 2:**

![](https://assets.glich.co/dsa/pyramid-transition-matrix/image1.jpg) 

**Input:** bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
**Output:** false
**Explanation:** The allowed triangular patterns are shown on the right.
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

**Constraints:**

* `2 <= bottom.length <= 6`
* `0 <= allowed.length <= 216`
* `allowed[i].length == 3`
* The letters in all input strings are from the set `{'A', 'B', 'C', 'D', 'E', 'F'}`.
* All the values of `allowed` are **unique**.

# Approaches
## Brute-Force Backtracking
This approach uses a straightforward recursive depth-first search (DFS) to explore all possible ways the pyramid can be built. Starting from the given `bottom` row, it tries to construct the next level up. For each valid next level, it recursively calls itself to build the subsequent level, continuing until it either reaches the single-block top (a success) or exhausts all possibilities for a given level (a failure).
**Time:** O(C^(N^2)) · **Space:** O(N^2 + K)
**Pros:** Conceptually simple and follows the problem description directly.
**Cons:** Extremely inefficient due to massive re-computation of results for the same intermediate rows.; Will almost certainly result in a 'Time Limit Exceeded' error for non-trivial inputs.
### Explanation
The core of this method is a recursive function that takes the current row of the pyramid as input and returns whether a pyramid can be completed from it. The function's logic is as follows:

1.  If the current row has only one block, we've reached the peak, so we return `true`.
2.  Otherwise, we need to generate all possible valid rows that can be placed on top of the current one. This is itself a recursive sub-problem: to build the next row of length `k-1` from a current row of length `k`, we determine the possible characters for each position `i` (from 0 to `k-2`) in the next row based on the blocks at `i` and `i+1` in the current row.
3.  We iterate through every completely formed `nextRow`.
4.  For each `nextRow`, we make a recursive call to see if we can complete the pyramid from there.
5.  If any recursive call returns `true`, we have found a valid construction, and we return `true`.
6.  If we try all possible next rows and none of them lead to a solution, we conclude that it's impossible to build from the `currentRow` and return `false`.

This process naturally explores the entire search space of possible pyramid constructions. However, it's highly inefficient because it may solve the same subproblem (i.e., determine if a pyramid can be built from a specific intermediate row like `"CE"`) multiple times if that row can be formed from different lower levels.

```java
import java.util.*;

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> transitions = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            transitions.computeIfAbsent(key, k -> new ArrayList<>()).add(s.charAt(2));
        }
        return solve(bottom, transitions);
    }

    private boolean solve(String currentRow, Map<String, List<Character>> transitions) {
        if (currentRow.length() == 1) {
            return true;
        }

        List<String> nextRows = new ArrayList<>();
        generateNextRows(currentRow, 0, new StringBuilder(), nextRows, transitions);

        for (String nextRow : nextRows) {
            if (solve(nextRow, transitions)) {
                return true;
            }
        }

        return false;
    }

    private void generateNextRows(String currentRow, int index, StringBuilder nextRowBuilder, List<String> nextRows, Map<String, List<Character>> transitions) {
        if (index == currentRow.length() - 1) {
            nextRows.add(nextRowBuilder.toString());
            return;
        }

        String key = currentRow.substring(index, index + 2);
        if (!transitions.containsKey(key)) {
            return; // This path is a dead end
        }

        for (char c : transitions.get(key)) {
            nextRowBuilder.append(c);
            generateNextRows(currentRow, index + 1, nextRowBuilder, nextRows, transitions);
            nextRowBuilder.deleteCharAt(nextRowBuilder.length() - 1); // Backtrack
        }
    }
}
```
### Algorithm
- Define a main recursive function, `solve(currentRow)`, that attempts to build the pyramid from `currentRow` upwards.
- **Base Case:** If `currentRow` has a length of 1, it means we have successfully reached the top of the pyramid. Return `true`.
- **Recursive Step:**
  - Generate all possible next rows that can be built on top of `currentRow`. This is done using another helper recursive function, let's call it `generateNextRows`.
  - `generateNextRows` works by iterating through `currentRow` from left to right. For each pair of adjacent blocks `(C1, C2)`, it finds all possible top blocks `T` from the `allowed` list.
  - It explores all combinations of these top blocks to form complete next rows.
  - For each `nextRow` generated, call `solve(nextRow)`.
  - If any of these recursive calls return `true`, it signifies that a valid pyramid can be completed. Propagate `true` up the call stack.
- If all possible next rows are explored and none lead to a solution, `solve(currentRow)` returns `false`.
- To make finding transitions faster, the `allowed` list is first preprocessed into a `Map<String, List<Character>>`, where the key is the two-character string of bottom blocks and the value is a list of possible top blocks.

## Backtracking with Memoization
This approach significantly optimizes the brute-force backtracking by using memoization, a technique common in dynamic programming. The key observation is that the same intermediate row configuration can be reached from multiple different lower rows. Instead of re-computing whether a pyramid can be built from this intermediate row every time it's encountered, we can store the result the first time we compute it and look it up for subsequent encounters.
**Time:** O(sum(|S_k| * C^(k-1))) · **Space:** O(S * N + N^2)
**Pros:** Drastically more efficient than the brute-force approach by avoiding re-computation.; Feasible and passes within time limits for the given constraints.; Represents a classic application of dynamic programming (via memoization) to a search problem.
**Cons:** The worst-case time complexity is still exponential, although it performs well given the problem's constraints.; Space complexity can be significant if the number of reachable intermediate row configurations is large.
### Explanation
We enhance the recursive solution by adding a cache (memoization table) to keep track of rows from which it's impossible to build a pyramid. This avoids redundant computations.

The algorithm is a top-down dynamic programming approach:

1.  We preprocess the `allowed` list into a map for quick lookups, just like in the brute-force approach.
2.  We use a `Set<String>` to store the rows that we have already processed and confirmed cannot lead to a valid pyramid top.
3.  The main recursive function `solve(currentRow)` first checks its base cases: if the row is of length 1 (success) or if the row is already in our failure set (cached failure).
4.  If it's a new row, we proceed to find a valid path upwards. We do this with a helper function that constructs the next row piece by piece. This helper tries every possible character for the first position of the next row, then for each of those, every possible character for the second, and so on.
5.  Once a complete `nextRow` is formed, we recursively call `solve` on it.
6.  If any of these recursive calls eventually return `true`, we have found a solution.
7.  If, after trying all possible valid next rows, none lead to a solution, we add the `currentRow` to our failure set and return `false`.

This way, any given row configuration is fully explored only once. Subsequent calls with the same row will return the cached result instantly.

```java
import java.util.*;

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> transitions = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            transitions.computeIfAbsent(key, k -> new ArrayList<>()).add(s.charAt(2));
        }
        // Memoization set for rows that cannot form a pyramid
        Set<String> memo = new HashSet<>();
        return solve(bottom, transitions, memo);
    }

    private boolean solve(String currentRow, Map<String, List<Character>> transitions, Set<String> memo) {
        if (currentRow.length() == 1) {
            return true;
        }
        if (memo.contains(currentRow)) {
            return false;
        }

        boolean canMakePyramid = findPathForNextRow(currentRow, 0, new StringBuilder(), transitions, memo);
        
        if (!canMakePyramid) {
            memo.add(currentRow);
        }
        
        return canMakePyramid;
    }

    private boolean findPathForNextRow(String currentRow, int index, StringBuilder nextRowBuilder, Map<String, List<Character>> transitions, Set<String> memo) {
        if (index == currentRow.length() - 1) {
            // A complete next row has been formed, now solve for it
            return solve(nextRowBuilder.toString(), transitions, memo);
        }

        String key = currentRow.substring(index, index + 2);
        if (!transitions.containsKey(key)) {
            return false; // No transition possible, this path is invalid
        }

        for (char c : transitions.get(key)) {
            nextRowBuilder.append(c);
            if (findPathForNextRow(currentRow, index + 1, nextRowBuilder, transitions, memo)) {
                return true; // A valid pyramid was found down this path
            }
            nextRowBuilder.deleteCharAt(nextRowBuilder.length() - 1); // Backtrack
        }

        return false; // No character choice at this index led to a solution
    }
}
```
### Algorithm
- **Preprocessing:** Convert the `allowed` list into a `Map<String, List<Character>>` for efficient lookups. The key is the 2-character base, and the value is a list of possible top blocks.
- **Memoization:** Use a `Set<String>` or `Map<String, Boolean>` to store the results for subproblems. A subproblem is identified by the string of a given row. We can store rows that are determined to be 'unsolvable'.
- **Recursive Solver:** Create a recursive function, `solve(currentRow, memo)`, that checks if a pyramid can be built.
- **Base Cases:**
  - If `currentRow.length() == 1`, return `true`.
  - If `currentRow` is in the memoization table (meaning we've already proved it's unsolvable), return `false`.
- **Recursive Step:**
  - Use a helper function to generate and test possible next rows one character at a time. This helper function, say `findPath(currentRow, nextRowBuilder, index, memo)`, will try to build a valid `nextRow`.
  - For each position in the `nextRow`, iterate through all possible characters. Recursively call `findPath` for the next position.
  - When a full `nextRow` is constructed, call `solve(nextRow, memo)`.
  - If `solve` returns `true`, a path is found, so propagate `true` all the way up.
- **Memoize Failures:** If the `findPath` function explores all possibilities for `currentRow` and fails to find a solution, add `currentRow` to the memoization set before returning `false`.

# Solutions
### Java

```java
class Solution {
private
  int[][] f = new int[7][7];
private
  Map<String, Boolean> dp = new HashMap<>();
public
  boolean pyramidTransition(String bottom, List<String> allowed) {
    for (String s : allowed) {
      int a = s.charAt(0) - 'A', b = s.charAt(1) - 'A';
      f[a][b] |= 1 << (s.charAt(2) - 'A');
    }
    return dfs(bottom, new StringBuilder());
  }
  boolean dfs(String s, StringBuilder t) {
    if (s.length() == 1) {
      return true;
    }
    if (t.length() + 1 == s.length()) {
      return dfs(t.toString(), new StringBuilder());
    }
    String k = s + "." + t.toString();
    if (dp.containsKey(k)) {
      return dp.get(k);
    }
    int a = s.charAt(t.length()) - 'A', b = s.charAt(t.length() + 1) - 'A';
    int cs = f[a][b];
    for (int i = 0; i < 7; ++i) {
      if (((cs >> i) & 1) == 1) {
        t.append((char)('A' + i));
        if (dfs(s, t)) {
          dp.put(k, true);
          return true;
        }
        t.deleteCharAt(t.length() - 1);
      }
    }
    dp.put(k, false);
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int f[7][7];
  unordered_map<string, bool> dp;
  bool pyramidTransition(string bottom, vector<string> &allowed) {
    memset(f, 0, sizeof f);
    for (auto &s : allowed) {
      int a = s[0] - 'A', b = s[1] - 'A';
      f[a][b] |= 1 << (s[2] - 'A');
    }
    return dfs(bottom, "");
  }
  bool dfs(string &s, string t) {
    if (s.size() == 1) {
      return true;
    }
    if (t.size() + 1 == s.size()) {
      return dfs(t, "");
    }
    string k = s + "." + t;
    if (dp.count(k)) {
      return dp[k];
    }
    int a = s[t.size()] - 'A', b = s[t.size() + 1] - 'A';
    int cs = f[a][b];
    for (int i = 0; i < 7; ++i) {
      if ((cs >> i) & 1) {
        if (dfs(s, t + (char)(i + 'A'))) {
          dp[k] = true;
          return true;
        }
      }
    }
    dp[k] = false;
    return false;
  }
};

```

### Python

```python
class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool: @ cache def dfs(s): if len(s) == 1: return True t = [] for a, b in pairwise(s): cs = d[a, b] if not cs: return False t . append(cs) return any(dfs('' . join(nxt)) for nxt in product(* t)) d = defaultdict(list) for a, b, c in allowed: d[a, b]. append(c) return dfs(bottom)

```