1375. Number of Times Binary String Is Prefix-Aligned
Problem Description
In this LeetCode problem, we are given an initially zeroed binary string of length n
, where the indexes are 1-indexed. Throughout a sequence of steps defined by an integer array flips
, we flip the bits of this binary string from 0
to 1
. The i
th element of flips
represents the bit position in the binary string that will be flipped during the i
th step of the process.
A binary string is considered prefix-aligned after the i
th step if all the bits from the beginning of the string to position i
are set to 1
, while the rest of the string remains at 0
. The task is to calculate the total number of times the binary string is prefix-aligned during the entire flipping process.
For example:
- Initial binary string of length 5: 00000 - flips sequence: [3,2,4,1,5] After each flip: - Step 1, flip position 3: 00100 (Not prefix-aligned as the first bit is still 0) - Step 2, flip position 2: 01100 (Not prefix-aligned as the first two bits are not all 1) - Step 3, flip position 4: 01110 (Not prefix-aligned as the first four bits are not all 1) - Step 4, flip position 1: 11110 (Not prefix-aligned as the first four bits are not all 1) - Step 5, flip position 5: 11111 (Prefix-aligned as all the bits are 1) Hence, the binary string is prefix-aligned 1 time during the flipping process.
Understanding the problem is crucial before attempting to create a solution.
Intuition
The intuition behind the solution is to keep track of the highest bit position (let's call it mx
) that has been flipped at each step. For each step i
, we compare mx
with the current step index i
: if mx
is equal to i
, it means that all bits up to the current step index have been flipped to 1
, and hence the string is prefix-aligned.
Here is how this intuition is applied to the solution:
- Initialize the counter
ans
to keep track of the number of times the string is prefix-aligned, andmx
to record the highest bit position flipped so far. - Iterate through each flip in the sequence, keeping track of the current step number
i
(starting from 1). - Update
mx
to be the maximum between its current value and the bit positionx
of the current flip. - If
mx
is equal toi
after flipping the bit at positionx
, incrementans
by 1 since the string is currently prefix-aligned. - Continue the loop until all flips are processed.
- Return
ans
, the total count of prefix-aligned occurrences.
Using this approach, we can efficiently determine the number of times the input binary string is prefix-aligned during the flipping process by only keeping track of the maximum flip position and the current step index.
Solution Approach
The solution provided follows an iterative approach with two primary variables in play: ans
and mx
. The variable ans
serves as a counter for the instances when the binary string is prefix-aligned, and mx
keeps track of the maximum index that has been flipped so far.
- Initialize
ans
to0
. This variable will count the number of times the binary string is prefix-aligned during the flip sequence. - Initialize
mx
to0
. This variable represents the maximum position of the flipped bit encountered up to the current step.
We use a for loop to iterate through each flip in the provided flips
list. The loop uses the built-in enumerate
function in Python to loop over flips
, starting from index 1
because the problem is 1-indexed
.
- During each iteration of the loop, we get two values:
i
, the step number starting from1
, andx
, the current position to flip. - For each flip, update
mx
to be the maximum between the currentmx
and the flip positionx
. This is achieved by the expressionmx = max(mx, x)
, which ensuresmx
always reflects the farthest position that was flipped till the current step. - The check
mx == i
will beTrue
if all bits from the start to the current positioni
are1
(thus, the string is prefix-aligned). If so, we incrementans
by1
. This leverages the fact that a binary string is prefix-aligned if the maximum flipped position at stepi
is equal toi
itself. Any flip sequence that has the largest flip within the range[1, i]
ati
ensures that all preceding bits are already flipped to1
. - Finally, the loop concludes once all the elements in
flips
have been iterated, and theans
value is returned.ans
now contains the number of times the binary string was prefix-aligned during the process.
This algorithm doesn't use any complex data structures and requires no additional space besides the two variables ans
and mx
, making it space-efficient. The time complexity of the algorithm is O(n) where n is the number of flips since we are going through each flip exactly once. It efficiently solves the problem by keeping track of only the current state necessary to determine prefix alignment at each step without reconstructing the binary string at each instance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have an initially zeroed binary string of length 4
and the following flips sequence: [1,3,2,4]
.
- Initial binary string: 0000
We iterate through each flip, updating the maximum position mx
flipped, and checking after each step if the string is prefix-aligned.
-
Step 1, flip position 1: The binary string after the flip becomes
1000
.mx
is updated to1
. Sincemx
(1) equals the step numberi
(1), we incrementans
by 1. The string is prefix-aligned.- New binary string: 1000
mx
= 1ans
= 1
-
Step 2, flip position 3: The binary string becomes
1010
. The newmx
is3
, which is now the highest position flipped so far. Sincemx
(3) does not equal the step numberi
(2),ans
is not incremented. The string is not prefix-aligned.- New binary string: 1010
mx
= 3ans
still = 1
-
Step 3, flip position 2: After this flip, the binary string is
1110
, andmx
remains3
. Asmx
(3) is not equal to the step numberi
(3),ans
remains the same. The string is not prefix-aligned.- New binary string: 1110
mx
still = 3ans
still = 1
-
Step 4, flip position 4: The final binary string is
1111
.mx
is updated to4
, which now equals the step numberi
(4). We incrementans
by 1 again because the string is prefix-aligned.- New binary string: 1111
mx
= 4ans
= 1 + 1 = 2
At the end of the flipping process, we have encountered 2 instances where the binary string is prefix-aligned, which means our answer ans
is 2
.
Using the solution approach, we keep track of the maximum flipped position and check for prefix alignment in each step efficiently. The variables ans
and mx
enable us to do this without needing additional data structures or performing complex operations. This makes the algorithm space-efficient and straightforward to implement with a time complexity of O(n), where n is the number of flips.
Solution Implementation
1# This class contains a method to determine the number of times all light bulbs are blue.
2class Solution:
3 def numTimesAllBlue(self, flips: List[int]) -> int:
4 # Initialize the number of moments when all bulbs are blue and the current maximum flipped bulb position.
5 moments_all_blue = 0
6 max_flipped_position = 0
7
8 # Loop through each flip by index and value.
9 for moment, flip_position in enumerate(flips, 1):
10 # Update the maximum flipped position if the current flip position is greater.
11 max_flipped_position = max(max_flipped_position, flip_position)
12
13 # If the maximum flipped position equals the current moment index, all the bulbs are blue.
14 moments_all_blue += max_flipped_position == moment
15
16 # Return the total count of moments when all the bulbs are blue.
17 return moments_all_blue
18```
19
20In the code above:
21
22- `flips`: The list of light bulb positions to flip during each moment, starting from 1.
23- `moments_all_blue`: The count of times when all lights up to the current moment (included) turned blue.
24- `max_flipped_position`: The maximum position (index) among the flipped light bulbs. If the maximum position we have flipped so far equals the number of flips (moments) that have occurred, it means that all the bulbs are blue.
25- The `enumerate` function is used to loop through each flip with its corresponding moment, beginning with 1. The `enumerate` function returns a tuple of two values: the index (starting from 1 in this case) and the value from the `flips` list.
26
27It's important to import the `List` typing from the `typing` module to ensure the type hint is recognized by the Python interpreter:
28
29```python
30from typing import List
31
1class Solution {
2 public int numTimesAllBlue(int[] flips) {
3 int numMomentsAllBlue = 0; // This will store the number of moments when all bulbs are blue
4 int maxTurnedOnBulb = 0; // This will keep track of the highest numbered bulb that has been turned on
5
6 // Iterate through the flips array. Each flip represents turning on the bulb at that index.
7 for (int moment = 1; moment <= flips.length; ++moment) {
8 // Update the maxTurnedOnBulb with the maximum value between the current max and the bulb flipped at this moment
9 maxTurnedOnBulb = Math.max(maxTurnedOnBulb, flips[moment - 1]);
10
11 // If the maximum turned-on bulb number equals the current moment, increment the numMomentsAllBlue counter
12 // It means all bulbs up to that point are blue
13 if (maxTurnedOnBulb == moment) {
14 ++numMomentsAllBlue;
15 }
16 }
17
18 // Return the total number of moments when all flipped-on bulbs are blue
19 return numMomentsAllBlue;
20 }
21}
22
1#include <vector>
2#include <algorithm> // For using the max function
3
4class Solution {
5public:
6 // Function to count the number of moments when all bulbs are blue
7 int numTimesAllBlue(vector<int>& flips) {
8 int countBlueMoments = 0; // Initialize a counter for the blue moments
9 int maxFlipped = 0; // This will keep track of the maximum bulb number flipped so far
10
11 // Loop through each flip in the flips vector
12 for (int i = 1; i <= flips.size(); ++i) {
13 // Update the maximum flipped bulb number if the current flip is greater
14 maxFlipped = max(maxFlipped, flips[i - 1]);
15
16 // If the maximum flipped bulb number equals the number of flips so far,
17 // it means all bulbs up to that point are on (and hence blue)
18 countBlueMoments += (maxFlipped == i) ? 1 : 0; // Use the ternary operator for the condition
19 }
20
21 // Return the total count of moments when all turned-on bulbs are blue
22 return countBlueMoments;
23 }
24};
25
1function numTimesAllBlue(lightSwitches: number[]): number {
2 let countAllBlue = 0; // This will hold the number of times all lights turned blue
3 let maxSwitchedOn = 0; // Tracks the maximum light switch number turned on so far
4
5 // Loop through each light switch flip
6 for (let i = 1; i <= lightSwitches.length; ++i) {
7 // Update maxSwitchedOn to be the highest of the current max or the current light switch flipped
8 maxSwitchedOn = Math.max(maxSwitchedOn, lightSwitches[i - 1]);
9 // If maxSwitchedOn is equal to the number of flips so far, all lights are blue
10 if (maxSwitchedOn === i) {
11 countAllBlue += 1;
12 }
13 }
14
15 // Return the total number of times all lights have turned blue
16 return countAllBlue;
17}
18
Time and Space Complexity
Time Complexity
The given algorithm consists of a single for
loop that iterates through every element in the flips
list exactly once. The enumeration of flips
does not change the overall time complexity. Inside the loop, the algorithm performs a constant amount of work on each iteration, including a comparison and an assignment. Therefore, the time complexity of this function is O(n)
where n
is the number of elements in flips
.
Space Complexity
The space complexity of the algorithm is defined by the amount of additional memory used by the algorithm as a function of the input size. Within the provided algorithm, ans
and mx
are the only variables that occupy extra space, and their memory footprint does not depend on the size of the input. As a result, the space complexity is O(1)
because the amount of extra memory used is constant, irrespective of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!