Skip to main content
Talentd

Pyramid Transition Matrix - Solution & Explanation

MediumBit ManipulationDepth-First SearchBreadth-First Search12 min readAsked at: Amazon, Airbnb, Google
Practice this problem

Problem Statement

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:

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 <= 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.

Approach Overview

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 1: Dynamic Programming Approach

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.

Code

PythonC++Java

Python

C++

Java

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Greedy Algorithm

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n log n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Memoization

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2)
Space Complexity: O(n)

Greedy Algorithm

Time Complexity: O(n log n)
Space Complexity: O(1)

Memoization—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 DFSO(2^n)O(26^2)When transitions are many and faster candidate checks are needed
Greedy Branch PruningO(2^n)O(n)Useful when early invalid pairs eliminate large parts of the search tree

Video Solution

Pyramid Transition Matrix | Detailed Intuition | Beginner Friendly | Dry Runs | Leetcode 756 | MIK • codestorywithMIK • 8,993 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Pyramid Transition Matrix easy or hard?
Pyramid Transition Matrix is rated Medium difficulty. The challenge is modeling the pyramid-building process and managing the exponential branching efficiently using memoization or pruning techniques.
Pyramid Transition Matrix Python/Java solution
Typical Python or Java solutions preprocess the allowed triples into a map from pair → list of possible blocks. A recursive DFS builds the next row character by character while caching failed rows. Memoization ensures repeated states are skipped, keeping the solution efficient within constraints.
How to solve Pyramid Transition Matrix in O(n)?
An O(n) solution does not exist for the general case because the algorithm must explore combinations of possible rows. The closest practical optimization uses bitmasks to represent valid transitions and prune branches quickly. This reduces constant factors but the theoretical worst case remains exponential.
What is the best approach for Pyramid Transition Matrix?
The most reliable approach is DFS with memoization. Build a mapping from each pair of characters to all possible blocks that can sit above them, then recursively construct the next row. Memoizing previously failed rows avoids recomputation and significantly reduces the search space. The worst‑case time complexity remains exponential but works efficiently for the given constraints.
Is Pyramid Transition Matrix asked at Google/Amazon/Meta?
Pyramid Transition Matrix appears in interview preparation sets for companies like Google, Amazon, and Meta because it tests recursion, state pruning, and graph-style search. The problem evaluates how well you model combinational states and apply DFS with memoization.
What data structure is used in Pyramid Transition Matrix?
The core structure is a hash map that maps each pair of characters to possible top characters. During the search, recursion or a stack performs DFS over possible rows. Some optimized solutions also use bitmasks to store transitions compactly.
What is the time complexity of Pyramid Transition Matrix?
The worst‑case time complexity is O(2^n) because each level of the pyramid can branch into multiple candidate rows. With memoization, many invalid configurations are cached and skipped, which improves practical performance. Space complexity is also O(2^n) due to recursion depth and stored states.

Ready to solve this problem?

Practice Pyramid Transition Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary