Domain 2MediumMEDIUM

Pyramid Transition Matrix

Determine if a pyramid can be built from bottom to top using allowed triples. Use DFS with memoization on row configurations and an adjacency map for O(1) transition lookups.

Domain: medium•Updated: 2026-08-31
#DFS#Backtracking#Memoization#Hash Map

Problem Breakdown

We are tasked with determining the feasibility of constructing a pyramid structure starting from a given bottom row string. The rules for stacking blocks are defined by an allowed list of triples (e.g., “BCG” means block ‘C’ can sit on top of adjacent blocks ‘B’ and ‘C’).

Inputs:

  • bottom: A string representing the base layer of the pyramid. Length NN (2≤N≤82 \le N \le 8).
  • allowed: A list of strings, each length 3, defining valid transitions between two adjacent blocks to a top block.

Outputs:

  • Boolean: True if we can build up to a single peak (length 1), otherwise False.

Implicit Constraints & Edge Cases:

  • Small Width: The base width is very small (N≤8N \le 8). This suggests an exponential solution might be acceptable, but optimization via lookup tables and pruning is necessary for efficiency.
  • Alphabet Size: Characters are limited to ‘A’-‘G’. This keeps the branching factor low (max ~7 options per pair), preventing combinatorial explosion from being too severe even with recursion.
  • Empty Allowed List: If no triples allow a specific transition, that path is invalid immediately. Our lookup logic must handle missing keys gracefully.

Intuition

  1. Brute Force Approach: We could try to build the pyramid level by level using backtracking. At each step (level), for every adjacent pair in the current row, we iterate through all valid top blocks from allowed. If any combination leads to a successful peak, return True.
  2. Why Brute Force is Insufficient: Without optimization, checking every possible path can be slow if many triples are allowed. The branching factor at each step could theoretically multiply quickly (O(KN−1)O(K^{N-1})). However, since we only need existence of a valid pyramid (True/False), and the state space shrinks by one block per level, we should avoid re-evaluating identical row configurations that appear in different branches.
  3. Key Insight: We can model this as a search problem where each node is a specific configuration of blocks at a certain height. To speed up lookups for valid tops given two adjacent base blocks (A, B), we should preprocess allowed into an adjacency map (dictionary). This reduces the transition lookup from O(len(allowed))O(\text{len}(allowed)) to O(1)O(1).
  4. Optimal Approach: Use Depth-First Search (DFS) with memoization. The state for our DFS is defined by the current row string. Since we are building upwards, if a specific row configuration at any level cannot reach the top, we cache that result as False to avoid re-computing it later in different branches of the recursion tree.

Approach

  1. Preprocessing: Convert the allowed list into an adjacency map where keys are pairs (left + right) (as strings) and values are sets of valid top blocks. This allows O(1)O(1) retrieval of possible tops for any adjacent pair. Consistency in key type is crucial here.
  2. DFS Function Definition: Create a helper function, say dfs(current_row), that returns a boolean indicating if the pyramid can be completed from this row upwards.
  3. Base Case: If len(current_row) is 1, we have reached the peak successfully; return True.
  4. Recursive Step: For every adjacent pair in current_row (indices ii and i+1i+1), retrieve all valid tops from our map for that specific pair (row[i] + row[i+1]). Note: We use string concatenation here to match the preprocessing keys, avoiding tuple/string mismatch bugs.
  5. State Generation & Memoization: Construct the next level’s rows by picking one top block per pair. Since we need any path, if any recursive call returns True, propagate it up immediately (pruning). Store results in a memo dictionary keyed by the row string to avoid redundant work on identical configurations encountered at different recursion depths or branches.
  6. Execution: Call dfs(bottom) and return its result.

Complexity Analysis

  • Time Complexity: O(N⋅KN)O(N \cdot K^N), where NN is the length of bottom and KK is the alphabet size (7). However, due to memoization on row configurations and the strict reduction in width (N−1N-1, then N−2N-2, etc.), this effectively behaves closer to a bounded search space. The preprocessing takes O(M)O(M) where MM is length of allowed.
  • Space Complexity: O(N⋅KN)O(N \cdot K^N) for memoization storage (worst case distinct row states) plus recursion stack depth O(N)O(N). Given the constraints (N≤8N \le 8, chars ‘A’-‘G’), this fits well within memory limits.

Solution

from collections import defaultdict
from typing import List, Set

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        # Preprocess allowed triples into a map for O(1) lookup of valid tops per pair
        adj = defaultdict(set)
        for triple in allowed:
            left, right, top = triple[0], triple[1], triple[2]
            # Use string concatenation as key to ensure consistency with row[i]+row[i+1] later
            adj[left + right].add(top)

        # Memoization cache to store results for specific row configurations
        memo = {}

        def dfs(row):
            # Base case: if only one block remains, we reached the peak successfully
            if len(row) == 1:
                return True
            
            # Check if result is already computed for this configuration
            if row in memo:
                return memo[row]
            
            next_row_candidates = []
            # Iterate through adjacent pairs to generate valid tops for the next level
            # We use a nested backtrack function to handle generating combinations of the next level
            
            def backtrack(index, current_next_row):
                if index == len(row) - 1: 
                    # We have formed a complete next level (length N-1)
                    return dfs("".join(current_next_row))
                
                pair_key = row[index] + row[index+1]
                valid_tops = adj[pair_key] # Returns empty set if no allowed tops
                
                for top in valid_tops:
                    current_next_row.append(top)
                    if backtrack(index + 1, current_next_row):
                        memo[row] = True
                        return True
                    current_next_row.pop() # Backtrack
                
                return False

            result = backtrack(0, [])
            
            # Store the final boolean result for this row configuration in cache
            memo[row] = result
            return result
        
        return dfs(bottom)

Edge Cases Handled

  • No Valid Moves: If a pair (A, B) has no allowed top in adj, the loop over valid tops will not execute (empty set), causing backtrack to return False for that branch. The outer function correctly returns False if all branches fail.
  • Single Block Base (Not possible per constraints): Constraints say N≥2N \ge 2, but if it were handled, length check covers base case.
  • Duplicate Allowed Triples: Using a set in adj values handles duplicates automatically without affecting logic.
  • Missing Characters: If characters not present in allowed list are used as bases/tops, the lookup returns empty/None (handled by default dict behavior or explicit checks), correctly returning False for that path.