We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pyramid Transition Matrix

Number: 757

Difficulty: Medium

Paid? No

Companies: Airbnb, Google

Problem Description

Given a bottom row of colored blocks (represented as a string) and a list of allowed triangular patterns (each represented as a three-letter string), determine if you can build a pyramid all the way to the top. In each step, a block is placed on top of two adjacent blocks from the current row, and this triple must match one of the allowed patterns.

Key Insights

  • Use DFS/backtracking to simulate building the pyramid row by row.
  • Preprocess allowed patterns into a dictionary (or map) mapping pairs of base blocks to a list of possible blocks that can be placed above.
  • Recursively construct each level: for every adjacent pair in the current row, try all allowed blocks.
  • Backtracking is essential since multiple choices may lead to dead ends.

Space and Time Complexity

Time Complexity: O(3^(n)) in the worst case where n is the length of the current row, due to exploring every valid combination. Space Complexity: O(n) for recursion stack and storing current pyramid level.

Solution

We use a DFS/backtracking approach. First, convert the list of allowed patterns into a dictionary mapping each valid pair (two-letter string) to possible third-block candidates. Then, recursively build the next row from the current row by processing all adjacent pairs. If at any point a pair does not have a mapping from the allowed patterns, that path is abandoned. The process stops when the top row (a single block) is reached, signaling a valid pyramid. The main challenge is to correctly build all possibilities for the next row and backtrack when necessary.

Code Solutions

# Python solution
class Solution:
    def pyramidTransition(self, bottom: str, allowed: list) -> bool:
        # Build a mapping from base pair to a list of blocks that can be placed above
        allowed_map = {}
        for pattern in allowed:
            key = pattern[:2]
            if key not in allowed_map:
                allowed_map[key] = []
            allowed_map[key].append(pattern[2])
        
        # Recursive function to determine if a pyramid can be built from the current row
        def dfs(current_row: str) -> bool:
            # If only one block remains, the pyramid is successfully built
            if len(current_row) == 1:
                return True
            # Helper function to build the next row by trying all allowed blocks for adjacent pairs
            def build_next(row: str, next_row: str, index: int) -> bool:
                # If we have processed all pairs in the current row
                if index == len(row) - 1:
                    return dfs(next_row)
                # Get the current pair of adjacent blocks
                pair = row[index:index+2]
                if pair in allowed_map:
                    # Try every possible block for the given pair
                    for block in allowed_map[pair]:
                        if build_next(row, next_row + block, index + 1):
                            return True
                # No valid block found for this pair, backtrack
                return False
            
            return build_next(current_row, "", 0)
        
        return dfs(bottom)
← Back to All Questions