756. Pyramid Transition Matrix

MediumBit ManipulationDepth-First SearchBreadth-First Search
Leetcode Link

Problem Description

In this problem, we are given the task of building a pyramid block by block. Each block is represented with a color, indicated by a letter. We construct each row of the pyramid such that it has one less block than the row beneath it. The pyramid is built by stacking a single block on top of two adjacent blocks directly below, forming a triangle shape.

We need to follow specific rules for stacking the blocks: only certain triangular patterns are allowed. A pattern is represented as a three-letter string, where the first two letters are the colors of the base blocks (left and right), and the third letter is the color of the block stacked on top.

The base of the pyramid is provided to us in the form of a string bottom, and we are also given a list of allowed patterns allowed. The goal is to determine if it is possible to build the entire pyramid all the way to the top, such that each triangular pattern formed is in the list of allowed patterns. If such a construction is possible, we return true; otherwise, we return false.

Intuition

The intuition behind our solution leverages the concept of depth-first search (DFS). The key is to build the pyramid level by level from the bottom up by checking if every step in the construction process uses a valid pattern from the allowed list.

The algorithm starts at the base row and attempts to construct the next row. For each pair of adjacent blocks in the current row, we look for all possible blocks that can be placed on top of them according to the allowed patterns. If for any pair there are no blocks that can be placed on top, we know right away that completing the pyramid is impossible, and we return false.

We repeatedly apply this process for each new row, reducing the width by one block each time until we reach the top of the pyramid (when the length of the string representing the row is 1). If at any point we cannot form a new row that matches the allowed patterns, we stop and return false. Otherwise, if we successfully reach the top, we return true.

The Python code uses a dfs (depth-first search) function which is recursively called to explore all possible combinations of blocks. The pairwise utility function is used to iterate over the bottom row string to get adjacent pairs. The product utility from itertools generates all possible combinations for the next row. Memoization via the @cache decorator is used to avoid redundant calculations by storing previously computed results of the DFS, optimizing the performance for large pyramids.

Learn more about Depth-First Search and Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution uses several key algorithms, data structures, and programming concepts:

  1. Depth-First Search (DFS): The recursive function dfs performs a depth-first search to construct possible configurations of the pyramid from the bottom up, level by level. Each invocation of dfs tries to build the next level based on currently considered blocks.

  2. Caching/Memoization: The @cache decorator is used to cache the results of the dfs function. This means that if the function is called with the same input more than once, it won't repeat the computation and will simply return the cached result. This optimization is important because the same configurations can occur many times, especially further up the pyramid.

  3. Data Structure - defaultdict: The variable d is a defaultdict of lists, used to map each possible pair of blocks to the blocks which can be placed on top of them according to the allowed patterns. This data structure is ideal for quick lookups and managing dynamic key-value pairs where each key might correspond to multiple values.

  4. Itertools' product Function: This function is used to compute the Cartesian product of lists which represent the potential blocks for the top level based on the current level configuration. For example, if you have two possible blocks that can go on top of a pair and three possible blocks for the next pair, product will generate all combinations of these choices to explore.

  5. Pairwise Iteration: A utility routine (implied to exist via the function pairwise) generates pairs from the current row to look up in the defaultdict d. Each pair needs to be considered to determine the possible blocks for the upper level.

Here's a step-by-step walkthrough of the code:

  • d is created as a defaultdict to hold a list for each pair of blocks. This is populated based on the allowed input, mapping each pair to corresponding top blocks.
  • The recursive helper function dfs is defined. It is decorated with @cache to optimize for performance using memoization.
  • dfs works as follows:
    • If the length of the current string s is 1, that means we've constructed the pyramid to the top, and we return true.
    • Otherwise, we look at each pair of adjacent blocks using pairwise(s) and find all possible top blocks from d.
    • If there are no possible top blocks for any pair (not cs), the function returns false, as the pyramid cannot be completed.
    • Next, for each combination of top blocks generated by product(*t), the function recursively calls dfs on the new level formed by joining these blocks (''.join(nxt)).
    • It returns true if any of these recursive calls succeed in building the whole pyramid, otherwise false.
  • The solution begins by calling dfs(bottom), initiating the depth-first search with the base level.

This approach systematically explores all potential configurations by building from the bottom row to the top, effectively checking if a proper pyramid can be built according to the rules defined by allowed.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above for better understanding.

Suppose we have the base of the pyramid represented by the string bottom as "ABCD" and an allowed list of patterns ["ABD", "BCE", "CAF", "DCG", "EFG"].

The goal is to check if we can build the entire pyramid up to the top block by using the patterns provided in allowed.

The dfs function will attempt to build the pyramid level by level. The initial call will be dfs("ABCD").

Let's go through the process:

  1. We use the pairwise function on our bottom "ABCD" to get the list of pairs: [("A", "B"), ("B", "C"), ("C", "D")].
  2. We use our defaultdict d, which we prepared earlier using the allowed list, to find the possible top blocks for each pair.
    • For ("A", "B"), we look at d and find "D" (because "ABD" is in allowed).
    • For ("B", "C"), we look at d and find "E" (because "BCE" is in allowed).
    • For ("C", "D"), we look at d and find "G" (because "CDG" is in allowed).
  3. With these possible top blocks, we use the product function to get all combinations for the next level which in this example is a single combination: ["D", "E", "G"].
  4. For each combination from the Cartesian product, we join them to form a new string "DEG" and then call dfs recursively with this new string.
  5. We recursively perform these steps until we either cannot form a new row (not cs branch in the dfs function returns false) or we build the pyramid to the top with a single block (the length of string s becomes 1 and we return true).

When dfs("DEG") is called, the process repeats:

  1. pairwise("DEG") gives [("D", "E"), ("E", "G")].
  2. Looking up the defaultdict d, we see:
    • ("D", "E") has no top block in d.
    • ("E", "G") has no top block in d either.

Since no top block can be placed on both these pairs, dfs("DEG") returns false, and hence, dfs("ABCD") also returns false. We cannot build a complete pyramid with the given base and allowed patterns.

Here, we systematically attempted all possible ways to build the pyramid and finally determined that it is not possible to build it to the top using the given rules. Therefore, our function would ultimately return false for this example.

Solution Implementation

1from itertools import product
2from collections import defaultdict
3from functools import lru_cache
4
5class Solution:
6    def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
7        # Use lru_cache for memoization instead of @cache which is not available in Python 3
8        @lru_cache(maxsize=None)
9        def build_pyramid(current_level):
10            # Base case: if current level is a single block, the pyramid is completed successfully
11            if len(current_level) == 1:
12                return True
13          
14            # Try to build the next level above the current one
15            next_level_options = []
16            for i in range(len(current_level) - 1):
17                # Get blocks that can be placed on top of the current pair
18                possible_blocks = transition_dict[current_level[i], current_level[i + 1]]
19                # If there are no possible blocks for the current pair, pyramid cannot be completed
20                if not possible_blocks:
21                    return False
22                next_level_options.append(possible_blocks)
23          
24            # Use itertools.product to generate all combinations for the next level
25            # And check recursively if any combination can build the pyramid to completion
26            return any(build_pyramid(''.join(next_level)) for next_level in product(*next_level_options))
27
28        # Create a dictionary to store allowed transitions
29        transition_dict = defaultdict(list)
30        for block_left, block_right, block_top in allowed:
31            transition_dict[block_left, block_right].append(block_top)
32
33        # Kick off the recursive pyramid building process starting from the bottom level
34        return build_pyramid(bottom)
35
1class Solution {
2    // 'transitionMatrix' stores all possible transitions from a pair of blocks to an upper block, using bitwise representation.
3    private int[][] transitionMatrix = new int[7][7];
4    // 'memoization' is used for storing already computed results to avoid reprocessing.
5    private Map<String, Boolean> memoization = new HashMap<>();
6
7    public boolean pyramidTransition(String bottom, List<String> allowed) {
8        // Populate the transition matrix based on 'allowed' transitions.
9        for (String transition : allowed) {
10            int first = transition.charAt(0) - 'A';
11            int second = transition.charAt(1) - 'A';
12            // Update matrix with bitwise OR to add the new transition.
13            transitionMatrix[first][second] |= 1 << (transition.charAt(2) - 'A');
14        }
15        // Start the DFS with the given bottom and an empty StringBuilder for the next level.
16        return dfs(bottom, new StringBuilder());
17    }
18
19    boolean dfs(String currentLevel, StringBuilder nextLevel) {
20        // Base case: if the current level has only one block, the pyramid is complete.
21        if (currentLevel.length() == 1) {
22            return true;
23        }
24        // Check if the next level is complete and if so, start DFS on the new level.
25        if (nextLevel.length() + 1 == currentLevel.length()) {
26            return dfs(nextLevel.toString(), new StringBuilder());
27        }
28        // Create a unique key to check/store the state in memoization.
29        String key = currentLevel + "." + nextLevel.toString();
30        if (memoization.containsKey(key)) {
31            return memoization.get(key);
32        }
33
34        // Get characters from the current level which will determine the next block of the level above.
35        int first = currentLevel.charAt(nextLevel.length()) - 'A';
36        int second = currentLevel.charAt(nextLevel.length() + 1) - 'A';
37        // Check possible transitions for the pair of blocks.
38        int possibleTransitions = transitionMatrix[first][second];
39        for (int i = 0; i < 7; ++i) {
40            // If the ith transition is possible, append the corresponding character.
41            if (((possibleTransitions >> i) & 1) == 1) {
42                nextLevel.append((char) ('A' + i));
43                if (dfs(currentLevel, nextLevel)) {
44                    // If DFS succeeds, set true in memoization and return true.
45                    memoization.put(key, true);
46                    return true;
47                }
48                // If DFS doesn't succeed, remove the last character and try the next possibility.
49                nextLevel.deleteCharAt(nextLevel.length() - 1);
50            }
51        }
52        // After trying all possibilities, if none work, set false in memoization and return false.
53        memoization.put(key, false);
54        return false;
55    }
56}
57
1#include <string>
2#include <vector>
3#include <unordered_map>
4#include <cstring>
5
6class Solution {
7public:
8    int transitionTable[7][7];
9    std::unordered_map<std::string, bool> memoization;
10
11    // Determines if a pyramid transition is possible with the given bottom row
12    // and the list of allowed transitions.
13    bool pyramidTransition(std::string bottom, std::vector<std::string>& allowed) {
14        // Initialize the transition table with zeroes
15        std::memset(transitionTable, 0, sizeof(transitionTable));
16
17        // Populate the transition table using the allowed transitions
18        for (const auto& triplet : allowed) {
19            int firstChar = triplet[0] - 'A';
20            int secondChar = triplet[1] - 'A';
21            transitionTable[firstChar][secondChar] |= 1 << (triplet[2] - 'A');
22        }
23
24        // Start the depth-first search algorithm with an empty temporary string
25        return depthFirstSearch(bottom, "");
26    }
27
28    // Helper function for depth-first search of pyramid transition
29    bool depthFirstSearch(std::string& currentBottom, std::string currentTop) {
30        // If the current bottom row has only one block, the pyramid is complete
31        if (currentBottom.size() == 1) return true;
32
33        // If the top row is only one block shorter than the bottom row,
34        // move to next top row and start again
35        if (currentTop.size() + 1 == currentBottom.size()) {
36            return depthFirstSearch(currentTop, "");
37        }
38
39        // Create a key from the current state of bottom and top rows
40        std::string key = currentBottom + "." + currentTop;
41
42        // If this state has been previously computed, return its result
43        if (memoization.count(key)) return memoization[key];
44
45        int firstCharIndex = currentBottom[currentTop.size()] - 'A';
46        int secondCharIndex = currentBottom[currentTop.size() + 1] - 'A';
47        int possibleTransitions = transitionTable[firstCharIndex][secondCharIndex];
48
49        // Check all possible characters for the next block in the top row
50        for (int i = 0; i < 7; ++i) {
51            if ((possibleTransitions >> i) & 1) {
52                // Recursively try to build the pyramid from this transition
53                if (depthFirstSearch(currentBottom, currentTop + static_cast<char>(i + 'A'))) {
54                    // If successful, memoize the result and return true
55                    memoization[key] = true;
56                    return true;
57                }
58            }
59        }
60
61        // If no transitions lead to a successful pyramid, memoize the result as false
62        memoization[key] = false;
63        return false;
64    }
65};
66
1// Import the required modules
2import { memset } from "node:buffer";
3
4// Represents the transition table mapping two characters to its possible upper characters
5let transitionTable: number[][];
6
7// Memoization map to store computed states of pyramid transitions
8let memoization: { [key: string]: boolean };
9
10// Determines if a pyramid transition is possible with the given bottom row
11// and the list of allowed transitions.
12function pyramidTransition(bottom: string, allowed: string[]): boolean {
13    // Initialize the transition table with zeroes
14    transitionTable = Array.from({ length: 7 }, () => Array(7).fill(0));
15
16    // Populate the transition table using the allowed transitions
17    allowed.forEach(triplet => {
18        const firstChar: number = triplet.charCodeAt(0) - 'A'.charCodeAt(0);
19        const secondChar: number = triplet.charCodeAt(1) - 'A'.charCodeAt(0);
20        transitionTable[firstChar][secondChar] |= 1 << (triplet.charCodeAt(2) - 'A'.charCodeAt(0));
21    });
22
23    // Initialize the memoization map
24    memoization = {};
25
26    // Start the depth-first-search algorithm with an empty temporary string
27    return depthFirstSearch(bottom, "");
28}
29
30// Helper function for depth-first search of pyramid transition
31function depthFirstSearch(currentBottom: string, currentTop: string): boolean {
32    // If the current bottom row has only one block, the pyramid is complete
33    if (currentBottom.length === 1) return true;
34
35    // If the top row is only one block shorter than the bottom row,
36    // move to the next top row and start again
37    if (currentTop.length + 1 === currentBottom.length) {
38        return depthFirstSearch(currentTop, "");
39    }
40
41    // Create a key from the current state of bottom and top rows
42    const key: string = `${currentBottom}.${currentTop}`;
43
44    // If this state has been previously computed, return its result
45    if (memoization[key] !== undefined) return memoization[key];
46
47    const i: number = currentTop.length;
48    const firstCharIndex: number = currentBottom.charCodeAt(i) - 'A'.charCodeAt(0);
49    const secondCharIndex: number = currentBottom.charCodeAt(i + 1) - 'A'.charCodeAt(0);
50    const possibleTransitions: number = transitionTable[firstCharIndex][secondCharIndex];
51
52    // Check all possible characters for the next block in the top row
53    for (let j = 0; j < 7; ++j) {
54        if ((possibleTransitions >> j) & 1) {
55            // Recursively try to build the pyramid from this transition
56            if (depthFirstSearch(currentBottom, currentTop + String.fromCharCode(j + 'A'.charCodeAt(0)))) {
57                // If successful, memoize the result and return true
58                memoization[key] = true;
59                return true;
60            }
61        }
62    }
63
64    // If no transitions lead to a successful pyramid, memoize the result as false
65    memoization[key] = false;
66    return false;
67}
68
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The provided code defines a function dfs that explores all valid pyramids that can be built on top of the string s by using the triangles defined in the allowed list. Every time dfs is called, it checks if s has length 1 (base case), in which case it returns True. If not, it constructs all possible permutations of new strings (nxt) for the next level of the pyramid using the cartesian product of allowed characters for each adjacent pair in the current level. This leads to a branching factor that could potentially be exponential in the worst case.

Let's denote n as the length of the input string bottom. At every level of the pyramid, the length of the string decreases by 1. Hence, there are at most n-1 levels in the recursion tree. The branching factor at level i is at most |allowed|^i because each pair of characters can potentially map to |allowed| different characters, making the branching factor for all levels combined:

1O(|allowed|^(n-2) + |allowed|^(n-3) + ... + |allowed|^1 + |allowed|^0)

This sum is dominated by the largest term, |allowed|^(n-2), so we can consider the time complexity to be exponential, specifically:

1O(|allowed|^(n-2))

However, due to caching of intermediate results (@cache), overlapping subproblems are solved only once, improving the time complexity particularly for cases with many overlapping subproblems. The actual time complexity will depend on the specific values in allowed and how many different combinations they allow for each pair of characters in bottom.

Space Complexity

The space complexity is mainly dictated by the memory used for caching and the call stack due to recursion. The depth of the recursion tree is at most n-1, and the cache will store at most O(2^(n-1)) states given that each level's state is determined by n-1, n-2, ..., 2, 1 characters, and for each character, there are 2 possibilities (included or not).

The auxiliary space used by the variables within dfs like t, which holds the current level combinations, is the number of pairs in the current level, which is at most n-1. So the auxiliary space complexity is O(n). This is small compared to the call stack and cache.

Therefore, the space complexity is also:

1O(2^(n-1))

This space complexity takes into account the call stack and the cache, which usually dominates the space used by the algorithm. However, note that if the allowed list allows for a large number of valid characters for each pair, the space complexity might be larger because the cache would need to hold a larger number of possible strings at each level.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫