1-bit and 2-bit Characters

main.md

Question

Approach

I scan the array from left to right. • If I see a 1, it must start a two-bit character, so I skip the next index (i += 2). • If I see a 0, it is a one-bit character, so I move one step (i += 1). At the end, if the pointer stops exactly at the last index, then the last character is a one-bit character.

Implementation

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

Complexities

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