Problem Description

The "1-bit and 2-bit Characters" problem asks you to determine whether the last character in a given binary array bits is a one-bit character or not. The encoding rules are:

• A character can be 1-bit: represented by 0.
• A character can be 2-bit: represented by 10 or 11.

• Each bit in the array is either 0 or 1.
• The array always ends with 0.
• There is always at least one valid way to decode the entire array.

Thought Process

To solve this problem, let's first understand the encoding:

• A 0 always represents a single 1-bit character.
• A 1 must be the start of a 2-bit character, and is always followed by another bit (10 or 11).

• Start at the beginning of the array.
• If we see a 0, move forward by 1 (it's a 1-bit character).
• If we see a 1, move forward by 2 (it's a 2-bit character).
• Repeat until we reach the last bit.

Solution Approach

Let's break down the steps for an efficient solution:

1. Initialize a pointer i at position 0.
2. Iterate through the array using i:
   • If bits[i] == 0, increment i by 1 (move to the next character).
   • If bits[i] == 1, increment i by 2 (skip the next bit, since it's part of a 2-bit character).
3. Continue this process until i reaches or passes the second-to-last element (len(bits) - 1), since the last character is always 0.
4. After the loop:
   • If i == len(bits) - 1, the last 0 is a 1-bit character (return True).
   • If i > len(bits) - 1, the last 0 was part of a 2-bit character (return False).

Example Walkthrough

Let's walk through an example with bits = [1, 0, 0]:

• Step 1: Start at i = 0. bits[0] = 1, so this is the start of a 2-bit character. Move i forward by 2 (i = 2).
• Step 2: Now i = 2. bits[2] = 0. Since i is at the last index, the last 0 is a standalone 1-bit character.
• Result: Return True.

• Step 1: i = 0, bits[0] = 1 → move to i = 2.
• Step 2: i = 2, bits[2] = 1 → move to i = 4 (past the last index).
• Result: Return False (the last 0 was consumed as part of a 2-bit character).

Code Implementation

class Solution:
    def isOneBitCharacter(self, bits):
        i = 0
        n = len(bits)
        while i < n - 1:
            if bits[i] == 1:
                i += 2
            else:
                i += 1
        return i == n - 1
      

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0, n = bits.size();
        while (i < n - 1) {
            if (bits[i] == 1) i += 2;
            else i += 1;
        }
        return i == n - 1;
    }
};
      

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0, n = bits.length;
        while (i < n - 1) {
            if (bits[i] == 1) i += 2;
            else i += 1;
        }
        return i == n - 1;
    }
}
      

var isOneBitCharacter = function(bits) {
    let i = 0, n = bits.length;
    while (i < n - 1) {
        if (bits[i] === 1) i += 2;
        else i += 1;
    }
    return i === n - 1;
};
      

Time and Space Complexity

Brute-force approach:

• Would involve trying every possible valid decoding, which is exponential in the worst case: O(2^n).

• We scan the array once, always moving forward by 1 or 2 steps. So, the time complexity is O(n), where n is the length of the input array.
• No extra space is used except for a few variables, so the space complexity is O(1).

Summary

The "1-bit and 2-bit Characters" problem can be solved efficiently by simulating the decoding process with a single pass through the array. By incrementing our pointer by 1 or 2 depending on whether we see a 0 or 1, we can easily determine if the last character stands alone. The key insight is that we don't need to explore all possible decodings; just follow the encoding rules step by step. This leads to an elegant O(n) time, O(1) space solution.