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 ().allowed: A list of strings, each length 3, defining valid transitions between two adjacent blocks to a top block.
Outputs:
- Boolean:
Trueif we can build up to a single peak (length 1), otherwiseFalse.
Implicit Constraints & Edge Cases:
- Small Width: The base width is very small (). 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
- 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. - 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 (). 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.
- 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 preprocessallowedinto an adjacency map (dictionary). This reduces the transition lookup from to . - 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
Falseto avoid re-computing it later in different branches of the recursion tree.
Approach
- Preprocessing: Convert the
allowedlist into an adjacency map where keys are pairs(left + right)(as strings) and values are sets of valid top blocks. This allows retrieval of possible tops for any adjacent pair. Consistency in key type is crucial here. - 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. - Base Case: If
len(current_row)is 1, we have reached the peak successfully; returnTrue. - Recursive Step: For every adjacent pair in
current_row(indices and ), 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. - 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. - Execution: Call
dfs(bottom)and return its result.
Complexity Analysis
- Time Complexity: , where is the length of
bottomand is the alphabet size (7). However, due to memoization on row configurations and the strict reduction in width (, then , etc.), this effectively behaves closer to a bounded search space. The preprocessing takes where is length ofallowed. - Space Complexity: for memoization storage (worst case distinct row states) plus recursion stack depth . Given the constraints (, 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 inadj, 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 , but if it were handled, length check covers base case.
- Duplicate Allowed Triples: Using a set in
adjvalues 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.