717. 1-bit and 2-bit Characters

Problem Description

In the given problem, we have an array called bits, which consists of only the numbers 0 and 1 representing bits. These bits form characters according to certain rules. A single bit of 0 represents one character (one-bit character), and a sequence of two bits that are either 10 or 11 represents another character (two-bit character). The array ends with a 0, which might be a part of the last two-bit character or stand alone as a one-bit character. Our task is to determine if this final 0 is definitely the one-bit character, not part of a two-bit character, by returning true if it is, or false if it's not.

Intuition

To solve this problem, we can iterate through the bits array and track what kind of character we're currently on. Since only a 1 can indicate the beginning of a two-bit character, each time we encounter a 1, we know the next bit belongs to the same character. Therefore, we can increment our position in the array by 2 in this case. If it's a 0, it must represent a one-bit character, so we only increment our position by 1.

The trick of the solution is to notice that we’ll never need to skip over the final 0 bit, because it's given that the array ends with a 0. We iterate through the array until we reach the penultimate bit. If our final position falls exactly on the penultimate bit, it means that the last bit is a one-bit character as it's impossible for it to be consumed as part of a two-bit character.

From this intuition, the solution emerges as a simple loop that controls the index based on the current bit value.

Solution Approach

The implementation of the solution makes use of a simple while-loop to traverse the bits array, ending the loop one element before the last to ensure we are only looking at complete characters.

Here's a breakdown of the algorithm, using the given solution as a reference:

Initialize an index variable i with value 0, which represents the current position in the bits array.
The length of the array is stored in the variable n.
We begin a while-loop that continues as long as i is less than n - 1. We stop at n - 1 because we're examining characters, and the last character cannot start at the second-to-last bit.
Within the loop, we check the value of the current bit:
- If bits[i] is 1, we're at the start of a two-bit character, so the current bit and the next bit form a character. We increment i by 2 to jump past this character.
- If bits[i] is 0, we're at a one-bit character, so we increment i by 1 to move to the next bit.
The loop continues, incrementing i in steps of 1 or 2 until it reaches the final or second-to-final bit in the array.
After the loop, we check if i is exactly at n - 1, which is where the final 0 is located.
- If i == n - 1, it means the last bit has not been part of any character we have encountered, so it stands alone as a one-bit character. In this case, we return true.
- If i != n - 1, it implies we've gone past the last bit as part of a two-bit character, so we return false. However, this situation won't happen as per the problem constraints.

The strength of this solution lies in its simplicity and efficiency - it has a time complexity of O(n), since it involves a single pass through the array, and a space complexity of O(1), as it requires a constant amount of extra space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example where the bits array is [1, 0, 0].

We initialize an index variable i with the value of 0 and store the length of the array n which is 3.
Start the while-loop since i (0) is less than n - 1 (2).
Check the value of bits[i]:
- bits[0] is 1, which indicates the start of a two-bit character. We increment i by 2. Now i equals 2.
The loop continues since i (2) is still less than n - 1 (2). However, this is not true—it's actually equal, so the condition to continue the loop is not met.
Loop has terminated and we check if i equals n - 1 (i is 2 and n - 1 is also 2), which is true.
Since i == n - 1, we determine that the final 0 is a one-bit character and return true.

Now let's consider a slightly variation where bits is [1, 1, 0]:

We initialize i with the value of 0 and n is again 3.
Start the while-loop with i less than n - 1.
Check the value of bits[i]:
- bits[0] is 1, so we have encountered a two-bit character. We increment i by 2, resulting in i being 2.
Since i now equals n - 1 (both are 2), the while-loop condition is no longer met and the loop terminates.
We check the condition outside of the loop, where i == n - 1 holds true.
Because the condition i == n - 1 is true, we conclude that the last 0 represents a one-bit character, so we return true.

This illustrates how the solution approach effectively determines whether the final 0 in the bits array stands as a one-bit character by iterating through the bits and tracking the position according to the rules described.

Solution Implementation

1class Solution:
2    def isOneBitCharacter(self, bits: List[int]) -> bool:
3        # Initialize the index to 0
4        index = 0
5        # Get the total number of bits
6        total_bits = len(bits)
7
8        # Iterate through the bits until the second-to-last element
9        while index < total_bits - 1:
10            # Move the index by 2 if the current bit is 1 (since it's the start of a 2-bit character),
11            # otherwise by 1 if the current bit is 0 (1-bit character)
12            index += bits[index] + 1
13
14        # Return True if the last bit was reached as a 1-bit character,
15        # False if we went past it (which is impossible in the constraints given)
16        return index == total_bits - 1
17

1class Solution {
2    public boolean isOneBitCharacter(int[] bits) {
3        // Initialize current position index
4        int currentIndex = 0;
5        // Get the length of bits array
6        int length = bits.length;
7
8        // Iterate over the array until we reach the penultimate character
9        // since we're checking for a one bit character at the end
10        while (currentIndex < length - 1) {
11            // If we encounter a '1', we move two places ahead, as '1' signifies the beginning of a two-bit character.
12            // If we encounter a '0', we move one place ahead, as '0' signifies a one-bit character.
13            currentIndex += bits[currentIndex] + 1;
14        }
15
16        // If we are standing at the penultimate position after the loop, it means the last character is a one-bit character
17        return currentIndex == length - 1;
18    }
19}
20

1#include <vector> // Include the necessary header for std::vector
2
3class Solution {
4public:
5    // Function to determine if the last character is encoded by one bit
6    bool isOneBitCharacter(std::vector<int>& bits) {
7        // Initialize the index variable to traverse the array
8        int index = 0;
9        // Store the size of the bits vector to avoid calculating it multiple times
10        int size = bits.size();
11
12        // Loop through the vector until the second-to-last element
13        while (index < size - 1) {
14            // We increment the index by 2 if the current bit is 1,
15            // since it indicates the beginning of a two-bit character,
16            // and by 1 if the current bit is 0 (one-bit character).
17            index += bits[index] + 1;
18        }
19
20        // Return true if we reached exactly the last index (size - 1),
21        // which means the last character could only be a one-bit character
22        return index == size - 1;
23    }
24};
25

1/**
2 * Determines if the last character of the bit string is a one-bit character.
3 * One-bit character is represented by a single 0, while a two-bit character is represented by 10 or 11.
4 * This function assumes that the given string is a valid sequence of one-bit and two-bit characters.
5 *
6 * @param {number[]} bits - An array of bits.
7 * @return {boolean} True if the last character is a one-bit character, false otherwise.
8 */
9function isOneBitCharacter(bits: number[]): boolean {
10    let currentIndex: number = 0;              // Index of the current bit in the loop.
11    const length: number = bits.length;        // Total number of bits in the array.
12
13    // Loop through the bits array until the second-to-last element.
14    while (currentIndex < length - 1) {
15        // If the current bit is 0, it represents a one-bit character, move to the next bit.
16        // If it is 1, it represents the first bit of a two-bit character, so skip the next bit.
17        currentIndex += bits[currentIndex] + 1;
18    }
19
20    // If currentIndex exactly matches the index of the last bit (which would be a one-bit character),
21    // it means the last character is a one-bit character.
22    return currentIndex === length - 1;
23}
24
25// Example usage:
26// const result: boolean = isOneBitCharacter([1, 0, 0]);
27// console.log(result); // Should log true or false depending on the input
28

Time and Space Complexity

The time complexity of the provided function isOneBitCharacter is O(n), where n is the length of the input list bits. This is because the function uses a while loop that iterates through the bits, incrementing the index i by either 1 or 2 each time based on the value of the current bit. In the worst-case scenario, each bit is a 0, and the loop iterates n times. In the best case, with alternating 1s and 0s, the function could potentially iterate n/2 times. However, since we only consider the upper bound, the loop is linear in nature with respect to the input size.

The space complexity of the function is O(1). This is because there are a fixed number of variables (i, n) that do not depend on the size of the input, and no additional data structures are used that would increase the amount of memory used as the input size increases.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know