Problem Statement in English

You’re given a string bottom, which represents the bottom row of a pyramid.

Each character in bottom is a block of a certain type. You’re also given a list of allowed triples allowed, where each triple allowed[i] = "A B C" means that if you have two adjacent blocks of type A and B, you can place a block of type C on top of them.

You want to build the pyramid from the bottom up, using the allowed triples to place blocks on top of each other.

Return true if you can build the pyramid all the way to the top (with a single block at the top), or false otherwise.

Approach

Hopefully you realize that you just have to try all possible combinations of blocks that can be placed on top of the current row, and see if any of those combinations can lead to a successful pyramid construction.

The question is more about…how do you implement this?

A subtle clue lies in the question title: blahblah Matrix.

We model the depth first search using a matrix, even though the shape of the pyramid is triangular. Yes we do end up wasting some space, but it makes the implementation way easier.

Every cell of a row represents a block, and each row has one less cell than the row below it.

Each cell is a child of the two cells directly below it. So formally matrix[row][col] is a child of matrix[row + 1][col] and matrix[row + 1][col + 1].

Now we just need a matrix to brute force, and a way to look up what blocks can be placed on top of two adjacent blocks.

So we create a dictionary that maps pairs of blocks to the list of blocks that can be placed on top of them.

The dfs itself is a function of each cell in the matrix - dfs(row, col).

A quick edge case is when row == 0, meaning we’ve successfully placed the top block, so we return True. Another edge case is when col > row, meaning we’ve placed all blocks in the current row, so we move to the next row up and start at column 0.

And that’s about it!

Solution in Python


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        N = len(bottom)
        db = defaultdict(list)

        for s in allowed:
            a, b, c = s
            db[a + b].append(c)

        matrix = [["" for _ in range(N)] for _ in range(N)]
        for i in range(N):
            matrix[-1][i] = bottom[i]
        
        def dfs(row, col):
            nonlocal matrix
            parent = "".join(matrix[row + 1][col:col + 2])

            for option in db[parent]:
                matrix[row][col] = option

                if row == 0:
                    return True

                # each row will have `rowIndex + 1` columns
                if col + 1 > row:
                    if dfs(row - 1, 0):
                        return True
                else:
                    if dfs(row, col + 1):
                        return True
            return False

        return dfs(N - 2,0)

Complexity

  • Time: $O(n^2)$
    Since we are exploring all possible configurations of the pyramid, and there are at most n rows with n columns each, the time complexity is $O(n^2)$.

  • Space: $O(n^2)$
    Since we are using a matrix to represent the pyramid, the space complexity is also $O(n^2)$.

Mistakes I Made

I cached the results of DFS cells like a mechanical fool, but that doesn’t work because the state of the matrix keeps changing as we backtrack. Even for any given (row, col).

I also needed a hint to realise that the dfs could be modelled as a matrix.

And we are done.