algoadvance

Leetcode 717. 1

Problem Statement

The problem is LeetCode 717: 1-bit and 2-bit Characters.

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, we need to determine if the last character must be a one-bit character or not.

Function signature:

bool isOneBitCharacter(vector<int>& bits);

Clarifying Questions

1. Input Constraints:
   • How many elements can the input array have?
   • Is the input array always guaranteed to have at least one 0 at the end?
2. Output:
   • Should the function return a boolean value indicating whether the last character is a one-bit character?
3. Examples:
   • Input: bits = [1, 0, 0] Output: true
   • Input: bits = [1, 1, 1, 0] Output: false

Strategy

To solve this problem, we’ll traverse through the array to understand how characters are formed:

1. We need to iterate through the input bits array from the start to determine the formation of characters until we reach the end.
2. If we encounter a 1, it means the current character is formed by this 1 and the next bit (i.e., it is a two-bit character). Therefore, we should skip the next index.
3. If we encounter a 0, it means the current character is a one-bit character.
4. Finally, we will check whether the last processed bit was a part of a one-bit character or a two-bit character.

Code

#include <vector>
using namespace std;

bool isOneBitCharacter(vector<int>& bits) {
    int n = bits.size();
    int i = 0;

    while (i < n - 1) {
        if (bits[i] == 1) {
            i += 2;
        } else {
            i++;
        }
    }

    // i should be on the position of the last bit, if i == n - 1, means the last bit is a single 0
    return i == n - 1;
}

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the input array. This is because we are iterating through the array once.
• Space Complexity: O(1), since we are not using any additional space that scales with the input size.

The given solution efficiently checks the formation of characters in the array and determines if the last character is a one-bit character.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?