LeetCode 717: 1-bit and 2-bit Characters

Problem Restatement

We are given a binary array:

bits

The array encodes characters using two rules:

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

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:

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:

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.

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: