1-bit and 2-bit Characters: Greedy Bit Scanning

May 22, 20265 min read

leetcodeproblemeasyarrays

LeetCode 717. 1-bit and 2-bit Characters gives you a binary array that always ends with 0 and asks: is the last character a 1-bit character? The trick is figuring out how the bits before it group together, because that determines whether the final 0 stands alone or belongs to a 2-bit character.

The problem

We have two special characters:

A 1-bit character represented by 0
A 2-bit character represented by 10 or 11

Given a binary array bits that always ends with 0, determine if the last character is a 1-bit character.

bits = [1, 0, 0]    -> true   (characters: "10" + "0", last is 1-bit)
bits = [1, 1, 1, 0] -> false  (characters: "11" + "10", last is 2-bit)

bits = [1, 0, 0] decodes as "10" (2-bit character) + "0" (1-bit character). The last character is 1-bit, so the answer is true.

The encoding is unambiguous. Whenever you see a 1, it must be the start of a 2-bit character (10 or 11). Whenever you see a 0 that is not the second bit of a 2-bit character, it is a complete 1-bit character on its own. This means you can decode the entire array from left to right without any backtracking.

The approach

Scan from left to right using a pointer i. At each position, look at bits[i]:

If bits[i] is 1, you are at the start of a 2-bit character. Skip two positions: i += 2.
If bits[i] is 0, you are at a 1-bit character. Skip one position: i += 1.

Stop the loop when i reaches or passes the last index. After the loop, check whether i landed exactly on the last position. If it did, the last 0 is a standalone 1-bit character. If i overshot (jumped past the last index), the final 0 was consumed as part of a 2-bit character.

This is a greedy approach. You do not need to try multiple groupings or use recursion. The encoding rules guarantee that scanning left to right always produces the unique valid decoding.

Practice greedy problems with spaced repetition

The solution

def isOneBitCharacter(bits):
    i = 0
    while i < len(bits) - 1:
        i += bits[i] + 1
    return i == len(bits) - 1

The expression bits[i] + 1 is a compact way to jump by the right amount. When bits[i] is 1, you jump by 2. When bits[i] is 0, you jump by 1. The loop runs while i is strictly before the last index, so you never accidentally read past the end.

Step-by-step walkthrough

Let's trace through bits = [1, 1, 1, 0]. The expected answer is false because the bits decode as "11" + "10", making the last 0 part of a 2-bit character.

Step 1: i = 0, bits[0] = 1 (start of a 2-bit character)

bits[0] is 1, so this starts a 2-bit character. Jump i += 2 to skip past both bits.

Step 2: i = 2, bits[2] = 1 (start of another 2-bit character)

bits[2] is 1, so another 2-bit character begins here. Jump i += 2 again.

Step 3: i = 4, loop ends (i is no longer less than len(bits) - 1)

The while loop condition i < len(bits) - 1 is false, so we stop. Check: i == 3? No, i == 4. We overshot the last index.

Result: i != 3, return false

i landed at 4, not at the last index (3). The last 0 was consumed as part of the 2-bit character "10". Answer: false.

The pointer jumped from 0 to 2 to 4. It never landed on index 3 (the last index), so the final 0 was not a standalone 1-bit character. The answer is false.

The key insight is that bits[i] + 1 encodes the jump size. A 1 always starts a 2-bit character, so you skip 2. A 0 is a complete 1-bit character, so you skip 1. You never need to look ahead or backtrack.

Complexity analysis

Approach	Time	Space
Greedy scan	O(n)	O(1)

Each element is visited at most once. The pointer only moves forward, and no extra data structures are needed.

The building blocks

Greedy scanning

The greedy pattern here is: make the locally determined choice at each step, and trust that it produces the globally correct answer. Because a 1 always starts a 2-bit character, there is never any ambiguity about how to decode the current position. You do not need dynamic programming, backtracking, or any form of look-ahead.

This same "scan forward, skip by a known amount" pattern appears in problems like Jump Game and interval-based problems. Whenever the input has unambiguous structure that you can decode left to right, a greedy scan is the right tool.

i = 0
while i < len(bits) - 1:
    i += bits[i] + 1

Once you internalize this pattern, you will recognize it instantly whenever a problem involves decoding a sequence with variable-length elements.

Edge cases

Single element [0]. The array contains only one 0. The while loop never runs because i (which is 0) is not less than len(bits) - 1 (also 0). The function returns i == 0, which is true. A lone 0 is always a 1-bit character.
All zeros [0, 0, 0]. Every element is a 1-bit character. The pointer advances one step at a time and lands exactly on the last index. Answer: true.
Starts with 0 followed by 10. For [0, 1, 0], the pointer goes 0 -> 1 -> 3. At index 0, bits[0] = 0 so i += 1. At index 1, bits[1] = 1 so i += 2, landing at 3. Since i == 3 and len(bits) - 1 == 2, we have i != 2, so the answer is false. The decoding is "0" + "10", and the last character is the 2-bit "10".
Two elements [1, 0]. The pointer starts at 0, bits[0] = 1, so i += 2. Now i = 2, which is not less than len(bits) - 1 = 1, so the loop ends. i == 1? No. Answer: false. The entire array is a single 2-bit character "10".
Long alternating pattern [1, 0, 1, 0, 0]. Decodes as "10" + "10" + "0". The pointer goes 0 -> 2 -> 4. i == 4 == len(bits) - 1? Yes. Answer: true.

Build greedy pattern intuition

From understanding to recall

The greedy scan for this problem is short, but that does not mean you will remember it under pressure. The subtle detail is the loop condition (i < len(bits) - 1 rather than i < len(bits)) and the final equality check. Miss either one and you get wrong answers on edge cases.

Spaced repetition locks in those details. You write the solution from scratch today, then again in two days, then a week later. Each time, the boundary condition and the bits[i] + 1 trick become more automatic. When you encounter a similar variable-length decoding problem in an interview, the pattern will surface without effort.

Number of 1 Bits - Another bit manipulation problem that requires careful iteration over individual bits
Single Number - Bit-level thinking with XOR, a different way to extract information from binary data
Counting Bits - Another problem requiring understanding of bit patterns and how they relate to each other

Start mastering greedy patterns today