Problem Statement in English

You’re given a binary array bits which represents a sequence of characters. The characters can be either:

  • A 1-bit character, represented by a single 0.
  • A 2-bit character, represented by either 10 or 11.

The array bits always ends with a 0, which is guaranteed to be a 1-bit character.

Your task is to determine if the last character in the array is indeed a 1-bit character.

Approach

Since if we encounter a 1, we know that the next bit is part of a 2-bit character, we can use a pointer to traverse the array.

If we end up at the last index, it means the last character is a 1-bit character. If we skip over it, then it’s part of a 2-bit character.

Solution in Python


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

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

        return i == N - 1

Complexity

  • Time: $O(n)$
    We traverse the list of bits once.

  • Space: $O(1)$
    Since we use only a constant amount of extra space.

Mistakes I Made

I used a stack instead of the the pointer technique and overcomplicated it 🤦‍♂️

And we are done.