Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The first bit of each character determines its length uniquely: zero consumes one bit and one consumes two. We can therefore decode greedily from the beginning. The final zero is a one-bit character exactly when decoding reaches it as the start of a character.

Approach

Start an index at zero and process character starts while the index is before the last position.
Advance by one for a zero and by two for a one, regardless of the second bit in the two-bit case.
Return whether the index stopped exactly at the final position. If it moved past that position, the last zero was consumed as part of 10. A single zero is accepted without entering the loop.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        i = 0

        while i < n - 1:
            if bits[i] == 0:
                i += 1
            else:
                i += 2

        return i == n - 1

Complexity analysis

The index advances by one or two positions and never moves backward, so the algorithm takes O(n) time and O(1) auxiliary space.