Pyramid Transition Matrix

#702 Most AskedMedium

Pyramid Transition Matrix #702 Most Asked

Medium

11 views

Topics:

StringsRecursionDynamic Programming

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains one less block than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific triangular patterns that are allowed. A triangular pattern consists of a single block stacked on top of two blocks. The patterns are given as a list of three-letter strings allowed, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

For example, "ABC" represents a triangular pattern with a 'C' block stacked on top of an 'A' (left) and 'B' (right) block. Note that this is different from "BAC" where 'B' is on the left bottom and 'A' is on the right bottom.

You start with a bottom row of blocks bottom, given as a single string, that you must use as the base of the pyramid.

Given bottom and allowed, return true if you can build the pyramid all the way to the top such that every triangular pattern in the pyramid is in allowed, or false otherwise.

Example 1:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true
Explanation: The allowed triangular patterns are shown on the right.
Starting from the bottom (level 3), we can build "CE" on level 2 and then build "A" on level 1.
There are three triangular patterns in the pyramid, which are "BCC", "CDE", and "CEA". All are allowed.

Example 2:

Input: bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
Output: false
Explanation: The allowed triangular patterns are shown on the right.
Starting from the bottom (level 4), there are multiple ways to build level 3, but trying all the possibilites, you will get always stuck before building level 1.

Constraints:

2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
The letters in all input strings are from the set {'A', 'B', 'C', 'D', 'E', 'F'}.
All the values of allowed are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the alphabet of allowed characters for the base and allowed strings, and how large can the alphabet be?
Can the allowed list ever be empty, and if so, what should be returned?
If there are multiple possible pyramid constructions from the base, should the function return true if *any* of them are valid, or does it need to explore *all* possibilities?
If the base string is empty, should I return true or false?
Is the input 'allowed' guaranteed to be well-formed, meaning each string has length 3 and contains only characters from the allowed alphabet?

Brute Force Solution

Approach

The pyramid transition problem asks if we can build a pyramid from a given bottom string, using allowed three-character building blocks. Brute force means we'll explore every single possible pyramid construction, trying all combinations until we find one that works, or exhaust all options.

Here's how the algorithm would work step-by-step:

Start with the given bottom string, which is the base of our pyramid.
Look at every possible pair of characters in the bottom string.
For each pair, check which characters are allowed to be placed on top of that pair, according to the building block rules.
Try placing each of these allowed characters on top of the pair, one at a time. This creates a new, shorter string for the next level up.
Repeat this process for the new string you just made. Check every pair, find the allowed characters above them, and try building the next level.
Keep going, level by level, trying all the allowed characters at each step to build the pyramid upwards.
If you reach the top level with only one character, you've successfully built a pyramid! Report that it's possible.
If you ever get stuck and can't find any allowed character to place on top of a pair, then you know that particular pyramid path is a dead end. Discard it and try another possibility.
If you try absolutely every single possible combination of characters and still haven't found a valid pyramid, then it's impossible to build one. Report that it's not possible.

Code Implementation

def pyramid_transition(bottom, allowed):
    allowed_transitions = {}
    for transition in allowed:
        base = transition[:2]
        top = transition[2]
        if base not in allowed_transitions:
            allowed_transitions[base] = set()
        allowed_transitions[base].add(top)

    def can_build_pyramid(current_level):
        if len(current_level) == 1:
            return True

        next_level_possibilities = []
        for i in range(len(current_level) - 1):
            pair = current_level[i:i+2]

            # If the pair isn't in allowed, then no further searching needed
            if pair not in allowed_transitions:
                return False
            
            if not next_level_possibilities:
                for character in allowed_transitions[pair]:
                    next_level_possibilities.append(character)
            else:
                new_possibilities = []
                for character in allowed_transitions[pair]:
                    for existing_level in next_level_possibilities:
                        new_possibilities.append(existing_level + character)
                next_level_possibilities = new_possibilities

        # Iterate through all possibilities for the next level
        for next_level in next_level_possibilities:
            if can_build_pyramid(next_level):
                return True
        
        # If all next levels failed, then return False
        return False

    return can_build_pyramid(bottom)

Big(O) Analysis

Time Complexity

O(k^(n^2)) – Let n be the length of the bottom string. In the worst-case scenario, for each pair of characters in a level, we might have k possible characters that can be placed above them, where k is the number of allowed characters in the building blocks. The number of pairs in a level of length 'm' is m-1. Since the pyramid has 'n' levels (counting from the bottom), and at each level of construction, we are exploring possible combinations of characters based on the allowed building blocks, the total number of possible pyramids we might need to explore grows exponentially with the square of the bottom string length. Therefore, the time complexity is approximately O(k^(n^2)), representing the exponential nature of exploring all possible pyramid combinations.

Space Complexity

O(N^2) – The algorithm uses recursion to explore different pyramid constructions. In the worst-case scenario, where almost every combination leads to a potential path, the recursion depth can reach N, where N is the length of the bottom string. Each recursive call stores a new string of length at most N-1 representing the level above, meaning N-1 memory is required per level. Therefore, the auxiliary space used by the call stack accumulates to O(N * (N-1)), which simplifies to O(N^2).

Optimal Solution

Approach

The most efficient way to solve this problem is to figure out what blocks can be built on top of other blocks. Instead of exploring every possible pyramid, we pre-compute which combinations of blocks are allowed and then use this knowledge to check if we can build the pyramid one level at a time, starting from the base.

Here's how the algorithm would work step-by-step:

First, look at the rules and make a list of all the possible pairs of blocks that can form a block above them.
Think of this list like a dictionary: if you see a pair of blocks in the base, you can quickly look up which block, if any, can be placed on top of them.
Now, start with the base of the pyramid. Check every pair of blocks next to each other in the base.
For each pair, use your dictionary to see what block(s) could be placed on top of them.
If you can find at least one valid block for every pair in the base, you've successfully built a possible second level.
Repeat this process for each level of the pyramid, going up one level at a time.
If you can reach the very top with a single block, it means a pyramid can be built, so the answer is 'yes'. If you ever reach a level where there are no valid blocks that can be placed, the pyramid cannot be built, so the answer is 'no'.

Code Implementation

def pyramidTransition(bottom, allowed):
    allowed_combinations = {}

    for combination in allowed:
        base = combination[:2]
        top = combination[2]
        if base not in allowed_combinations:
            allowed_combinations[base] = set()
        allowed_combinations[base].add(top)

    def canBuild(current_level):
        if len(current_level) == 1:
            return True

        next_level_possibilities = []
        for i in range(len(current_level) - 1):
            pair = current_level[i:i+2]
            if pair in allowed_combinations:
                next_level_possibilities.append(allowed_combinations[pair])
            else:
                return False

        # Need to explore different combinations for the next level
        def generateNextLevel(index, current_next_level):
            if index == len(next_level_possibilities):
                return canBuild("".join(current_next_level))

            for possible_block in next_level_possibilities[index]:
                if generateNextLevel(index + 1, current_next_level + [possible_block]):
                    return True
            return False

        # Begin building the next level recursively
        return generateNextLevel(0, [])

    # Check if the bottom level can build the pyramid
    return canBuild(bottom)

Big(O) Analysis

Time Complexity

O(N^2 * A) – Let N be the length of the input base string, and A be the number of rules provided. We first precompute a dictionary mapping pairs of blocks to the blocks that can be placed on top. This takes O(A) time. The algorithm proceeds level by level. At each level, we iterate through all adjacent pairs of blocks, which takes O(N) time. For each pair, we check the dictionary to determine possible blocks above, a lookup that takes O(1) time (assuming a hashmap). In the worst case, we could have N levels. Because we are processing each pair at each level, and the dictionary construction is dominated by the total time, the time complexity is O(N * N * A) which simplifies to O(N^2 * A).

Space Complexity

O(2^N) – The algorithm creates a dictionary (or hash map) to store possible blocks that can be placed on top of pairs of blocks. In the worst case, the size of this dictionary can grow exponentially with the number of possible blocks because we have to consider all possible pairs of blocks and the blocks they can form above them, leading to potentially 3-character combinations where N is the length of the input string representing the base. Additionally, each level of the pyramid is built and stored which, in the worst-case can be exponential. Furthermore, the recursive calls for exploring the pyramid can grow to a depth proportional to the height of the pyramid, which is dependent on the input length, leading to additional stack space. Therefore, auxiliary space is dominated by the storage of possible combinations of blocks and levels of the pyramid.

Edge Cases

Case	How to Handle
Null or empty bottom string	Return True if an empty string is provided as the bottom, as it vacuously satisfies the condition; otherwise, handle the null case with an appropriate error, such as raising an IllegalArgumentException.
Empty allowed list	If the allowed list is empty, and the bottom string is not empty, it is impossible to build a valid pyramid so return False.
Bottom string length is 1	If the bottom string has length 1, the pyramid is trivially valid only if the allowed characters permit creating a level above it which could be one character long, handled within the recursive valid pyramid construction.
Maximum string length exceeding practical recursion depth	Consider memoization or dynamic programming to avoid excessive recursion depth and potential stack overflow errors for long strings.
Allowed list contains duplicate triplets	The algorithm should treat duplicates in the allowed list as the same allowed transition, and it will not negatively affect the generation of the pyramid.
No valid pyramid exists for the given bottom and allowed	The solution should correctly return False when there's no possible pyramid based on the bottom string and allowed transitions by exhaustively checking all possibilities.
Integer overflow in calculating indices, if any indices calculation exists	Use appropriate data types or modular arithmetic to prevent integer overflow when calculating indices based on string length or positions.
Allowed string characters are not consistent with bottom string characters	Validate that all characters in the bottom string are present in the allowed transitions to prevent errors, returning False if invalid characters are present.

Null or empty bottom string

How to Handle:

Return True if an empty string is provided as the bottom, as it vacuously satisfies the condition; otherwise, handle the null case with an appropriate error, such as raising an IllegalArgumentException.

Empty allowed list

How to Handle:

If the allowed list is empty, and the bottom string is not empty, it is impossible to build a valid pyramid so return False.

Bottom string length is 1

How to Handle:

If the bottom string has length 1, the pyramid is trivially valid only if the allowed characters permit creating a level above it which could be one character long, handled within the recursive valid pyramid construction.

Maximum string length exceeding practical recursion depth

How to Handle:

Consider memoization or dynamic programming to avoid excessive recursion depth and potential stack overflow errors for long strings.

Allowed list contains duplicate triplets

How to Handle:

The algorithm should treat duplicates in the allowed list as the same allowed transition, and it will not negatively affect the generation of the pyramid.

No valid pyramid exists for the given bottom and allowed

How to Handle:

The solution should correctly return False when there's no possible pyramid based on the bottom string and allowed transitions by exhaustively checking all possibilities.

Integer overflow in calculating indices, if any indices calculation exists

How to Handle:

Use appropriate data types or modular arithmetic to prevent integer overflow when calculating indices based on string length or positions.

Allowed string characters are not consistent with bottom string characters

How to Handle:

Validate that all characters in the bottom string are present in the allowed transitions to prevent errors, returning False if invalid characters are present.