grid47 Exploring patterns and algorithms
Aug 23, 2024
7 min read
Solution to LeetCode 756: Pyramid Transition Matrix Problem
You are building a pyramid by stacking blocks, each represented by a color denoted by a letter. Each row above the bottom consists of one less block, centered on the row beneath. Only specific triangular patterns of blocks are allowed. A triangular pattern consists of three blocks: two at the bottom and one on top. Given the bottom row and allowed patterns, determine if it’s possible to construct the pyramid.
Problem
Approach
Steps
Complexity
Input: You are given a string representing the bottom row of blocks, and a list of strings representing the allowed triangular patterns.
• Explanation: Start with 'XYZ'. Use 'XYZ' to form 'ZY' on the next level, then form 'Y' on the top level. All patterns are valid, so the pyramid can be built.
• Explanation: Start with 'AAA'. There are no valid patterns to form a level from 'AA', so the pyramid cannot be built.
Approach: The approach is to use a recursive function to check if the pyramid can be constructed level by level, verifying the allowed triangular patterns for each pair of adjacent blocks in the current row.
Observations:
• We need to recursively reduce the problem from bottom to top, checking the allowed patterns for each adjacent pair of blocks.
• We can use a hash map to store the allowed patterns for efficient look-up during the recursive checks.
Steps:
• 1. Create a hash map of allowed triangular patterns where the key is the pair of blocks at the bottom and the value is the top block.
• 2. Start from the bottom row and recursively check if the pyramid can be constructed by trying to form each subsequent row using the allowed patterns.
• 3. Return true if the pyramid can be built or false if any row cannot be formed.
Empty Inputs:
• The allowed list may be empty, in which case it's impossible to form the pyramid.
Large Inputs:
• The solution must handle the upper limit of allowed patterns efficiently.
Special Values:
• No special cases for the input constraints.
Constraints:
• The solution must handle the bottom row's length ranging from 2 to 6 and up to 216 allowed patterns.
unordered_set<string> invalid;
boolpyramidTransition(string bottom, vector<string>& allowed) {
invalid.clear();
unordered_map<string, vector<char>> m;
for(auto&s:allowed) m[s.substr(0, 2)].push_back(s.back());
return helper(bottom, m, 0, "");
}
boolhelper(string bottom, unordered_map<string, vector<char>>& m, int start, string next){
if(bottom.size() ==1) returntrue;
elseif(invalid.find(bottom) != invalid.end()) returnfalse;
elseif(start == (int)bottom.size() -1) {
bool res = helper(next, m, 0, "");
if (!res) { invalid.insert(next); }
return res;
}
for(charc : m[bottom.substr(start, 2)])
if(helper(bottom, m, start+1, next+c)) returntrue;
returnfalse;
}
1 : Data Structures
unordered_set<string> invalid;
Creates an unordered set 'invalid' to keep track of previously visited bottom rows to avoid cycles or redundant checks.
Begins the definition of the 'pyramidTransition' function. The function checks if a pyramid can be built based on the given bottom row and allowed stone transitions.
3 : Clear Invalid Set
invalid.clear();
Clears the 'invalid' set to ensure no old invalid configurations are present before checking the new pyramid bottom.
4 : Mapping Transitions
unordered_map<string, vector<char>> m;
Defines an unordered map 'm' where the key is a pair of stones and the value is a list of possible stones that can be placed above the pair.
Fills the map 'm' by iterating through the allowed transitions. For each transition, it maps the first two characters of the transition to the corresponding stone that can be placed above it.
6 : Recursion
returnhelper(bottom, m, 0, "");
Calls the helper function to start the process of attempting to build the pyramid, beginning from the bottom and using the transition map 'm'.
7 : Helper Function Start
boolhelper(string bottom, unordered_map<string, vector<char>>& m, int start, string next){
Starts the definition of the 'helper' function. This function handles the recursive process of trying to build the pyramid from the bottom upwards.
8 : Base Case - Single Stone
if(bottom.size() ==1) returntrue;
Base case of the recursion. If the bottom row has only one stone, the pyramid is successfully built.
Checks if the current bottom row has been processed before. If it has, the function returns false to avoid infinite recursion or redundant calculations.
10 : Recursive Step
elseif(start == (int)bottom.size() -1) {
If the current start index is the last stone in the bottom row, the function will attempt to build the next layer above it.
11 : Recursive Call
bool res = helper(next, m, 0, "");
Recursively calls the helper function with the newly formed next layer (the stones placed above the current bottom).
12 : Memoization
if (!res) { invalid.insert(next); }
If the recursion fails, the next layer configuration is added to the 'invalid' set to avoid future redundant checks.
13 : Return Result
return res;
Returns the result of the recursive call, indicating whether it was possible to build the pyramid from the current bottom layer.
14 : Character Iteration
for(charc : m[bottom.substr(start, 2)])
Iterates over all possible stone transitions that can be placed above the current two stones at the 'start' position of the bottom row.
15 : Recursive Call with New Stone
if(helper(bottom, m, start+1, next+c)) returntrue;
Recursively attempts to build the pyramid by adding each possible stone transition to the 'next' layer, checking if a valid configuration can be formed.
16 : Return False
returnfalse;
If no valid configuration is found after iterating through all possible stone transitions, the function returns false.
Best Case: O(1)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The solution involves checking all possible pairs at each level, leading to a time complexity proportional to the size of the bottom row and the allowed patterns.
Best Case: O(n)
Worst Case: O(n^2)
Description: The space complexity is proportional to the number of levels in the pyramid and the number of allowed patterns.
