LeetCode Solutions Blog

Count Subarrays With More Ones Than Zeros

Number: 510

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a binary array nums (containing only 0’s and 1’s), count how many subarrays have more 1’s than 0’s. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

Transform the array by converting 0’s to -1 and keeping 1’s as 1.
Use prefix sums so that the condition “more 1’s than 0’s” becomes “subarray sum > 0.”
The problem reduces to counting the number of pairs (i, j) with i < j such that prefix[j] > prefix[i].
This can be efficiently solved using a Binary Indexed Tree (Fenwick Tree) or merge sort based inversion counting, with coordinate compression to handle negative prefix sums.

Space and Time Complexity

Time Complexity: O(n log n) due to BIT queries/updates or merge sort based counting.
Space Complexity: O(n) for storing prefix sums and BIT data structure.

Solution

We start by transforming the binary array: convert each 0 to -1 and each 1 remains as 1. Create a prefix sum array P where P[0] = 0 and for 1 ≤ i ≤ n, P[i] = P[i-1] + (transformed value at i-1).
The requirement “more 1’s than 0’s” for a subarray from i to j translates to P[j+1] - P[i] > 0, or equivalently P[i] < P[j+1].
Thus, the goal is to count how many pairs of indices (i, j+1) satisfy i < j+1 and P[i] < P[j+1].

To count such pairs efficiently:

Use coordinate compression on the prefix sums to map them to a continuous range.
Use a BIT to keep a frequency count of prefix sums encountered.
As you iterate through the prefix sum array, for each prefix P[j], query the BIT for the count of earlier prefix sums that are smaller than P[j]. Add this count to the result, then update the BIT with P[j].
Finally, return the computed result modulo 10^9+7.

Code Solutions

# Python solution with detailed comments

MOD = 10**9 + 7

# Implementation of a Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, size):
        # Tree array of size size+1 (1-indexed)
        self.size = size
        self.tree = [0] * (size + 1)
        
    def update(self, index, value):
        # Increase the value at index and move to the next responsible node
        while index <= self.size:
            self.tree[index] += value
            index += index & -index
            
    def query(self, index):
        # Get cumulative frequency up to index
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

def countSubarrays(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    # Build prefix sum array with 0 converted to -1 and 1 remains 1
    for i in range(1, n+1):
        prefix[i] = prefix[i-1] + (1 if nums[i-1] == 1 else -1)
        
    # Coordinate compression: get sorted unique prefix sums
    all_vals = sorted(set(prefix))
    # Mapping each prefix value to a 1-indexed coordinate
    val_to_idx = {val: idx+1 for idx, val in enumerate(all_vals)}
    
    # Initialize BIT with the size equal to the number of unique prefix sums
    bit = BIT(len(all_vals))
    res = 0
    # Iterate over prefix sums and count valid subarrays
    for p in prefix:
        # Find compressed index for current prefix
        pos = val_to_idx[p]
        # Query BIT for count of prefix sums smaller than current prefix
        count_smaller = bit.query(pos - 1)
        res = (res + count_smaller) % MOD
        # Update BIT with current prefix occurring
        bit.update(pos, 1)
    return res

# Example usage:
if __name__ == "__main__":
    test_nums = [0, 1, 1, 0, 1]
    print(countSubarrays(test_nums))  # Expected output: 9