LeetCode 717 - 1-bit and 2-bit Characters

LeetCode Problem 717

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

In this problem, we are given a binary array called bits. The array represents a sequence of encoded characters using the following rules:

• A one-bit character is represented by a single 0
• A two-bit character is represented by either 10 or 11

The array is guaranteed to end with 0. Our task is to determine whether the final character in the decoding must be a one-bit character.

The important detail is that decoding must happen from left to right. Whenever we encounter:

• 0, it represents a complete one-bit character
• 1, it must combine with the next bit to form a two-bit character

We are not allowed to arbitrarily split bits. The encoding rules uniquely determine how the array is parsed.

For example, consider:

[1,0,0]

The first two bits, 10, form a two-bit character. The remaining 0 becomes a one-bit character. Therefore, the answer is true.

Now consider:

[1,1,1,0]

The first two bits, 11, form a two-bit character. The remaining 10 also form a two-bit character. The last 0 is consumed as part of that two-bit character, so the answer is false.

The constraints are small:

• 1 <= bits.length <= 1000
• Each value is either 0 or 1

Since the input size is modest, even a linear scan is more than sufficient.

There are several important edge cases to think about:

• A single-element array like [0]
• Arrays where every character before the end is a two-bit character
• Arrays containing long runs of 1s before the final 0
• Cases where the final 0 is part of a 10 or 11 pair

The problem guarantees that the encoding is valid and that the array always ends in 0, which simplifies the logic significantly.

Approaches

Brute Force Approach

A brute-force solution would explicitly decode the entire array into characters.

We would start from index 0 and repeatedly:

• If the current bit is 0, record a one-bit character and move forward by one position
• If the current bit is 1, record a two-bit character and move forward by two positions

At the end, we check whether the final decoded character was a one-bit character.

This approach is correct because it directly follows the encoding rules exactly as stated in the problem. Every character is decoded in order, so the result is guaranteed to match the intended interpretation.

However, this solution does more work than necessary because we do not actually need to store or construct the decoded characters. We only care about whether the last character is one-bit or two-bit.

Optimal Approach

The key observation is that we only need to simulate the traversal, not store the decoded result.

We can scan through the array using an index:

• If we see 0, move one step forward
• If we see 1, move two steps forward

We stop before the final position and determine whether we land exactly on the last index.

If the traversal reaches the last index directly, then the last character is a one-bit character.

If the traversal skips past the last index, then the final 0 was consumed as part of a two-bit character.

This works because the encoding is deterministic. At every position, the current bit uniquely determines how many positions must be consumed.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Explicitly decodes and stores characters
Optimal	O(n)	O(1)	Simulates decoding with index jumps

Algorithm Walkthrough

1. Initialize an index variable i to 0.
2. Continue processing while i is less than len(bits) - 1.

We intentionally stop before the final index because we want to determine whether that last bit stands alone or gets consumed by a two-bit character. 3. At each step, inspect bits[i].

• If bits[i] == 0, this represents a one-bit character, so increment i by 1.
• If bits[i] == 1, this must represent the start of a two-bit character, so increment i by 2.

4. After the loop finishes, check whether i == len(bits) - 1.

• If true, the traversal landed exactly on the final bit, meaning the last character is a one-bit character.
• Otherwise, the final bit was consumed as part of a two-bit character.

Why it works

The algorithm works because the encoding rules are deterministic. Every 0 consumes one position, and every 1 consumes two positions. By simulating this process exactly, the index always points to the start of the next undecoded character.

If the traversal stops exactly at the last index, then that final 0 has not been consumed yet and must represent a one-bit character. If the traversal passes beyond the last index, then the final 0 was already consumed as part of a two-bit character.

Python Solution

from typing import List

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        index = 0
        last_index = len(bits) - 1

        while index < last_index:
            if bits[index] == 0:
                index += 1
            else:
                index += 2

        return index == last_index

The implementation closely follows the algorithm described earlier.

We first compute last_index, which represents the final position in the array. This makes the comparisons easier to read and avoids repeatedly calling len(bits).

The while loop processes characters until we reach or pass the last position. Inside the loop:

• A 0 advances the pointer by one position because it represents a one-bit character.
• A 1 advances the pointer by two positions because it starts a two-bit character.

After decoding finishes, we return whether the pointer stopped exactly on the final index.

This solution does not allocate extra memory and only uses a few integer variables, making it very space efficient.

Go Solution

func isOneBitCharacter(bits []int) bool {
    index := 0
    lastIndex := len(bits) - 1

    for index < lastIndex {
        if bits[index] == 0 {
            index++
        } else {
            index += 2
        }
    }

    return index == lastIndex
}

The Go implementation mirrors the Python solution almost exactly.

Slices in Go already provide efficient indexed access, so no additional data structures are needed. Since the constraints are small and indices remain well within integer limits, there are no overflow concerns.

The logic remains identical:

• 0 advances by one position
• 1 advances by two positions
• The final comparison determines whether the last bit stands alone

Worked Examples

Example 1

bits = [1,0,0]

Step	Index	Current Bit	Action	Next Index
1	0	1	Two-bit character	2

The loop stops because index == last_index.

Final state:

index = 2
last_index = 2

Since the index lands exactly on the final position, the last character is one-bit.

Result:

true

Example 2

bits = [1,1,1,0]

Step	Index	Current Bit	Action	Next Index
1	0	1	Two-bit character	2
2	2	1	Two-bit character	4

The loop stops because index > last_index.

Final state:

index = 4
last_index = 3

The traversal skipped past the final position, meaning the last 0 was consumed by a two-bit character.

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each bit is visited at most once
Space	O(1)	Only a few integer variables are used

The algorithm runs in linear time because the index moves forward by either one or two positions during each iteration. No position is revisited.

The space complexity is constant because the algorithm does not allocate any additional data structures proportional to the input size.

Test Cases

sol = Solution()

assert sol.isOneBitCharacter([1, 0, 0]) == True      # standard valid one-bit ending
assert sol.isOneBitCharacter([1, 1, 1, 0]) == False # ending zero consumed by two-bit character
assert sol.isOneBitCharacter([0]) == True            # single one-bit character
assert sol.isOneBitCharacter([1, 0]) == False        # single two-bit character
assert sol.isOneBitCharacter([0, 0]) == True         # multiple one-bit characters
assert sol.isOneBitCharacter([1, 1, 0]) == True      # one two-bit character followed by one-bit
assert sol.isOneBitCharacter([1, 1, 1, 1, 0]) == False # chain of two-bit characters
assert sol.isOneBitCharacter([1, 0, 1, 0, 0]) == True  # mixed encoding ending in one-bit
assert sol.isOneBitCharacter([1, 0, 1, 1, 0]) == False # final zero belongs to two-bit character

Test	Why
[1,0,0]	Basic example with one-bit ending
[1,1,1,0]	Basic example where ending is two-bit
[0]	Smallest valid input
[1,0]	Single two-bit character
[0,0]	Consecutive one-bit characters
[1,1,0]	Mix of two-bit and one-bit
[1,1,1,1,0]	Long chain of two-bit characters
[1,0,1,0,0]	Alternating pattern ending in one-bit
[1,0,1,1,0]	Final zero consumed by two-bit character

Edge Cases

Single Element Array

An input like:

[0]

is the smallest possible valid input. A careless implementation might incorrectly attempt to read beyond the array bounds when checking for two-bit characters.

This implementation handles the case naturally because the loop condition index < last_index is immediately false. The algorithm directly returns True since the single 0 must be a one-bit character.

Final Zero Consumed by a Two-Bit Character

Consider:

[1,0]

The final 0 does not stand alone. Instead, it forms the two-bit character 10.

A buggy implementation might incorrectly assume that every array ending in 0 has a one-bit final character. Our traversal avoids this mistake because the index jumps by two positions after encountering the leading 1.

Consecutive Leading Ones

Inputs like:

[1,1,1,1,0]

can be tricky because several two-bit characters appear consecutively.

A naive solution might misalign the parsing boundaries. This implementation avoids ambiguity by strictly following the encoding rules from left to right. Every time a 1 is encountered, exactly two positions are consumed, guaranteeing correct alignment throughout the traversal.