1375. Number of Times Binary String Is Prefix-Aligned LeetCode Solution
In this guide, you will get 1375. Number of Times Binary String Is Prefix-Aligned LeetCode Solution with the best time and space complexity. The solution to Number of Times Binary String Is Prefix-Aligned problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Times Binary String Is Prefix-Aligned
You have a 1-indexed binary string of length n where all the bits are 0 initially. We will flip all the bits of this binary string (i.e., change them from 0 to 1) one by one. You are given a 1-indexed integer array flips where flips[i] indicates that the bit at index i will be flipped in the ith step.
A binary string is prefix-aligned if, after the ith step, all the bits in the inclusive range [1, i] are ones and all the other bits are zeros.
Return the number of times the binary string is prefix-aligned during the flipping process.
Example 1:
Input: flips = [3,2,4,1,5]
Output: 2
Explanation: The binary string is initially “00000”.
After applying step 1: The string becomes “00100”, which is not prefix-aligned.
After applying step 2: The string becomes “01100”, which is not prefix-aligned.
After applying step 3: The string becomes “01110”, which is not prefix-aligned.
After applying step 4: The string becomes “11110”, which is prefix-aligned.
After applying step 5: The string becomes “11111”, which is prefix-aligned.
We can see that the string was prefix-aligned 2 times, so we return 2.
Input: flips = [4,1,2,3]
Output: 1
Explanation: The binary string is initially “0000”.
After applying step 1: The string becomes “0001”, which is not prefix-aligned.
After applying step 2: The string becomes “1001”, which is not prefix-aligned.
After applying step 3: The string becomes “1101”, which is not prefix-aligned.
After applying step 4: The string becomes “1111”, which is prefix-aligned.
We can see that the string was prefix-aligned 1 time, so we return 1.
Constraints:
n == flips.length
1 <= n <= 5 * 104
flips is a permutation of the integers in the range [1, n].
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1375. Number of Times Binary String Is Prefix-Aligned LeetCode Solution in C++
class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
int ans = 0;
int rightmost = 0;
for (int i = 0; i < flips.size(); ++i) {
rightmost = max(rightmost, flips[i]);
// max(flips[0..i]) = rightmost = i + 1,
// so flips[0..i] is a permutation of 1, 2, ..., i + 1.
if (rightmost == i + 1)
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
1375. Number of Times Binary String Is Prefix-Aligned LeetCode Solution in Java
class Solution {
public int numTimesAllBlue(int[] flips) {
int ans = 0;
int rightmost = 0;
for (int i = 0; i < flips.length; ++i) {
rightmost = Math.max(rightmost, flips[i]);
// Math.max(flips[0..i]) = rightmost = i + 1,
// so flips[0..i] is a permutation of 1, 2, ..., i + 1.
if (rightmost == i + 1)
++ans;
}
return ans;
}
} // code provided by PROGIEZ
1375. Number of Times Binary String Is Prefix-Aligned LeetCode Solution in Python
class Solution:
def numTimesAllBlue(self, flips: list[int]) -> int:
ans = 0
rightmost = 0
for i, flip in enumerate(flips):
rightmost = max(rightmost, flip)
# max(flips[0..i]) = rightmost = i + 1,
# so flips[0..i] is a permutation of 1, 2, ..., i + 1.
if rightmost == i + 1:
ans += 1
return ans # code by PROGIEZ
