1161EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Weights on the Tips of First Slots

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 mobile hangs from a single top weight. Every weight holds at most two weights below it in a first and a second slot, and either slot may be empty. Each weight shows a number.

A flat list is read level by level: its first entry is the top weight'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.

A weight is a tip when both of its slots are empty. Return the total of the numbers on the tips that hang in a first slot.

Examples

Example 1

Input: mobile = [1, 2, 3, 4, 5, 6, 7]
Output: 10

The four weights at the bottom are the tips. Two of them hang in a first slot, showing 4 and 6, so the total is 10.

Example 2

Input: mobile = [1, null, 2]
Output: 0

The one weight below the top hangs in a second slot, so nothing counts.

Example 3

Input: mobile = [1, 2]
Output: 2

The single weight below the top hangs in a first slot with nothing under it.

Constraints

1 <= mobile.length <= 2000
The mobile holds between 1 and 1000 weights.
-1000 <= mobile[i] <= 1000
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 sum_of_left_leaves(mobile: list) -> int:

Java

public int sumOfLeftLeaves(Integer[] mobile)

The intended approach

Time O(n) over the weights.Space O(n) for the slot links.

Whether a weight counts depends on two separate things: which slot it hangs in, and whether anything hangs below it. A weight cannot see which slot it occupies, so the question is easier to ask from above. So read the flat list into slot links and then walk every weight, looking at what sits in its first slot. If that slot is filled and the weight in it has both its own slots empty, its number is added. Nothing else counts: a weight in a second slot never does, however bare it is, and a weight in a first slot with something hanging below it does not either. The top weight hangs in no slot at all, so it is never counted, which falls out for free from asking each weight about its own first slot rather than asking each weight about itself.

Pythonentry point: sum_of_left_leaves

def sum_of_left_leaves(mobile):

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

    total = 0
    for pos in order:
        child = left.get(pos)
        if child is not None:
            if left.get(child) is None and right.get(child) is None:
                total += mobile[child]
    return total

The obvious version

Walk down from the top carrying a flag saying whether the current weight was reached through a first slot. On reaching a weight with both slots empty, add its number when the flag is raised. Costs one walk with the flag dragged along rather than a look at each weight's own first slot.

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_sum_of_left_leaves(mobile):

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

    total = 0
    stack = [(0, False)]
    while stack:
        pos, first = stack.pop()
        lo = left.get(pos)
        ro = right.get(pos)
        if lo is None and ro is None:
            if first:
                total += mobile[pos]
            continue
        if lo is not None:
            stack.append((lo, True))
        if ro is not None:
            stack.append((ro, False))
    return total

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