Given a binary array bits that ends with 0, determine whether the last character must be a 1-bit character.

  • A 1-bit character is 0
  • A 2-bit character is 10 or 11

Parse from left to right and check whether the final 0 stands alone as a 1-bit character.

Examples

Example 1:

Input: bits = [1,0,0]
Output: true
Explanation: Parse "10" then the final "0" is a lone 1-bit character.

Example 2:

Input: bits = [1,1,1,0]
Output: false
Explanation: Parse "11" then "10" — the final 0 is part of a 2-bit character.

Constraints

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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Thinking Process

Simulate parsing without building characters:

  • From index i, if bits[i] == 1, the next two bits form one character → advance by 2
  • If bits[i] == 0, advance by 1
  • Stop before the last index (i < n - 1) so we can tell whether the final bit is consumed as part of a pair

If we land exactly on n - 1, the last 0 was never paired → true. If we reach n, the last 0 was consumed as the second bit of 10 → false.

Array + hash map 2 7 11 map hash map for O(1) lookups

Solution — O(n) time, O(1) space

class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        n = len(bits)
        i = 0
        # Parse until we reach or pass the last index
        while i < n - 1:
            i += 2 if bits[i] == 1 else 1
            return i == n - 1

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: Simulate parsing without building characters:

How the code works:

  • From index i, if bits[i] == 1, the next two bits form one character → advance by 2
  • If bits[i] == 0, advance by 1
  • Stop before the last index (i < n - 1) so we can tell whether the final bit is consumed as part of a pair

Walkthrough — input bits = [1,0,0], expected output true:

Parse “10” then the final “0” is a lone 1-bit character.

Time: O(n) · Space: O(1)

Common Mistakes

  • Looping while i < n instead of i < n - 1 — can overshoot and misread the last character
  • Treating 1 as a standalone 1-bit character (only 0 is 1-bit)
  • Not using the guarantee that the array ends in 0

Key Takeaways

  • Greedy linear scan with a variable step size (+1 or +2) handles encoding rules without explicit decoding
  • The loop bound i < n - 1 is the key insight — same pattern appears in string decoding problems

References

Template Reference