1113MediumTreeBreadth-First SearchBinary Tree

Is the Tower Tidy

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tower hangs from a single top tile. Every tile holds at most two tiles below it in a first and a second slot, and either slot may be empty. Each tile shows a number.

A flat list is read level by level: its first entry is the top tile's number, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.

Number the rows of tiles from 0 at the top. The tower is tidy when both of the following hold:

Every tile on an even-numbered row shows an odd number, and read left to right the row strictly rises.
Every tile on an odd-numbered row shows an even number, and read left to right the row strictly falls.

Return true when the tower is tidy.

Examples

Example 1

Input: tower = [1, 4, 2]
Output: true

Row 0 holds the odd number 1. Row 1 holds 4 then 2, both even and falling, so the tower is tidy.

Example 2

Input: tower = [1, 2, 4]
Output: false

Row 1 holds 2 then 4. Both are even, but an odd-numbered row has to fall from left to right.

Example 3

Input: tower = [1, 4, 2, 3, 5, 7, 9]
Output: true

Row 0 holds 1, row 1 holds 4 then 2, and row 2 holds 3, 5, 7 and 9. The even rows rise through odd numbers and the odd row falls through even ones.

Constraints

1 <= tower.length <= 200000
The tower holds between 1 and 10^5 tiles.
1 <= tower[i] <= 10^6
The first entry of the list is not null.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_even_odd_tree(tower: list) -> bool:

Java

public boolean isEvenOddTree(Integer[] tower)

The intended approach

Time O(n) over the tiles.Space O(n) for the slot links and the widest row.

Both rules are about a whole row read left to right, so the tiles have to be gathered a row at a time. Read the flat list into slot links, then walk down from the top holding one row of tiles at a time: the next row is every filled slot of the current row, taken in order, which keeps the left-to-right reading intact. For each row, the row number decides which pair of rules applies. Carry the previous tile's number along and check two things per tile: that it is odd or even as the row demands, and that it stands strictly beyond the tile before it in the right direction. Both halves matter on their own. A row can rise while holding an even number, and a row can be all odd while standing still or falling, and either failing sinks the tower. Strictly means equal neighbours fail too, so the comparison has to reject a tie. Every tile is looked at once.

Pythonentry point: is_even_odd_tree

def is_even_odd_tree(tower):

    n = len(tower)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if tower[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if tower[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    row = [0]
    depth = 0
    while row:
        prev = None
        for pos in row:
            value = tower[pos]
            if depth % 2 == 0:
                if value % 2 == 0:
                    return False
                if prev is not None and value <= prev:
                    return False
            else:
                if value % 2 == 1:
                    return False
                if prev is not None and value >= prev:
                    return False
            prev = value
        nxt = []
        for pos in row:
            for child in (left.get(pos), right.get(pos)):
                if child is not None:
                    nxt.append(child)
        row = nxt
        depth += 1
    return True

The obvious version

Work out each tile's row number on its own and bucket the numbers by row, keeping the order the tiles were discovered in, which is left to right within a row. Then judge each bucket outright: check the odd or even demand across it, and compare it against a freshly sorted copy of itself, rising or falling as the row number asks, refusing any row that holds a repeat.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_even_odd_tree(tower):

    n = len(tower)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if tower[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if tower[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    rung = {0: 0}
    rows = {}
    for pos in order:
        depth = rung[pos]
        if depth not in rows:
            rows[depth] = []
        rows[depth].append(tower[pos])
        for child in (left.get(pos), right.get(pos)):
            if child is not None:
                rung[child] = depth + 1
    for depth in rows:
        values = rows[depth]
        if len(set(values)) != len(values):
            return False
        if depth % 2 == 0:
            for value in values:
                if value % 2 == 0:
                    return False
            if values != sorted(values):
                return False
        else:
            for value in values:
                if value % 2 == 1:
                    return False
            if values != sorted(values, reverse=True):
                return False
    return True

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in