1-bit and 2-bit Characters

Difficulty: Easy | Acceptance: 49.60% | Paid: No Topics: Array

We have two special characters:

The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

• Examples
• Constraints
• Linear Scan (Greedy)
• Count from End

Examples

Example 1

Input:

bits = [1,0,0]

Output:

true

Explanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2

Input:

bits = [1,1,1,0]

Output:

false

Explanation: The only way to decode it is two-bit character and two-bit character. So the last character is not one-bit character.

Constraints

1 <= bits.length <= 1000
bits[i] is either 0 or 1.

Linear Scan (Greedy)

Intuition Parse the array from left to right, consuming 1 bit for 0 and 2 bits for 1, then check if we land exactly on the last index.

Steps

• Initialize pointer at index 0
• While pointer is before the last element:
  • If current bit is 0, move pointer by 1 (1-bit character)
  • If current bit is 1, move pointer by 2 (2-bit character)
• Return true if pointer equals the last index

class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        i = 0
        n = len(bits)
        while i < n - 1:
            if bits[i] == 0:
                i += 1
            else:
                i += 2
        return i == n - 1

Complexity

• Time: O(n) - single pass through the array
• Space: O(1) - only using a pointer variable
• Notes: Simple and intuitive approach

Count from End

Intuition Count consecutive 1s before the last 0. If count is even, last 0 is a 1-bit character; if odd, it pairs with a preceding 1.

Steps

• Start from second-to-last element and move backward
• Count consecutive 1s until hitting a 0
• Return true if count is even, false if odd

class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        n = len(bits)
        ones = 0
        for i in range(n - 2, -1, -1):
            if bits[i] == 1:
                ones += 1
            else:
                break
        return ones % 2 == 0

Complexity

• Time: O(n) - worst case scans entire array
• Space: O(1) - only using a counter
• Notes: Elegant mathematical insight; often faster in practice as it may exit early