Count Subarrays With More Ones Than Zeros - Solution & Explanation
Problem Statement
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. Since the answer may be very large, return it modulo 109 + 7.
A subarray is a contiguous sequence of elements within an array.
Example 1:
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] The subarrays of size 2 that have more ones than zeros are: [1,1] The subarrays of size 3 that have more ones than zeros are: [0,1,1], [1,1,0], [1,0,1] The subarrays of size 4 that have more ones than zeros are: [1,1,0,1] The subarrays of size 5 that have more ones than zeros are: [0,1,1,0,1]
Example 2:
Input: nums = [0] Output: 0 Explanation: No subarrays have more ones than zeros.
Example 3:
Input: nums = [1] Output: 1 Explanation: The subarrays of size 1 that have more ones than zeros are: [1]
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1
Approach Overview
Problem Overview: Given a binary array, count the number of subarrays where the number of 1s is strictly greater than the number of 0s. The challenge is efficiently checking this condition across all possible subarrays without enumerating every pair of indices.
Approach 1: Brute Force / Prefix Sum Check (O(n²) time, O(1) extra space)
Convert the problem into a running difference: treat 1 as +1 and 0 as -1. A subarray has more ones than zeros if its sum is positive. For every start index, iterate the end index and maintain a running sum. If the sum becomes positive, increment the answer. This works because the transformed array directly encodes the difference between counts. Time complexity is O(n²) since every subarray is checked, with O(1) extra space. Useful for understanding the prefix sum transformation but too slow for large inputs.
Approach 2: Prefix Sum + Binary Indexed Tree (O(n log n) time, O(n) space)
Transform the array by mapping 0 → -1 and compute a running prefix sum. A subarray (l, r) has more ones than zeros if prefix[r] - prefix[l] > 0, which means prefix[r] > prefix[l]. The task becomes counting how many previous prefix sums are smaller than the current one. Maintain frequencies of prefix sums using a Binary Indexed Tree. For each prefix value, query how many earlier prefixes are smaller, add that count to the answer, then update the current prefix in the tree. Coordinate compression keeps indices manageable. Each update and query costs O(log n), giving total complexity O(n log n) with O(n) space.
This approach is a classic application of prefix sums combined with order statistics. Similar counting problems can also be solved using Segment Trees, merge sort–based inversion counting, or ordered sets. All rely on tracking how many earlier prefix sums are smaller than the current one.
Recommended for interviews: Start by explaining the prefix sum transformation (1 → +1, 0 → -1). That observation shows you understand the core condition. Then move to the Prefix Sum + Binary Indexed Tree approach. Interviewers expect the optimized counting method because it reduces the problem to prefix ordering queries and runs in O(n log n). Mentioning alternatives like merge sort counting or ordered sets also signals strong algorithmic range.
Approach 1: Prefix Sum + Binary Indexed Tree
The problem requires us to count the number of subarrays where the count of 1 is greater than the count of 0. If we treat 0 in the array as -1, then the problem becomes counting the number of subarrays where the sum of elements is greater than 0.
To calculate the sum of elements in a subarray, we can use the prefix sum. To count the number of subarrays where the sum of elements is greater than 0, we can use a binary indexed tree to maintain the occurrence count of each prefix sum. Initially, the occurrence count of the prefix sum 0 is 1.
Next, we traverse the array nums, use variable s to record the current prefix sum, and use variable ans to record the answer. For each position i, we update the prefix sum s, then query the occurrence count of the prefix sum in the range [0, s) in the binary indexed tree, add it to ans, and then update the occurrence count of s in the binary indexed tree.
Finally, return ans.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Default Approach
Code
Python
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum + Binary Indexed Tree | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Running Sum | O(n²) | O(1) | Small arrays or when demonstrating the core prefix-sum idea in interviews |
| Prefix Sum + Binary Indexed Tree | O(n log n) | O(n) | General case for large inputs; efficient counting of smaller previous prefix sums |
| Prefix Sum + Merge Sort Counting | O(n log n) | O(n) | Useful when solving similar problems via divide-and-conquer or inversion counting |
| Prefix Sum + Ordered Set / Balanced BST | O(n log n) | O(n) | Languages with built-in ordered sets or tree maps that support rank queries |
Video Solution
【每日一题】LeetCode 2031. Count Subarrays With More Ones Than Zeros • Huifeng Guan • 616 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Count Subarrays With More Ones Than Zeros easy or hard?
Count Subarrays With More Ones Than Zeros Python/Java solution
How to solve Count Subarrays With More Ones Than Zeros in O(n)?
What is the best approach for Count Subarrays With More Ones Than Zeros?
Is Count Subarrays With More Ones Than Zeros asked at Google/Amazon/Meta?
What data structure is used in Count Subarrays With More Ones Than Zeros?
What is the time complexity of Count Subarrays With More Ones Than Zeros?
Ready to solve this problem?
Practice Count Subarrays With More Ones Than Zeros with our built-in code editor and test cases.
Practice on FleetCode