1-bit and 2-bit Characters | 2 Ways | Easy | Leetcode 717 | codestorywithMIK
1-bit and 2-bit Characters - Video Solution
Watch 10 video solutions for 1-bit and 2-bit Characters, a easy level problem involving Array. This walkthrough by codestorywithMIK has 5,003 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
We have two special characters:
- The first character can be represented by one bit
0. - The second character can be represented by two bits (
10or11).
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 <= 1000bits[i]is either0or1.
Approach Overview
Problem Overview: You are given a binary array where characters are encoded using either 0 (a 1‑bit character) or 10/11 (a 2‑bit character). The array always ends with 0. The task is to determine whether the last character must be a 1‑bit character after decoding the sequence.
Approach 1: Traversal and Check (O(n) time, O(1) space)
Scan the array from left to right using an index pointer. If the current bit is 0, it represents a 1‑bit character, so move the pointer forward by one position. If the current bit is 1, it starts a 2‑bit character (10 or 11), so skip two positions. Continue this process until you reach the end of the array. The key insight: if the pointer lands exactly on the last index, the last character is a 1‑bit character; if the pointer jumps past it, the last 0 was consumed as part of a 2‑bit character. This greedy traversal works because each encoding pattern has a fixed length. The array is processed once, giving O(n) time and constant O(1) space. Since the problem operates directly on a binary array, no additional data structures are needed.
Approach 2: Reverse Traversal (O(n) time, O(1) space)
Instead of simulating decoding from the start, examine the pattern before the last 0. Move backward from the second‑to‑last index and count how many consecutive 1s appear before that final zero. If the count of consecutive ones is even, the last 0 stands alone as a 1‑bit character. If the count is odd, the last 0 must pair with the preceding 1 to form a 2‑bit character. This works because every 2‑bit encoding begins with 1, and pairs of bits determine whether the final zero gets grouped. The algorithm performs a single backward pass over part of the array, resulting in O(n) time and O(1) space. This approach is common in array scanning problems and resembles simple greedy reasoning about local patterns.
Recommended for interviews: The forward traversal approach is the one most interviewers expect. It directly simulates the decoding process and is easy to reason about during a whiteboard explanation. The reverse traversal trick is a neat optimization insight and demonstrates deeper pattern recognition. Showing the straightforward traversal first proves you understand the encoding rules, while mentioning the reverse counting method shows stronger problem‑solving depth.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Traversal and Check | O(n) | O(1) | Best general solution. Easy to explain in interviews and directly simulates decoding. |
| Reverse Traversal | O(n) | O(1) | Useful when reasoning from the end of the array or identifying patterns in consecutive bits. |