Pyramid Transition Matrix

Pyramid Transition Matrix

What is this problem about?

The Pyramid Transition Matrix problem asks whether a given base string can build upward into a pyramid where each level is one character shorter and each character is determined by allowed triples (left, right → up). You need to determine if there exists at least one way to build the entire pyramid up to a single apex. This medium coding problem uses DFS/BFS with memoization. The BFS, DFS, and bit manipulation interview pattern is demonstrated.

Why is this asked in interviews?

Airbnb and Google ask this to test recursive state-space search with memoization. The pyramid building structure is naturally recursive — each level depends entirely on the previous — making DFS with state caching the right approach.

Algorithmic pattern used

DFS with memoization on (current level, next level). For each pair of adjacent characters at the current level, look up all valid characters that can sit above them. Recursively build the next level trying all combinations. Memoize on the (current_row, next_row_in_progress) state to avoid recomputation.

Example explanation

allowed=["XYD","YZE","DEA","FFF"]. Base="XYZF". Build next level: from XY→D, YZ→E, ZF→? (no rule) → no valid pyramid. Try other combinations... If all fail, return false.

Base="XY": from XY→D. Single character D. Check: pyramid is "XY" → "D". Return true.

Common mistakes candidates make

• Not memoizing the state (causes exponential time).
• Using wrong state: memoize on (current_level_str, next_level_in_progress) pair.
• Not exploring all valid next-level characters for each position.
• Terminating too early without exploring all paths.

Interview preparation tip

Pyramid Transition Matrix is a string DFS with layer-by-layer construction. The memoization key combines the current level string and the partial next level built so far. Practice similar "layer-by-layer string construction" problems. Bit manipulation can compress multiple characters into an integer bitmask for faster state comparison — useful when the character set is small.