Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

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.

Solution

Method 1 – Greedy Linear Scan

Intuition

The key idea is to simulate reading the bits from left to right, always taking the largest valid character (either a 2-bit character if we see a 1, or a 1-bit character if we see a 0). If we land exactly on the last bit and it’s a single 0, then the last character is a one-bit character.

Approach

  1. Initialize a pointer i at the start of the array.
  2. While i is less than the last index:
  • If bits[i] is 1, increment i by 2 (since 10 or 11 forms a 2-bit character).
  • If bits[i] is 0, increment i by 1 (since 0 is a 1-bit character).
  1. After the loop, check if i is exactly at the last index (len(bits) - 1).
  • If yes, the last character is a one-bit character, return true.
  • Otherwise, return false.

Code

1
2
3
4
5
6
7
8
9

class Solution {
   public boolean isOneBitCharacter(int[] bits) {
      int i = 0, n = bits.length;
      while (i < n - 1) {
        i += bits[i] == 1 ? 2 : 1;
      }
      return i == n - 1;
   }
}
1
2
3
4
5
6

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

Complexity

  • ⏰ Time complexity: O(N), where N is the length of bits.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.