How hard is LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is rated Medium on LeetCode.

What is the time complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

The Python solution on this page runs in O(n), where n is the length of the array flips.

What is the space complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1375. Number of Times Binary String Is Prefix-Aligned cover?

LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is tagged Array on LeetCode.

Number of Times Binary String Is Prefix-Aligned — LeetCode 1375 Python Solution

MediumArray

Problem: #1375
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: flips = [3,2,4,1,5]
Output: 2
Explanation: The binary string is initially "00000".

Python solution

Python

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        ans = mx = 0
        for i, x in enumerate(flips, 1):
            mx = max(mx, x)
            ans += mx == i
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array flips
Space	O(1) auxiliary

Frequently asked questions

How hard is LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is rated Medium on LeetCode.
What is the time complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: The Python solution on this page runs in O(n), where n is the length of the array flips.
What is the space complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1375. Number of Times Binary String Is Prefix-Aligned cover?: LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is tagged Array on LeetCode.