Count Subarrays With More Ones Than Zeros - Video Solutions
【每日一题】LeetCode 2031. Count Subarrays With More Ones Than Zeros
Count Subarrays With More Ones Than Zeros - Video Solution
Watch 3 video solutions for Count Subarrays With More Ones Than Zeros, a medium level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Huifeng Guan has 616 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |