1-bit and 2-bit Characters — Solution in Python, Java & C++
1-bit and 2-bit Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.
1-bit and 2-bit Characters is an easy coding problem on arrays, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A code has two kinds of characters: a one-bit character written as 0, and two-bit characters written as 10 or 11.
You are given a bit array bits that ends with 0 and is a valid encoding of some text. Return true if its last character must be a one-bit character, and false otherwise.
Example 1
Input: bits = [1,1,0]
Output: true
Explanation: It decodes as `11` then `0`.
Example 2
Input: bits = [0,1,0]
Output: false
Explanation: It decodes as `0` then `10` — the final `0` belongs to a two-bit character.
Example 3
Input: bits = [0]
Output: true
Constraints
1 <= bits.length <= 1000bits[i] is either 0 or 1bits[bits.length - 1] == 0
Hints for 1-bit and 2-bit Characters
Hint 1
Decoding from the left is unambiguous: a
0is always a whole character, and a1always starts a two-bit character that swallows the next bit.Hint 2
Walk with an index: step 1 on a
0, step 2 on a1. Where does the walk land just before the end?Hint 3
The last character is one bit exactly when the walk lands on index
n - 1.
How to solve 1-bit and 2-bit Characters
The encoding is prefix-free, so a single left-to-right walk decodes it. The question is only whether some character starts at the final index.
Approach
- Set
i = 0. - While
i < n - 1: advanceibybits[i] + 1(1 for a0, 2 for a1). - Return
i == n - 1.
Why it works
At every step i is the start of a character, because 0 is a complete character and 1 must begin a two-bit one. The loop stops when i reaches n - 1 (a character starts at the last bit, and since it is 0, that character is one bit) or n (the last bit was the second half of a two-bit character).
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Looking only at
bits[n - 2]is wrong:[1,1,0]has a1there but the answer istrue. - An equivalent shortcut counts the run of
1s just before the last0: an even count meanstrue.
Reference solution
Python
from typing import List
def isOneBitCharacter(bits: List[int]) -> bool:
i, n = 0, len(bits)
while i < n - 1:
i += bits[i] + 1
return i == n - 1Java
public static boolean isOneBitCharacter(int[] bits) {
int i = 0, n = bits.length;
while (i < n - 1) i += bits[i] + 1;
return i == n - 1;
}C++
bool isOneBitCharacter(vector<int>& bits) {
int i = 0, n = bits.size();
while (i < n - 1) i += bits[i] + 1;
return i == n - 1;
}JavaScript
var isOneBitCharacter = function(bits) {
var i = 0, n = bits.length;
while (i < n - 1) i += bits[i] + 1;
return i === n - 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays