756. Pyramid Transition Matrix

Time: O(n · 7^n)

Space: O(n · 7^n)

Approach

Bitmask memoized DFS; precompute allowed top-character bitmasks for each base pair from the allowed strings.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Hash Table

Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.

Breadth-First Search

BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.

756.cs

// Approach: Bitmask memoized DFS; precompute allowed top-character bitmasks for each base pair from the allowed strings.
// Time: O(n · 7^n) Space: O(n · 7^n)

public class Solution
{
    // Stores allowed transitions: transitions[a][b] is a bitmask representing possible top blocks
    // for base blocks 'A'+a and 'A'+b
    private int[][] transitions = new int[7][];
    // Memoization cache: key is "currentLevel.nextLevelBuiltSoFar", value is whether pyramid can be completed
    private Dictionary<string, bool> memo = new Dictionary<string, bool>();

    public Solution()
    {
        for (int i = 0; i < 7; i++)
            transitions[i] = new int[7];
    }

    public bool PyramidTransition(string bottom, IList<string> allowed)
    {
        // Build transition table from allowed triplets
        // Each triplet "XYZ" means blocks X and Y can support block Z
        foreach (string triplet in allowed)
        {
            int leftBlock = triplet[0] - 'A';
            int rightBlock = triplet[1] - 'A';
            int topBlock = triplet[2] - 'A';

            // Use bitmask to store multiple possible top blocks for each pair
            transitions[leftBlock][rightBlock] |= (1 << topBlock);
        }

        // Start DFS from bottom level with empty next level
        return CanBuildPyramid(bottom, new StringBuilder());
    }

    private bool CanBuildPyramid(string currentLevel, StringBuilder nextLevel)
    {
        // Base case: reached the top of pyramid (single block)
        if (currentLevel.Length == 1)
            return true;

        // Current level is complete, move to next level up
        if (nextLevel.Length + 1 == currentLevel.Length)
            return CanBuildPyramid(nextLevel.ToString(), new StringBuilder());

        // Create memoization key
        string memoKey = currentLevel + "." + nextLevel.ToString();
        if (memo.TryGetValue(memoKey, out bool cachedResult))
            return cachedResult;

        // Get current pair of blocks to process
        int leftBlockIndex = currentLevel[nextLevel.Length] - 'A';
        int rightBlockIndex = currentLevel[nextLevel.Length + 1] - 'A';

        // Get bitmask of possible blocks that can go on top of this pair
        int possibleBlocks = transitions[leftBlockIndex][rightBlockIndex];

        // Try each possible block
        for (int blockIndex = 0; blockIndex < 7; blockIndex++)
        {
            // Check if this block is allowed on top of current pair
            if (((possibleBlocks >> blockIndex) & 1) == 1)
            {
                // Try placing this block
                nextLevel.Append((char)('A' + blockIndex));

                // Recursively check if pyramid can be completed
                if (CanBuildPyramid(currentLevel, nextLevel))
                {
                    memo[memoKey] = true;
                    return true;
                }

                // Backtrack: remove the block we just tried
                nextLevel.Length--;
            }
        }

        // No valid pyramid can be built from this state
        memo[memoKey] = false;
        return false;
    }
}

Was this solution helpful?