Skip to main content
Talentd

1-bit and 2-bit Characters - Solution & Explanation

EasyArray16 min readAsked at: Google, Bloomberg, Ixl +1
Practice this problem

Problem Statement

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.

 

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.

Approach Overview

Problem Overview: You are given a binary array where characters are encoded using either 0 (a 1‑bit character) or 10/11 (a 2‑bit character). The array always ends with 0. The task is to determine whether the last character must be a 1‑bit character after decoding the sequence.

Approach 1: Traversal and Check (O(n) time, O(1) space)

Scan the array from left to right using an index pointer. If the current bit is 0, it represents a 1‑bit character, so move the pointer forward by one position. If the current bit is 1, it starts a 2‑bit character (10 or 11), so skip two positions. Continue this process until you reach the end of the array. The key insight: if the pointer lands exactly on the last index, the last character is a 1‑bit character; if the pointer jumps past it, the last 0 was consumed as part of a 2‑bit character. This greedy traversal works because each encoding pattern has a fixed length. The array is processed once, giving O(n) time and constant O(1) space. Since the problem operates directly on a binary array, no additional data structures are needed.

Approach 2: Reverse Traversal (O(n) time, O(1) space)

Instead of simulating decoding from the start, examine the pattern before the last 0. Move backward from the second‑to‑last index and count how many consecutive 1s appear before that final zero. If the count of consecutive ones is even, the last 0 stands alone as a 1‑bit character. If the count is odd, the last 0 must pair with the preceding 1 to form a 2‑bit character. This works because every 2‑bit encoding begins with 1, and pairs of bits determine whether the final zero gets grouped. The algorithm performs a single backward pass over part of the array, resulting in O(n) time and O(1) space. This approach is common in array scanning problems and resembles simple greedy reasoning about local patterns.

Recommended for interviews: The forward traversal approach is the one most interviewers expect. It directly simulates the decoding process and is easy to reason about during a whiteboard explanation. The reverse traversal trick is a neat optimization insight and demonstrates deeper pattern recognition. Showing the straightforward traversal first proves you understand the encoding rules, while mentioning the reverse counting method shows stronger problem‑solving depth.

Approach 1: Approach 1: Traversal and Check

This approach involves traversing the bit array to simulate decoding according to the rules. If a '0' is encountered, it signifies a one-bit character so you move one step forward. If a '1' is encountered, it indicates the start of a two-bit character ('10' or '11'), so you move two steps forward. The ultimate goal is to check whether the last character is reached after processing all bits, and it must land on a one-bit character.

The solution uses a simple loop to traverse through the array. When the loop reaches the second-to-last index, it checks if the last index can be reached with a one-bit character.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the bits array.
Space Complexity: O(1), as we are not using any extra space.

Try this approach in the editor →

Approach 2: Approach 2: Reverse Traversal

This approach involves reverse traversal, where we start checking bits from the end to see if the trailing '0' can be interpreted as a single one-bit character. Specifically, we count the number of continuous '1's preceding the last '0'. Based on whether this count is even or odd, we determine if the last character is a one-bit character (odd -> last is a part of an incomplete two-bit sequence, thus false; even -> last is a single-bit, thus true).

This C implementation calculates the number of continuous '1's from the second last element backwards and determines whether it is even or odd to decide if the last bit is a one-bit character.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), in the worst-case scenario where most bits are '1'.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Direct Traversal

We can directly traverse the first n-1 elements of the array bits, and each time decide how many elements to skip based on the value of the current element:

  • If the current element is 0, skip 1 element (representing a one-bit character);
  • If the current element is 1, skip 2 elements (representing a two-bit character).

When the traversal ends, if the current index equals n-1, it means the last character is a one-bit character, and we return true; otherwise, return false.

The time complexity is O(n), where n is the length of the array bits. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Traversal and Check

Time Complexity: O(n), where n is the length of the bits array.
Space Complexity: O(1), as we are not using any extra space.

Approach 2: Reverse Traversal

Time Complexity: O(n), in the worst-case scenario where most bits are '1'.
Space Complexity: O(1).

Direct Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Traversal and CheckO(n)O(1)Best general solution. Easy to explain in interviews and directly simulates decoding.
Reverse TraversalO(n)O(1)Useful when reasoning from the end of the array or identifying patterns in consecutive bits.

Video Solution

1-bit and 2-bit Characters | 2 Ways | Easy | Leetcode 717 | codestorywithMIK • codestorywithMIK • 5,003 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is 1-bit and 2-bit Characters easy or hard?
LeetCode classifies this problem as Easy. The logic is straightforward once you recognize that 1 starts a two-bit character and 0 stands alone. The challenge mainly involves correctly simulating the traversal and handling the final element check.
1-bit and 2-bit Characters Python/Java solution
In Python or Java, implement a loop with an index variable. Increment the index by 1 if the current element is 0, otherwise increment by 2. After the loop finishes, check whether the index stopped exactly at the last element to determine if it represents a 1-bit character.
How to solve 1-bit and 2-bit Characters in O(n)?
Traverse the array with an index pointer. When you see a 0, move one step; when you see a 1, skip the next bit because it forms a 2-bit character. Continue until reaching the end. If the pointer lands exactly on the final index, the last character is a 1-bit character.
What is the best approach for 1-bit and 2-bit Characters?
The traversal and check approach is the most common solution. Iterate through the array and move one step for a 0 (1-bit character) or two steps for a 1 (start of a 2-bit character). If the pointer ends exactly on the last index, the last character is a 1-bit character. This runs in O(n) time with O(1) space.
Is 1-bit and 2-bit Characters asked at Google/Amazon/Meta?
Problems involving binary encoding patterns and array traversal appear frequently in interviews at companies like Google, Amazon, and Meta. This specific problem is commonly used in coding practice platforms to test array scanning logic and greedy reasoning.
What data structure is used in 1-bit and 2-bit Characters?
The problem primarily uses a simple array of integers representing bits. The algorithm relies on sequential traversal and pointer movement rather than additional data structures such as hash maps or stacks.
What is the time complexity of 1-bit and 2-bit Characters?
The optimal solutions run in O(n) time because the array is scanned once. Each step either advances the pointer by one or two positions. Space complexity remains O(1) since the algorithm uses only a few variables and no additional data structures.

Ready to solve this problem?

Practice 1-bit and 2-bit Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Gray Code