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.Pyramid Transition Matrix asks whether a pyramid can be built from a given bottom row using a set of allowed triples. Each triple ABC means that if blocks A and B are adjacent, block C can be placed above them. The key idea is to treat the problem as a search over possible rows while constructing the pyramid level by level.
A common approach is to preprocess the allowed triples into a map where each pair (A, B) points to all possible characters that can appear above them. Then use Depth-First Search (DFS) with backtracking to generate the next row from the current row. If multiple characters are possible for a pair, recursively explore each option. When a row of length 1 is reached, a valid pyramid has been formed.
To improve efficiency, pruning and memoization can avoid recomputing invalid intermediate rows. The branching factor depends on the number of valid transitions, making the search exponential in the worst case.
Time Complexity: roughly O(k^n) in the worst case due to branching during DFS.
Space Complexity: O(n) recursion depth plus storage for transition mappings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Backtracking | O(k^n) in worst case due to branching possibilities | O(n) recursion stack plus transition map |
| DFS with Memoization | Reduced by caching invalid rows, but still exponential in worst case | O(n + states cached) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at large tech companies. It tests recursion, backtracking, and the ability to model transitions between states efficiently.
A hash map or dictionary works best to map character pairs to possible top characters. This allows constant-time lookup when generating the next level of the pyramid during DFS.
The common approach is DFS with backtracking. First map every pair of characters to the list of possible blocks that can be placed above them, then recursively build the next row. Pruning invalid paths early helps reduce unnecessary exploration.
Yes, BFS can be used by generating all possible rows level by level. However, DFS with backtracking is usually preferred because it uses less memory and allows earlier pruning when a path becomes invalid.