The same unit, already there

Before a transit authority creates a unit, someone has to check that the same unit is not already sitting somewhere else in the chart.

The problem

The chart hangs off one unit at the top. Under a unit there are at most two sub-units, drawn in a fixed order — first and second — and that order matters. Each unit is recorded by its headcount.

You are given the whole chart and a proposed unit, which is itself a small chart. Say whether the proposal already exists: whether some unit in the chart has the same headcount, the same sub-units in the same order, and the same everything below that, all the way down to the bottom. A unit counts as one of its own sub-units, so a proposal identical to the whole chart is already there.

Input. chart and unit — each in level order, None where a unit has no sub-unit on that side.

Output. True if the proposed unit already exists, False otherwise.

Example.

chart = [12, 5, 9, 2, 7], unit = [5, 2, 7]   ->  True

The chart's unit of 5 has 2 first and 7 second, and nothing below those. The proposal is that unit exactly.

A second example, where only the top of the proposal matches:

chart = [12, 5, 9, 2, 7, None, None, 1], unit = [5, 2, 7]   ->  False

Here the chart's 2 has a team of 1 under it. The proposal stops at 2, the real unit does not, so they are not the same unit. Swapping the sub-units in the proposal, [5, 7, 2], is also False: the order is part of the chart.

Constraints.

• 1 <= units in the chart <= 2 x 10^4
• 1 <= units in the proposal <= 10^3
• 1 <= headcount <= 10^4, and headcounts repeat freely

Hints

Approach

Brute force

For every unit in the chart, compare it against the proposal unit by unit, giving up at the first difference. That is O(n x m): 2 x 10^7 comparisons at the limits, and a chart where many units share a headcount really does reach them.

The insight

Write each chart as a preorder reading with a blank recorded for every sub-unit that is not there, and a whole unit becomes one unbroken stretch of that reading — so the question is a substring search.

Preorder writes a unit's headcount, then the entire reading of its first sub-unit, then the entire reading of its second, with nothing else in between. So each unit occupies one contiguous stretch, and any stretch equal to the proposal's reading must begin where some unit begins.

The blanks are the precondition, not decoration. Without them a unit with one sub-unit first reads exactly like a unit with one sub-unit second, and the search happily reports a match that does not exist. With them, no two different charts share a line.

Algorithm

1. Build both charts from their level-order lists.
2. Read each one preorder into a list of tokens, appending a blank token wherever a sub-unit is missing.
3. Build the border table of the proposal's tokens: for each prefix, the longest proper prefix that is also its suffix.
4. Scan the chart's tokens, falling back through the border table on a mismatch instead of restarting.
5. Return True if the scan ever matches the whole proposal.

Complexity

Time O(n + m) — each unit yields at most three tokens, and the search never steps backwards over the chart. Space O(n + m) for the two readings and the border table.

Solution

"""The same unit, already there — serialise both charts with blanks, then search."""

from collections import deque

BLANK = "-"


class Unit:
    __slots__ = ("headcount", "left", "right")

    def __init__(self, headcount):
        self.headcount = headcount
        self.left = None
        self.right = None


def build(rows):
    """Level-order chart, None where a unit has no sub-unit on that side."""
    if not rows or rows[0] is None:
        return None
    root = Unit(rows[0])
    queue = deque([root])
    i = 1
    while queue and i < len(rows):
        node = queue.popleft()
        if i < len(rows):
            head = rows[i]
            i += 1
            if head is not None:
                node.left = Unit(head)
                queue.append(node.left)
        if i < len(rows):
            head = rows[i]
            i += 1
            if head is not None:
                node.right = Unit(head)
                queue.append(node.right)
    return root


def serialise(root):
    """Preorder tokens, one BLANK written for every sub-unit that is not there.

    Writing the blanks is what makes the reading faithful: without them the unit
    with one junior on the left and the unit with one junior on the right read
    the same. With them, every whole unit is one unbroken run of tokens.
    """
    tokens = []
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            tokens.append(BLANK)
            continue
        tokens.append(node.headcount)
        stack.append(node.right)        # pushed first, so the left run comes out first
        stack.append(node.left)
    return tokens


def contains(chart, unit):
    """Knuth-Morris-Pratt over token lists: is `unit` an unbroken run of `chart`?"""
    m = len(unit)
    if m > len(chart):
        return False
    # border[i] = length of the longest proper prefix of unit[:i+1] that is also
    # its suffix, which is how far back a mismatch may fall instead of restarting.
    border = [0] * m
    k = 0
    for i in range(1, m):
        while k and unit[i] != unit[k]:
            k = border[k - 1]
        if unit[i] == unit[k]:
            k += 1
        border[i] = k
    k = 0
    for token in chart:
        while k and token != unit[k]:
            k = border[k - 1]
        if token == unit[k]:
            k += 1
            if k == m:
                return True
    return False


def solve(chart, unit):
    return contains(serialise(build(chart)), serialise(build(unit)))

TESTS = [
    (([12, 5, 9, 2, 7], [5, 2, 7]), True),
    (([12, 5, 9, 2, 7, None, None, 1], [5, 2, 7]), False),
    (([12, 5, 9, 2, 7], [12, 5, 9, 2, 7]), True),
    (([12, 5, 9, 2, 7], [5, 7, 2]), False),
    (([3, 4, 5], [3]), False),
    (([3, 4, 5], [4]), True),
    (([2, None, 2, None, 2], [2, None, 2]), True),
    (([5, None, 2], [5, 2]), False),
    (([1, 12, 3], [2]), False),
    (([], [4]), False),
]

Pitfalls

• Joining the tokens into a string with no separator. Headcount 2 then hides inside headcount 12, and "12-5" contains "2-5": the search finds a unit nobody drew. Compare token by token, or write a delimiter after every number.
• Leaving the blanks out of the reading. With chart = [5, None, 2] and unit = [5, 2] both read as 5 2, so the answer comes back True for a unit whose one sub-unit is on the other side.
• Stopping the comparison when the proposal runs out. That accepts the second example: it matches 5, 2 and 7 and never notices the team of 1 hanging under the 2.

Variants

• Parterre mirror — the same paired comparison of two structures, run once rather than at every node.
• Counting clearance charts — shape again, counted rather than searched for.