Is Count Subarrays With More Ones Than Zeros easy or hard?

The problem is rated Medium on LeetCode but feels closer to hard if you have not seen prefix-order counting before. The key difficulty is recognizing the transformation from binary values to prefix sums and then counting earlier smaller prefixes efficiently using a Fenwick Tree or similar structure.

Count Subarrays With More Ones Than Zeros Python/Java solution

Implement the optimal approach by converting the array (1 → +1, 0 → -1), computing prefix sums, and using a Fenwick Tree to track frequencies of previous prefix values. For each prefix, query how many earlier prefixes are smaller and update the tree. The same logic works in Python, Java, C++, Go, and TypeScript with O(n log n) complexity.

How to solve Count Subarrays With More Ones Than Zeros in O(n)?

A strict O(n) solution is generally not used for this problem because we must dynamically count how many previous prefix sums are smaller than the current one. That operation requires an ordered structure such as a Binary Indexed Tree, Segment Tree, or balanced BST, leading to O(n log n) complexity. The key trick is mapping 0 to -1 and using prefix sums.

What is the best approach for Count Subarrays With More Ones Than Zeros?

The most efficient approach uses a prefix sum transformation combined with a Binary Indexed Tree (Fenwick Tree). Convert 0 to -1 and maintain a running prefix sum. For each position, count how many earlier prefix sums are smaller than the current one using the tree. This counts all subarrays where ones exceed zeros in O(n log n) time and O(n) space.

Is Count Subarrays With More Ones Than Zeros asked at Google/Amazon/Meta?

Problems involving prefix sums and counting subarrays with ordering constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include counting subarrays with positive sums, range sum queries, and inversion-style counting problems. Mastering prefix sums with Fenwick Trees or Segment Trees is valuable for these interviews.

What data structure is used in Count Subarrays With More Ones Than Zeros?

The most common data structure is a Binary Indexed Tree (Fenwick Tree) used to maintain counts of prefix sums and query how many are smaller than the current value. Alternatives include Segment Trees, ordered sets (balanced BSTs), or merge-sort-based counting techniques. All support efficient prefix ordering queries.

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

The optimal solution runs in O(n log n) time using prefix sums and a Binary Indexed Tree or similar ordered structure. Each element requires a logarithmic query and update. A brute-force approach that checks all subarrays runs in O(n^2) time and is too slow for large inputs.

Description Hints 3 Solution Video 15:28

2031. Count Subarrays With More Ones Than Zeros

Medium49.7% acceptance1 companyPremium elsewhere, free here

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 10⁹ + 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 <= 10⁵
0 <= nums[i] <= 1

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Change the zeros in nums to -1 and create a prefix sum array prefixSum using the new nums.

Hint 2

If prefixSum[i] for any index i in the range 0 <= i < prefixSum.length is positive, that means that there are more ones than zeros in the prefix ending at index i.

Hint 3

If prefixSum[j] > prefixSum[i] for two indexes i and j such that 0 <= i < j < prefixSum.length, that means that there are more ones than zeros in nums in the range [i + 1 : j] (inclusive)

15:28

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution