Scale Engineer

1-bit and 2-bit Characters

Easy
#0671Time: O(N), where N is the length of the `bits` array. Each recursive call processes one or two elements and moves forward, so each element is visited at most once.Space: O(N), where N is the length of the array. In the worst-case scenario (an array of all zeros), the recursion depth can go up to N, consuming space on the call stack.2 companies
Data structures
Array
Companies
IXLQuora

Prompt

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.

 

Example 1:

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:

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simulates the decoding process recursively. A helper function determines if the end of the array can be reached from a given starting index. The decoding rules are applied to determine the next index to recurse on.

Algorithm

  • Define a recursive helper function canDecode(bits, index).
  • In canDecode:
    • If index == bits.length - 1, return true.
    • If index >= bits.length, return false.
    • If bits[index] == 0, it's a one-bit character, so recursively call canDecode(bits, index + 1).
    • If bits[index] == 1, it's a two-bit character, so recursively call canDecode(bits, index + 2).
  • The initial call from the main function is canDecode(bits, 0).

Walkthrough

This method uses recursion to mimic the deterministic decoding process. We define a function that takes the current index as a parameter and explores the single possible decoding path from there.

  • The base cases for the recursion are crucial:

    1. If the current index is the last index of the array (bits.length - 1), it means we have successfully landed on the final 0. This must be a one-bit character, so we've found a valid decoding ending with a one-bit character. We return true.
    2. If the current index goes beyond the array bounds (>= bits.length), it means the previous step led to an invalid state (e.g., a two-bit character starting at the second-to-last position). We return false.

  • The recursive step depends on the value at the current index:

    • If bits[index] is 0, we must treat it as a one-bit character and move to the next index (index + 1).
    • If bits[index] is 1, we must treat it as a two-bit character and skip the next bit, moving to index + 2.

The initial call will be with index = 0.

class Solution {    public boolean isOneBitCharacter(int[] bits) {        return canDecode(bits, 0);    }     private boolean canDecode(int[] bits, int index) {        // Base case: If we land exactly on the last index, it must be the 1-bit '0'.        if (index == bits.length - 1) {            return true;        }        // Base case: If we overshoot, it's an invalid decoding.        if (index >= bits.length) {            return false;        }         // Recursive step based on the character type        if (bits[index] == 0) {            // 1-bit character, move to the next index.            return canDecode(bits, index + 1);        } else {            // 2-bit character, skip the next index.            return canDecode(bits, index + 2);        }    }}

Complexity

Time

O(N), where N is the length of the `bits` array. Each recursive call processes one or two elements and moves forward, so each element is visited at most once.

Space

O(N), where N is the length of the array. In the worst-case scenario (an array of all zeros), the recursion depth can go up to N, consuming space on the call stack.

Trade-offs

Pros

  • Conceptually simple and directly models the problem's structure.

  • The logic is a straightforward translation of the decoding rules.

Cons

  • Uses O(N) space for the recursion call stack, which is less efficient than an iterative solution.

  • Can lead to a StackOverflowError for very large inputs, although not an issue with the given constraints.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem