LeetCode 717: 1-bit and 2-bit Characters

Problem Restatement

We are given a binary array:

bits

The array encodes characters using two rules:

Character Type	Encoding
One-bit character	0
Two-bit character	10 or 11

The array always ends with:

0

We need to determine whether the final character must be a one-bit character.

Return:

True

if the last character is one-bit.

Otherwise return:

False

Input and Output

Item	Meaning
Input	Binary array bits
Output	Whether the last character is one-bit
One-bit encoding	0
Two-bit encoding	10 or 11
Important detail	The array always ends with 0

The function shape is:

class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        ...

Examples

Example 1:

bits = [1, 0, 0]

Parse from left to right:

10 -> two-bit character
0  -> one-bit character

The final character is one-bit.

Output:

True

Example 2:

bits = [1, 1, 1, 0]

Parse from left to right:

11 -> two-bit character
10 -> two-bit character

The final 0 belongs to the last two-bit character.

So the final character is not one-bit.

Output:

False

First Thought: Try Every Parsing

A recursive approach could try every possible valid decoding.

At each index:

Current Bit	Possible Action
0	Take one-bit character
1	Take two-bit character

Then recursively check whether the final character is one-bit.

This works, but it is unnecessary.

The encoding rules already force a unique greedy parsing.

Key Insight

The encoding is deterministic.

Whenever we see:

0

it must represent a one-bit character.

Whenever we see:

1

it must begin a two-bit character, because there is no valid one-bit encoding starting with 1.

So:

Current Bit	Move
0	Advance by 1
1	Advance by 2

We only need to simulate decoding until we reach the last position.

If we land exactly on the final index, then the last character is one-bit.

If we jump past the final index, then the last 0 was consumed as part of a two-bit character.

Algorithm

1. Start with index i = 0.
2. While i < len(bits) - 1:
   • If bits[i] == 0, increment i by 1.
   • Otherwise increment i by 2.
3. Return whether:

   i == len(bits) - 1
   

Correctness

The encoding rules uniquely determine how to parse the array.

If bits[i] == 0, the current character must be the one-bit encoding 0, so advancing by one position is correct.

If bits[i] == 1, the current character must be either 10 or 11, both of which are two-bit encodings, so advancing by two positions is correct.

Therefore the algorithm always follows the only valid decoding path.

The loop stops before processing the final array position directly.

If the index ends exactly at the final position, then the final 0 begins its own one-bit character.

If the index jumps beyond the final position, then the final 0 was consumed as the second bit of a two-bit character.

Thus the algorithm returns True exactly when the last character is one-bit.

Complexity

Let n be the length of bits.

Metric	Value	Why
Time	O(n)	We scan the array once
Space	O(1)	Only one index variable is used

Implementation

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

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

        return i == last

Code Explanation

The variable:

last = len(bits) - 1

stores the final index.

We process characters from left to right:

while i < last:

If the current bit is 0, it represents a one-bit character:

if bits[i] == 0:
    i += 1

If the current bit is 1, it begins a two-bit character:

else:
    i += 2

After parsing finishes:

return i == last

means the last character stands alone as a one-bit character.

Example Walkthrough

Use:

bits = [1, 0, 0]

Initialize:

i = 0
last = 2

At index 0:

bits[0] = 1

So this begins a two-bit character:

10

Advance:

i = 2

Now:

i == last

So the final bit forms a one-bit character.

Return:

True

Now use:

bits = [1, 1, 1, 0]

At index 0:

11

Advance to:

i = 2

At index 2:

10

Advance to:

i = 4

Now:

i > last

So the final 0 was part of the two-bit character 10.

Return:

False

Alternative Observation

Another way to think about the problem:

The final 0 is one-bit if and only if the number of consecutive 1s immediately before it is even.

For example:

[1, 0, 0]

There is one 1 before the final 0.

Odd count means the previous 1 pairs with the earlier 0, leaving the last 0 alone.

But:

[1, 1, 1, 0]

There are three consecutive 1s before the final 0.

Odd count means the final 0 gets consumed by a two-bit character.

The greedy simulation is usually clearer and simpler.

Testing

def test_is_one_bit_character():
    s = Solution()

    assert s.isOneBitCharacter([1, 0, 0]) is True
    assert s.isOneBitCharacter([1, 1, 1, 0]) is False
    assert s.isOneBitCharacter([0]) is True
    assert s.isOneBitCharacter([1, 0]) is False
    assert s.isOneBitCharacter([0, 0]) is True
    assert s.isOneBitCharacter([1, 1, 0]) is True

    print("all tests passed")

test_is_one_bit_character()

Test coverage:

Test	Why
Standard true example	Confirms final standalone 0
Standard false example	Confirms final 0 consumed by two-bit character
Single 0	Smallest valid input
Single two-bit character	Confirms no standalone final character
Two one-bit characters	Confirms repeated one-bit parsing
Mixed encoding	Confirms greedy stepping works