Problem Description

You are given a binary array bits that consists of only 0s and 1s, and this array always ends with a 0.

There are two types of special characters that can be encoded in this binary array:

• A one-bit character: represented by a single 0
• A two-bit character: represented by either 10 or 11

Your task is to determine whether the last character in the encoded sequence must be a one-bit character (a single 0).

For example:

• If bits = [1, 0, 0], the array can be decoded as [10, 0] where 10 is a two-bit character and 0 is a one-bit character. The last character is a one-bit character, so return true.
• If bits = [1, 1, 1, 0], the array can be decoded as [11, 10] where both are two-bit characters. The last character is not a one-bit character, so return false.

The key insight is that when we encounter a 1, it must be the start of a two-bit character (either 10 or 11), so we need to skip the next bit. When we encounter a 0, it represents a complete one-bit character. By traversing the array and correctly identifying characters, we can determine if the final 0 stands alone as a one-bit character or is part of a two-bit character.

Intuition

The key observation is that we need to parse the binary array from left to right to understand how the bits group into characters. Since we know the encoding rules:

• 0 forms a one-bit character
• 10 or 11 forms a two-bit character

We notice that whenever we see a 1, it must be the start of a two-bit character (since there's no valid character starting with 1 that is only one bit). This means when we encounter a 1, we must consume the next bit as well, regardless of whether it's 0 or 1.

When we see a 0, it's a complete one-bit character by itself, so we only move forward by one position.

The clever insight is that we can traverse the array using this rule:

• If the current bit is 0, move forward by 1 position
• If the current bit is 1, move forward by 2 positions

This can be simplified to: move forward by bits[i] + 1 positions, since when bits[i] = 0, we move by 0 + 1 = 1, and when bits[i] = 1, we move by 1 + 1 = 2.

By doing this traversal, we're essentially "consuming" characters one by one. If we land exactly at position n - 1 (the last index), it means the last 0 forms its own one-bit character. If we skip over n - 1 and land at n, it means the last 0 was part of a two-bit character that started at position n - 2.

This greedy approach works because there's only one valid way to parse the array - we must process characters from left to right, and the rules for identifying character boundaries are deterministic.

Solution Approach

The implementation uses a simple linear traversal with a pointer-based approach:

1. Initialize variables: Start with index i = 0 and get the length of the array n = len(bits).

2. Traverse the array: Use a while loop that continues as long as i < n - 1. We stop before the last element because we want to determine if we land exactly on the last position or skip over it.

3. Character consumption logic: Inside the loop, we use the formula i += bits[i] + 1:

   • When bits[i] = 0: We have a one-bit character, so we move forward by 0 + 1 = 1 position
   • When bits[i] = 1: We have a two-bit character, so we move forward by 1 + 1 = 2 positions

4. Final check: After the loop ends, we check if i == n - 1:

   • If i == n - 1: We landed exactly on the last position, meaning the last 0 is a standalone one-bit character, so return true
   • If i == n: We skipped over the last position (from n - 2 to n), meaning the last two bits form a two-bit character, so return false

Example walkthrough with bits = [1, 0, 0]:

• Start: i = 0, n = 3
• Iteration 1: bits[0] = 1, so i = 0 + 1 + 1 = 2
• Loop ends since i = 2 is not less than n - 1 = 2
• Check: i = 2 equals n - 1 = 2, so return true

Example walkthrough with bits = [1, 1, 1, 0]:

• Start: i = 0, n = 4
• Iteration 1: bits[0] = 1, so i = 0 + 1 + 1 = 2
• Iteration 2: bits[2] = 1, so i = 2 + 1 + 1 = 4
• Loop ends since i = 4 is not less than n - 1 = 3
• Check: i = 4 does not equal n - 1 = 3, so return false

The time complexity is O(n) where n is the length of the array, as we traverse the array at most once. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with bits = [1, 1, 0, 1, 0]:

Initial Setup:

• i = 0 (starting position)
• n = 5 (array length)
• We'll traverse until i < n - 1 (i.e., i < 4)

Step-by-step traversal:

Step 1: i = 0

• Current bit: bits[0] = 1
• This must be the start of a two-bit character
• Move forward by: bits[0] + 1 = 1 + 1 = 2 positions
• New position: i = 0 + 2 = 2
• Characters identified so far: [11] (consumed bits at positions 0 and 1)

Step 2: i = 2

• Current bit: bits[2] = 0
• This is a one-bit character
• Move forward by: bits[2] + 1 = 0 + 1 = 1 position
• New position: i = 2 + 1 = 3
• Characters identified so far: [11, 0] (consumed bit at position 2)

Step 3: i = 3

• Current bit: bits[3] = 1
• This must be the start of a two-bit character
• Move forward by: bits[3] + 1 = 1 + 1 = 2 positions
• New position: i = 3 + 2 = 5
• Characters identified so far: [11, 0, 10] (consumed bits at positions 3 and 4)

Loop termination:

• Loop ends because i = 5 is not less than n - 1 = 4

Final check:

• Is i == n - 1? Check if 5 == 4? No.
• Since i = 5 (which equals n), we skipped over the last position
• This means the last 0 at position 4 was part of the two-bit character 10 that started at position 3
• Return: false

The array was decoded as [11, 0, 10], where the last character is a two-bit character, not a one-bit character.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the bits array. The algorithm uses a single while loop that traverses through the array. In each iteration, the pointer i advances by either 1 or 2 positions (depending on bits[i] value). In the worst case, when all bits are 0, the pointer advances one position at a time, requiring at most n-1 iterations. In the best case, when bits alternate optimally, the pointer might skip positions, but it still visits each position at most once. Therefore, the time complexity is linear.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables i and n, regardless of the input size. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Processing the Entire Array

The Mistake: Many developers instinctively write a loop that processes every element in the array:

# INCORRECT approach
def isOneBitCharacter(self, bits: List[int]) -> bool:
    i = 0
    while i < len(bits):  # Processing ALL elements
        if bits[i] == 0:
            i += 1
        else:
            i += 2
    # Now what? How do we know if the last bit was standalone?

Why It's Wrong: Once you've consumed all bits, you lose the information about whether the last 0 was processed as a standalone one-bit character or as part of a two-bit character. You can't determine the answer after processing everything.

The Solution: Stop processing before the last element (i < len(bits) - 1), then check where your pointer landed. This preserves the crucial information about how the last bit should be interpreted.

Pitfall 2: Overthinking with Flag Variables

The Mistake: Trying to track the "type" of the last processed character using additional variables:

# OVERLY COMPLEX approach
def isOneBitCharacter(self, bits: List[int]) -> bool:
    i = 0
    last_was_one_bit = False
    while i < len(bits):
        if bits[i] == 0:
            last_was_one_bit = True
            i += 1
        else:
            last_was_one_bit = False
            i += 2
    return last_was_one_bit

Why It's Problematic:

• Adds unnecessary complexity and state management
• More prone to bugs when handling edge cases
• Harder to reason about correctness

The Solution: The elegant approach relies on pointer positioning alone. By stopping before the last element and checking if i == len(bits) - 1, you naturally determine whether the last bit is standalone without any extra bookkeeping.

Pitfall 3: Misunderstanding the Two-Bit Character Rule

The Mistake: Assuming you need to check what comes after a 1 to validate if it forms a valid two-bit character:

# UNNECESSARY validation
def isOneBitCharacter(self, bits: List[int]) -> bool:
    i = 0
    while i < len(bits) - 1:
        if bits[i] == 1:
            # Checking if next bit exists and forms valid 10 or 11
            if i + 1 < len(bits) and bits[i + 1] in [0, 1]:
                i += 2
            else:
                return False  # Invalid encoding?
        else:
            i += 1
    return i == len(bits) - 1

Why It's Wrong: The problem guarantees that the input is a valid encoding. When you see a 1, it's guaranteed to be the start of a valid two-bit character (10 or 11). The next bit is guaranteed to exist and be valid.

The Solution: Trust the problem constraints. When you encounter a 1, simply skip two positions without validation. This simplifies the code and avoids unnecessary checks.