009. Split on Sentinels

Why this mechanism works

The active group is not final until a separator arrives. Empty groups should never be committed. Allocating a fresh active list after appending also prevents later mutation from changing an already committed group through aliasing.

State and boundaries

current contains the uncommitted integer run. groups contains completed nonempty runs.

Protocol

1. Start an empty current group.
2. Append integers to it.
3. On None, commit only if current is nonempty.
4. Replace current with a fresh list.
5. Flush a nonempty final group.

Visualization

1 2 | 3 | | 4
[1,2] [3]  [4]
empty interval: no group

Python implementation

def split_sentinels(values):
    groups, current = [], []
    for value in values:
        if value is None:
            if current:
                groups.append(current)
                current = []
        else:
            current.append(value)
    if current:
        groups.append(current)
    return groups

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 split_sentinels: groups, current = [], []
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[]

L3 split_sentinels: for value in values:
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[]; value=1

L9 split_sentinels: current.append(value)
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[1]; value=1

L3 split_sentinels: for value in values:
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[1]; value=2

L9 split_sentinels: current.append(value)
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[1, 2]; value=2

L3 split_sentinels: for value in values:
values=[1, 2, None, 3, None, None, 4]; groups=[]; current=[1, 2]; value=None

L6 split_sentinels: groups.append(current)
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2]]; current=[1, 2]; value=None

L7 split_sentinels: current = []
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2]]; current=[]; value=None

... 4 intermediate state changes omitted ...

L7 split_sentinels: current = []
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2], [3]]; current=[]; value=None

L3 split_sentinels: for value in values:
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2], [3]]; current=[]; value=4

L9 split_sentinels: current.append(value)
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2], [3]]; current=[4]; value=4

L11 split_sentinels: groups.append(current)
values=[1, 2, None, 3, None, None, 4]; groups=[[1, 2], [3], [4]]; current=[4]; value=4

L2 split_sentinels: groups, current = [], []
values=[None, None]; groups=[]; current=[]

L3 split_sentinels: for value in values:
values=[None, None]; groups=[]; current=[]; value=None

Why the solution is correct

Each integer is appended to the only group compatible with its location between sentinels. A separator closes that group, while repeated separators add nothing. The final flush completes the last segment, preserving all data without empty groups.

Time and space

O(n) time and O(n) returned storage; all non-sentinel values are copied once.

Common mistakes

Using if value treats zero as a separator. Clearing the same list after appending it would also empty the stored group.

Reasoning card

Transfer exercise

Generalize the separator to a predicate while preserving the no-empty-groups contract.