Approach #1: State to State Transition [Wrong Answer]
Intuition and Algorithm
We model the states that blocks can be in. Each state is a binary number where the k
th bit is set if the k
th type of block is a possibility. Then, we create a transition map T[state1][state2] > state
that takes a left state and a right state and outputs all possible parent states.
At the end, applying these transitions is straightforward. However, this approach is not correct, because the transitions are not independent. If for example we have states in a row A, {B or C}, A
, and allowed triples (A, B, D)
, (C, A, D)
, then regardless of the choice of {B or C}
we cannot create the next row of the pyramid.
Complexity Analysis

Time Complexity: , where is the length of
bottom
, is the length ofallowed
, and is the size of the alphabet. 
Space Complexity: in additional space complexity.
Approach #2: DepthFirst Search [Accepted]
Intuition
We exhaustively try every combination of blocks.
Algorithm
We can work in either strings or integers, but we need to create a transition map T
from the list of allowed triples. This map T[x][y] = {set of z}
will be all possible parent blocks for a left child of x
and a right child of y
. When we work in strings, we use Set
, and when we work in integers, we will use the set bits of the result integer.
Afterwards, to solve
a row, we generate every possible combination of the next row and solve them. If any of those new rows are solvable, we return True
, otherwise False
.
We can also cache intermediate results, saving us time. This is illustrated in the comments for Python. For Java, all caching is done with lines of code that mention the integer R
.
Complexity Analysis

Time Complexity: , where is the length of
bottom
, and is the size of the alphabet, and assuming we cache intermediate results. We might try every sequence of letters for each row. [The total complexity is because is a geometric series equal to .] Without intermediate caching, this would be . 
Space Complexity: additional space complexity.
Analysis written by: @awice.