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.
Which of the following is a good use case for backtracking?
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
iwith value 0, which represents the current position in thebitsarray. - The length of the array is stored in the variable
n. - We begin a while-loop that continues as long as
iis less thann - 1. We stop atn - 1because 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 incrementiby 2 to jump past this character. - If
bits[i]is 0, we're at a one-bit character, so we incrementiby 1 to move to the next bit.
- If
- The loop continues, incrementing
iin steps of 1 or 2 until it reaches the final or second-to-final bit in the array. - After the loop, we check if
iis exactly atn - 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 returntrue. - If
i != n - 1, it implies we've gone past the last bit as part of a two-bit character, so we returnfalse. However, this situation won't happen as per the problem constraints.
- If
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.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Example Walkthrough
Let's consider an example where the bits array is [1, 0, 0].
- We initialize an index variable
iwith the value of 0 and store the length of the arraynwhich is 3. - Start the while-loop since
i(0) is less thann - 1(2). - Check the value of
bits[i]:bits[0]is1, which indicates the start of a two-bit character. We incrementiby 2. Nowiequals 2.
- The loop continues since
i(2) is still less thann - 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
iequalsn - 1(iis 2 andn - 1is also 2), which is true. - Since
i == n - 1, we determine that the final 0 is a one-bit character and returntrue.
Now let's consider a slightly variation where bits is [1, 1, 0]:
- We initialize
iwith the value of 0 andnis again 3. - Start the while-loop with
iless thann - 1. - Check the value of
bits[i]:bits[0]is1, so we have encountered a two-bit character. We incrementiby 2, resulting inibeing 2.
- Since
inow equalsn - 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 - 1holds true. - Because the condition
i == n - 1is true, we conclude that the last0represents a one-bit character, so we returntrue.
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
171class 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}
201#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};
251/**
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
28Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?
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.
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.