LeetCode 756 - Pyramid Transition Matrix

Here’s a full, detailed technical solution guide for LeetCode 756 - Pyramid Transition Matrix, following your formatting rules precisely.

leetcodemediumhash-tablestringbacktrackingbit-manipulation

LeetCode Problem 756

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking, Bit Manipulation

Solution

Here’s a full, detailed technical solution guide for LeetCode 756 - Pyramid Transition Matrix, following your formatting rules precisely.

Problem Understanding

The problem is asking us to determine whether a pyramid of blocks can be constructed from a given bottom row of blocks, such that all blocks above obey certain triangular stacking rules. Each block has a color represented by a single uppercase letter from A to F. Each block in a row above the bottom must sit on exactly two adjacent blocks below it, forming a triangle, and only specific top-block outcomes are allowed for each pair of bottom blocks. These allowed patterns are provided as a list of strings, where each string has length 3: the first two letters are the bottom blocks, and the third is the allowed top block.

The input consists of:

  • bottom: a string representing the base row of the pyramid.
  • allowed: a list of unique three-character strings defining allowed triangular patterns.

The output is a boolean:

  • true if the pyramid can be built all the way to a single top block while obeying all allowed patterns.
  • false otherwise.

Constraints clarify the problem scale:

  • 2 <= bottom.length <= 6, so the maximum height is 6.
  • 0 <= allowed.length <= 216 because there are 6 letters, giving 6*6*6 = 216 possible triples.
  • All letters are from {'A','B','C','D','E','F'}, simplifying indexing and storage.

Important edge cases include:

  • A bottom row where no allowed patterns exist for a pair of adjacent blocks.
  • Allowed patterns that contain multiple possible top blocks for a single pair.
  • Minimum and maximum bottom row lengths, i.e., 2 and 6.

Approaches

Brute Force

The brute-force approach is to attempt all possible ways to place blocks on top row by row. For each pair of adjacent blocks, we find all allowed top blocks and recursively try all combinations to build the next level. This approach guarantees correctness because it explores all possible pyramids, but it is slow: the number of combinations grows exponentially with the pyramid height. For a bottom of length n, each pair could have up to 6 possible top blocks, leading to O(6^(n-1 + n-2 + ... + 1)) = O(6^(n(n-1)/2)) possibilities.

Optimal Approach

The key insight is that we can use a hash map to efficiently look up allowed top blocks for each bottom pair and employ DFS (Depth-First Search) to recursively attempt building the pyramid. Since the bottom length is small (<=6), DFS with pruning is feasible. By memoizing intermediate levels or avoiding impossible paths early, we prevent unnecessary recursion. This approach leverages the small input constraints and the structure of the problem (top blocks depend only on adjacent bottom pairs).

Approach Time Complexity Space Complexity Notes
Brute Force O(6^(n(n-1)/2)) O(n) Try all possible combinations recursively
Optimal (DFS + Hash Map) O(6^(n(n-1)/2)) worst-case, practical pruning reduces this O(allowed.length) for hash map + O(n) recursion DFS with allowed top-block lookup and pruning

Algorithm Walkthrough

  1. Preprocess allowed patterns: Create a hash map pair_to_tops where the key is a tuple (a, b) of two bottom blocks, and the value is the set of allowed top blocks. This allows constant-time lookup during recursion.
  2. DFS recursive function: Define a function can_build(current_level) that returns True if the pyramid can be completed starting from current_level.
  3. Base case: If current_level has length 1, it is the top of the pyramid. Return True.
  4. Generate next level possibilities: For each adjacent pair of blocks (current_level[i], current_level[i+1]), retrieve possible top blocks from pair_to_tops. If no allowed top exists, return False immediately.
  5. Backtracking: Recursively attempt to build all combinations of the next level using the allowed top blocks for each pair. This can be implemented by generating all strings that represent the next level and calling can_build on each one.
  6. Return: If any combination of the next level leads to a complete pyramid, return True. If none do, return False.

Why it works: At each step, we only explore valid pyramids based on allowed patterns. Since DFS tries all possible top block combinations, no valid configuration is missed, guaranteeing correctness.

Python Solution

from typing import List, Dict, Set
from collections import defaultdict

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        pair_to_tops: Dict[str, Set[str]] = defaultdict(set)
        for triple in allowed:
            pair_to_tops[triple[:2]].add(triple[2])

        def can_build(current_level: str) -> bool:
            if len(current_level) == 1:
                return True  # Reached the top successfully

            next_level_options = []

            def dfs_next_level(index: int, path: List[str]):
                if index == len(current_level) - 1:
                    next_level_options.append(''.join(path))
                    return
                pair = current_level[index:index+2]
                if pair not in pair_to_tops:
                    return  # Dead end, no allowed top
                for top in pair_to_tops[pair]:
                    path.append(top)
                    dfs_next_level(index + 1, path)
                    path.pop()

            dfs_next_level(0, [])
            for next_level in next_level_options:
                if can_build(next_level):
                    return True
            return False

        return can_build(bottom)

Implementation Walkthrough: The pair_to_tops dictionary stores all allowed top blocks for each bottom pair. can_build recursively attempts to build the pyramid. dfs_next_level generates all valid next-level strings. The recursion ensures that all valid configurations are considered, and pruning occurs when no allowed top exists for a pair.

Go Solution

func pyramidTransition(bottom string, allowed []string) bool {
	pairToTops := make(map[string][]byte)
	for _, triple := range allowed {
		pair := triple[:2]
		top := triple[2]
		pairToTops[pair] = append(pairToTops[pair], top)
	}

	var canBuild func(current string) bool
	canBuild = func(current string) bool {
		if len(current) == 1 {
			return true
		}
		var nextLevels []string

		var dfsNext func(index int, path []byte)
		dfsNext = func(index int, path []byte) {
			if index == len(current)-1 {
				nextLevels = append(nextLevels, string(path))
				return
			}
			pair := current[index : index+2]
			tops, ok := pairToTops[pair]
			if !ok {
				return
			}
			for _, top := range tops {
				dfsNext(index+1, append(path, top))
			}
		}

		dfsNext(0, []byte{})
		for _, next := range nextLevels {
			if canBuild(next) {
				return true
			}
		}
		return false
	}

	return canBuild(bottom)
}

Go-specific Notes: Go uses slices instead of lists, and strings are immutable, so we carefully build next levels using byte slices. The recursive DFS logic is analogous to Python, with map[string][]byte serving as the hash map.

Worked Examples

Example 1

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]

  1. Preprocess allowed patterns:
pair_to_tops = {
 "BC": {"C"},
 "CD": {"E"},
 "CE": {"A"},
 "FF": {"F"}
}
  1. Bottom "BCD" → adjacent pairs "BC" and "CD".
  2. Next level options:
  • "BC" → "C", "CD" → "E" → next level "CE".
  1. "CE" → only pair "CE" → "A", top "A" reached.
  2. Pyramid built successfully, return True.

Example 2

Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]

  1. Preprocess allowed patterns:
pair_to_tops = {
 "AA": {"B", "C"},
 "AB": {"B"},
 "AC": {"C"},
 "BC": {"D"},
 "BD": {"E"},
 "DE": {"F"}
}
  1. Bottom "AAAA" → pairs "AA","AA","AA".
  2. Next level options: all combinations of "B" or "C" for each pair.
  3. Recursively attempting all next levels leads to dead ends; cannot reach top, return False.

Complexity Analysis

Measure Complexity Explanation
Time O(6^(n(n-1)/2)) worst-case For bottom length n, each pair can have up to 6 tops. Total possibilities for all pairs in pyramid is exponential
Space O(allowed.length + n) pair_to_tops hash map stores allowed patterns; recursion stack depth is up to n

Although exponential in theory, the constraints (n <= 6, letters <=