MediumNo. 2031LeetCode Premium
Count Subarrays With More Ones Than Zeros — LeetCode 2031 Python Solution
- Pattern
- Binary Search
- Topics
- Binary Indexed Tree, Segment Tree, Array, Hash Table, Binary Search, Divide and Conquer, Ordered Set, Merge Sort
- 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
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 ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2424 | Longest Uploaded Prefix | Medium |
| 2080 | Range Frequency Queries | Medium |
| 2250 | Count Number of Rectangles Containing Each Point | Medium |
| 2251 | Number of Flowers in Full Bloom | Hard |
| 2713 | Maximum Strictly Increasing Cells in a Matrix | Hard |
| 0105 | Construct Binary Tree from Preorder and Inorder Traversal | Medium |
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 × 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.