How hard is LeetCode 2031. Count Subarrays With More Ones Than Zeros?

LeetCode 2031. Count Subarrays With More Ones Than Zeros is rated Medium on LeetCode.

What is the time complexity of LeetCode 2031. Count Subarrays With More Ones Than Zeros?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2031. Count Subarrays With More Ones Than Zeros?

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

Is LeetCode 2031. Count Subarrays With More Ones Than Zeros a premium problem?

Yes. LeetCode 2031. Count Subarrays With More Ones Than Zeros is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Count Subarrays With More Ones Than Zeros — LeetCode 2031 Python Solution

MediumLeetCode PremiumBinary Indexed TreeSegment TreeArrayHash TableBinary SearchDivide and ConquerOrdered SetMerge Sort

Problem: #2031
Pattern: Binary Search
Reading time: 6 min
Source: leetcode.com

The problem

You are given a binary array nums containing only the integers 0 and 1. Return the number of subarrays in nums that have more 1's than 0's.

Example

Input: nums = [0,1,1,0,1]
Output: 9
Explanation: The subarrays of size 1 that have more ones than zeros are: [1], [1], [1]

Python solution

Python

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] += v
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:
        n = len(nums)
        base = n + 1
        tree = BinaryIndexedTree(n + base)
        tree.update(base, 1)
        mod = 10**9 + 7
        ans = s = 0
        for x in nums:
            s += x or -1
            ans += tree.query(s - 1 + base)
            ans %= mod
            tree.update(s + base, 1)
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2031. Count Subarrays With More Ones Than Zeros is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2031. Count Subarrays With More Ones Than Zeros?: LeetCode 2031. Count Subarrays With More Ones Than Zeros is rated Medium on LeetCode.
What is the time complexity of LeetCode 2031. Count Subarrays With More Ones Than Zeros?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2031. Count Subarrays With More Ones Than Zeros?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2031. Count Subarrays With More Ones Than Zeros cover?: LeetCode 2031. Count Subarrays With More Ones Than Zeros is tagged Binary Indexed Tree, Segment Tree, Array, Hash Table, Binary Search, Divide and Conquer, Ordered Set and Merge Sort on LeetCode.
Is LeetCode 2031. Count Subarrays With More Ones Than Zeros a premium problem?: Yes. LeetCode 2031. Count Subarrays With More Ones Than Zeros is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.