Watch 10 video solutions for Pyramid Transition Matrix, a medium level problem involving Bit Manipulation, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 8,499 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
"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:
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:
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 <= 60 <= allowed.length <= 216allowed[i].length == 3{'A', 'B', 'C', 'D', 'E', 'F'}.allowed are unique.Problem Overview: You are given a bottom row of blocks and a list of allowed triples ABC, meaning if blocks A and B are adjacent, block C can be placed above them. The task is to determine whether you can build the pyramid all the way to a single block at the top.
Approach 1: Dynamic Programming / DFS State Building (Time: O(2^n), Space: O(2^n))
Preprocess the allowed triples into a mapping where each pair (A, B) points to all possible top blocks. Starting from the bottom string, recursively construct the next level by checking each adjacent pair and generating all valid characters that can sit above it. This naturally forms a search tree where each level shortens the row by one. Memoization (DP on strings) avoids recomputing states that were already proven impossible, which drastically prunes the search space. The recursion is essentially a depth-first search over possible rows while caching failed configurations.
Approach 2: Greedy Expansion with Bitmask Optimization (Time: O(2^n), Space: O(26^2))
Instead of storing lists of characters for each pair, encode allowed transitions using bitmasks. Each pair (A,B) maps to a 26-bit mask representing all valid top blocks. While generating the next row, use bit operations to quickly enumerate candidates. This approach aggressively prunes invalid branches early and reduces memory overhead compared to storing lists. It still explores combinations using recursion or stack-based search similar to breadth-first search, but bit manipulation speeds up candidate checks.
Recommended for interviews: The DFS with memoization approach is the most common solution. It clearly models the pyramid-building process and demonstrates understanding of recursion, state pruning, and caching. Adding a bitmask optimization shows stronger mastery of bit manipulation and performance tuning. Interviewers mainly look for the recursive state generation plus memoization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization (DP on Rows) | O(2^n) | O(2^n) | General case; easiest to implement and common in interviews |
| Bitmask Optimized DFS | O(2^n) | O(26^2) | When transitions are many and faster candidate checks are needed |
| Greedy Branch Pruning | O(2^n) | O(n) | Useful when early invalid pairs eliminate large parts of the search tree |