# LeetCode 717: 1-bit and 2-bit Characters

## Problem Restatement

We are given a binary array:

```python
bits
```

The array encodes characters using two rules:

| Character Type | Encoding |
|---|---|
| One-bit character | `0` |
| Two-bit character | `10` or `11` |

The array always ends with:

```python
0
```

We need to determine whether the final character must be a one-bit character.

Return:

```python
True
```

if the last character is one-bit.

Otherwise return:

```python
False
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary array `bits` |
| Output | Whether the last character is one-bit |
| One-bit encoding | `0` |
| Two-bit encoding | `10` or `11` |
| Important detail | The array always ends with `0` |

The function shape is:

```python
class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        ...
```

## Examples

Example 1:

```python
bits = [1, 0, 0]
```

Parse from left to right:

```python
10 -> two-bit character
0  -> one-bit character
```

The final character is one-bit.

Output:

```python
True
```

Example 2:

```python
bits = [1, 1, 1, 0]
```

Parse from left to right:

```python
11 -> two-bit character
10 -> two-bit character
```

The final `0` belongs to the last two-bit character.

So the final character is not one-bit.

Output:

```python
False
```

## First Thought: Try Every Parsing

A recursive approach could try every possible valid decoding.

At each index:

| Current Bit | Possible Action |
|---|---|
| `0` | Take one-bit character |
| `1` | Take two-bit character |

Then recursively check whether the final character is one-bit.

This works, but it is unnecessary.

The encoding rules already force a unique greedy parsing.

## Key Insight

The encoding is deterministic.

Whenever we see:

```python
0
```

it must represent a one-bit character.

Whenever we see:

```python
1
```

it must begin a two-bit character, because there is no valid one-bit encoding starting with `1`.

So:

| Current Bit | Move |
|---|---|
| `0` | Advance by `1` |
| `1` | Advance by `2` |

We only need to simulate decoding until we reach the last position.

If we land exactly on the final index, then the last character is one-bit.

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

## Algorithm

1. Start with index `i = 0`.
2. While `i < len(bits) - 1`:
   - If `bits[i] == 0`, increment `i` by `1`.
   - Otherwise increment `i` by `2`.
3. Return whether:
   ```python
   i == len(bits) - 1
   ```

## Correctness

The encoding rules uniquely determine how to parse the array.

If `bits[i] == 0`, the current character must be the one-bit encoding `0`, so advancing by one position is correct.

If `bits[i] == 1`, the current character must be either `10` or `11`, both of which are two-bit encodings, so advancing by two positions is correct.

Therefore the algorithm always follows the only valid decoding path.

The loop stops before processing the final array position directly.

If the index ends exactly at the final position, then the final `0` begins its own one-bit character.

If the index jumps beyond the final position, then the final `0` was consumed as the second bit of a two-bit character.

Thus the algorithm returns `True` exactly when the last character is one-bit.

## Complexity

Let `n` be the length of `bits`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only one index variable is used |

## Implementation

```python
class Solution:
    def isOneBitCharacter(self, bits: list[int]) -> bool:
        i = 0
        last = len(bits) - 1

        while i < last:
            if bits[i] == 0:
                i += 1
            else:
                i += 2

        return i == last
```

## Code Explanation

The variable:

```python
last = len(bits) - 1
```

stores the final index.

We process characters from left to right:

```python
while i < last:
```

If the current bit is `0`, it represents a one-bit character:

```python
if bits[i] == 0:
    i += 1
```

If the current bit is `1`, it begins a two-bit character:

```python
else:
    i += 2
```

After parsing finishes:

```python
return i == last
```

means the last character stands alone as a one-bit character.

## Example Walkthrough

Use:

```python
bits = [1, 0, 0]
```

Initialize:

```python
i = 0
last = 2
```

At index `0`:

```python
bits[0] = 1
```

So this begins a two-bit character:

```python
10
```

Advance:

```python
i = 2
```

Now:

```python
i == last
```

So the final bit forms a one-bit character.

Return:

```python
True
```

Now use:

```python
bits = [1, 1, 1, 0]
```

At index `0`:

```python
11
```

Advance to:

```python
i = 2
```

At index `2`:

```python
10
```

Advance to:

```python
i = 4
```

Now:

```python
i > last
```

So the final `0` was part of the two-bit character `10`.

Return:

```python
False
```

## Alternative Observation

Another way to think about the problem:

The final `0` is one-bit if and only if the number of consecutive `1`s immediately before it is even.

For example:

```python
[1, 0, 0]
```

There is one `1` before the final `0`.

Odd count means the previous `1` pairs with the earlier `0`, leaving the last `0` alone.

But:

```python
[1, 1, 1, 0]
```

There are three consecutive `1`s before the final `0`.

Odd count means the final `0` gets consumed by a two-bit character.

The greedy simulation is usually clearer and simpler.

## Testing

```python
def test_is_one_bit_character():
    s = Solution()

    assert s.isOneBitCharacter([1, 0, 0]) is True
    assert s.isOneBitCharacter([1, 1, 1, 0]) is False
    assert s.isOneBitCharacter([0]) is True
    assert s.isOneBitCharacter([1, 0]) is False
    assert s.isOneBitCharacter([0, 0]) is True
    assert s.isOneBitCharacter([1, 1, 0]) is True

    print("all tests passed")

test_is_one_bit_character()
```

Test coverage:

| Test | Why |
|---|---|
| Standard true example | Confirms final standalone `0` |
| Standard false example | Confirms final `0` consumed by two-bit character |
| Single `0` | Smallest valid input |
| Single two-bit character | Confirms no standalone final character |
| Two one-bit characters | Confirms repeated one-bit parsing |
| Mixed encoding | Confirms greedy stepping works |