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.
This approach involves using dynamic programming to break the problem into smaller overlapping subproblems. Our goal is to use past solutions to solve larger problems more efficiently.
In Python, the dynamic programming approach involves defining a base case and using a list to store intermediate results. This helps to avoid repeated calculations.
Time Complexity: O(n^2)
Space Complexity: O(n)
The greedy approach makes locally optimal choices at each step with the hope of finding a global optimum. This can be effective in problems where a correct local solution also leads to a correct global solution.
In JavaScript, implementing a greedy algorithm involves iterating over the data while making optimal choices based on current conditions. This can reduce complexity significantly in certain scenarios.
JavaScript
C#
Time Complexity: O(n log n)
Space Complexity: O(1)
We define a hash table d to store the allowed triangular patterns, where the key is a pair of two characters and the value is the corresponding list of characters, indicating that the two characters can form a triangular pattern with each item in the value list being the top of the triangle.
Starting from the bottom layer, for every two adjacent characters in each layer, if they can form a triangular pattern, we add the top character of the triangular pattern to the character list at the corresponding position in the next layer, then recursively process the next layer.
When the recursion reaches a single character, it means we have successfully built to the top of the pyramid, and we return true. If at some layer, two adjacent characters cannot form a triangular pattern, we return false.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) |
| Greedy Algorithm | Time Complexity: O(n log n) |
| 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 |
Pyramid Transition Matrix | Detailed Intuition | Beginner Friendly | Dry Runs | Leetcode 756 | MIK • codestorywithMIK • 8,499 views views
Watch 9 more video solutions →Practice Pyramid Transition Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor