Pyramid Transition Matrix

Medium Recursion & Backtracking Choice per Position Original on LeetCode

Reported atAirbnb

Pyramid Transition Matrix is a medium recursion & backtracking problem solved with the choice per position pattern. The best approach, optimal (backtracking with memo on rows), runs in O(A^n · A^(n-1)) time and O(A^n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from backtracking up.

Problem

You are stacking lettered blocks into a pyramid. Each row has one block fewer than the row below it, and every block rests on two neighbouring blocks underneath.

Not every stack is legal. A rule is a three-letter string: "XYZ" means a block Z may sit on top of a left block X and a right block Y. The list allowed holds all legal rules; any block placed above a pair must match one of them.

Given the bottom row as the string bottom and the list allowed, return true if you can build the pyramid all the way up to a single block on top, using only allowed placements, and false otherwise.

Examples

Example 1

Input
bottom = "ABC", allowed = ["ABD", "BCE", "DEF", "ABF"]
Output
true
Why
Over AB put D and over BC put E, giving the row DE; the rule DEF then caps the pyramid with F.

Example 2

Input
bottom = "AAB", allowed = ["AAC", "ABD", "CCA", "DDA"]
Output
false
Why
The only possible second row is CD, and no rule has CD as its base.

Example 3

Input
bottom = "BA", allowed = ["BAC", "BAA"]
Output
true
Why
A bottom of two blocks needs a single rule: BA can be topped with C (or A).

Constraints

  • 2 <= bottom.length <= 6
  • 0 <= allowed.length <= 216
  • Every allowed[i] has length 3, and all of them are distinct.
  • All letters are from the set {'A', 'B', 'C', 'D', 'E', 'F'}.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
BacktrackingO(A^(n²))O(n²)
Optimal (backtracking with memo on rows)O(A^n · A^(n-1))O(A^n)

1Backtracking

TimeO(A^(n²))With A = 6 letters, each of the about n² / 2 blocks above the bottom can take up to A values, and without memory the search may try them all.
SpaceO(n²)The recursion holds one partial row per level, about n² / 2 letters in total.

Group the rules by base pair. To decide whether a row can be finished, fill the row above it left to right: for position i, try each block allowed on top of row[i] row[i+1]. When the new row is complete, recurse on it. A row of one block is a finished pyramid.

  1. Build a map from each two-letter base to the list of letters allowed above it.
  2. solve(row): if row has length 1, return true; otherwise return build(row, 0, empty).
  3. build(row, i, next): if next has length row.length - 1, return solve(next).
  4. Otherwise for each letter c above row[i..i+1]: append c, if build(row, i + 1, next) succeeds return true, then remove c.
  5. Return false if no choice works.
class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> tops = new HashMap<>();
        for (String rule : allowed) {
            tops.computeIfAbsent(rule.substring(0, 2), k -> new ArrayList<>()).add(rule.charAt(2));
        }
        return solve(bottom, tops);
    }

    private boolean solve(String row, Map<String, List<Character>> tops) {
        if (row.length() == 1) return true;
        return build(row, 0, new StringBuilder(), tops);
    }

    private boolean build(String row, int i, StringBuilder next, Map<String, List<Character>> tops) {
        if (i == row.length() - 1) return solve(next.toString(), tops);
        List<Character> options = tops.get(row.substring(i, i + 2));
        if (options == null) return false;
        for (char c : options) {
            next.append(c);
            if (build(row, i + 1, next, tops)) return true;
            next.deleteCharAt(next.length() - 1);
        }
        return false;
    }
}

2Optimal (backtracking with memo on rows)

TimeO(A^n · A^(n-1))There are at most A^k distinct rows of length k, each solved once, and solving a row enumerates at most A^(k-1) candidate rows above it. For n ≤ 6 and A = 6 this is a few million steps at worst.
SpaceO(A^n)The memo stores one entry per distinct row seen, plus the recursion stack.

The answer for a row depends only on the row itself, not on how it was produced. Cache the result of solve(row) in a map. Each distinct row is then expanded at most once, which removes the repeated work that makes plain backtracking blow up.

  1. Build the base-pair map as before.
  2. solve(row): if length 1 return true; if row is in the memo, return the stored answer.
  3. Otherwise run build(row, 0, empty) exactly like plain backtracking, store the result for row, and return it.
class Solution {
    private final Map<String, List<Character>> tops = new HashMap<>();
    private final Map<String, Boolean> memo = new HashMap<>();

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        tops.clear();
        memo.clear();
        for (String rule : allowed) {
            tops.computeIfAbsent(rule.substring(0, 2), k -> new ArrayList<>()).add(rule.charAt(2));
        }
        return solve(bottom);
    }

    private boolean solve(String row) {
        if (row.length() == 1) return true;
        Boolean cached = memo.get(row);
        if (cached != null) return cached;
        boolean ok = build(row, 0, new StringBuilder());
        memo.put(row, ok);
        return ok;
    }

    private boolean build(String row, int i, StringBuilder next) {
        if (i == row.length() - 1) return solve(next.toString());
        List<Character> options = tops.get(row.substring(i, i + 2));
        if (options == null) return false;
        for (char c : options) {
            next.append(c);
            if (build(row, i + 1, next)) return true;
            next.deleteCharAt(next.length() - 1);
        }
        return false;
    }
}

Edge cases to test

  • No rules at all: impossible for any bottom
  • A pair in the bottom row that has no rule
  • A pair with several possible tops, where only one choice leads to a full pyramid
  • The same row of blocks reached through different choices, which an unmemoized search rebuilds again and again

Hints

Hint 1

Index the rules by their two-letter base so you can list the possible blocks above any pair instantly.

Hint 2

Build the next row one position at a time, trying each allowed block, and recurse on the finished row. A row of length 1 means success.

Hint 3

Many different paths produce the same intermediate row. Remember which rows are known to fail.

FAQ

What is the best time complexity for Pyramid Transition Matrix?

Optimal (backtracking with memo on rows) runs in O(A^n · A^(n-1)) time and O(A^n) extra space. There are at most A^k distinct rows of length k, each solved once, and solving a row enumerates at most A^(k-1) candidate rows above it. For n ≤ 6 and A = 6 this is a few million steps at worst.

Which pattern does Pyramid Transition Matrix use?

It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.

Is there a brute force solution for Pyramid Transition Matrix?

Yes. Backtracking takes O(A^(n²)) time and O(n²) space. Group the rules by base pair.

Which edge cases should I test for Pyramid Transition Matrix?

No rules at all: impossible for any bottom; A pair in the bottom row that has no rule; A pair with several possible tops, where only one choice leads to a full pyramid; The same row of blocks reached through different choices, which an unmemoized search rebuilds again and again.