Subarrays with Sum Equal to Even Count — Problem Statement & Solution Guide

ArraysHardSubarray Sum Equals K

TimeO(n)

SpaceO(n)

Problem Description

Given an array of integers nums, find the total number of contiguous subarrays where the sum of the elements is exactly equal to the count of even elements in that subarray.

An integer x is considered even if x % 2 == 0 (this includes negative even integers and zero).

DSA Pattern Breakdown

"Subarrays with Sum Equal to Even Count"

hard

WHY DOES IT MATTER?

The prefix sum + hashmap pattern transforms a seemingly quadratic subarray counting problem into a linear-time solution, which is essential for handling large datasets common in production systems. It also provides a clean, mathematically grounded framework that is easy to reason about and implement correctly.

OPTIMIZATION CHALLENGE

The core insight is to recognize that the equality condition can be expressed as a zero-sum over a transformed array. By converting the problem to counting equal prefix sums, we avoid nested loops and reduce the time complexity from O(n²) to O(n).

REAL-WORLD CONNECTION

Imagine a distributed log system where each log entry has a size and a flag indicating whether it contains sensitive data. You need to find contiguous log segments where the total size equals the number of sensitive entries. The prefix sum approach is analogous to maintaining cumulative metrics across shards, enabling efficient real-time analytics without scanning every segment.

When explaining this in an interview, emphasize the transformation step first, then show how the hashmap naturally counts matches. Highlight that the algorithm is a direct application of a well-known pattern, which demonstrates both depth of knowledge and the ability to apply proven techniques.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to counting subarrays where the sum of elements equals the number of even elements. By defining a transformed value for each element as val[i] = nums[i] - (nums[i] % 2 == 0 ? 1 : 0), the condition becomes that the sum of val over a subarray is zero. Thus, the task is equivalent to counting pairs of indices (i, j) with equal prefix sums of val. A naive O(n^2) double loop fails for large arrays because it examines every subarray individually. The optimal paradigm uses a single pass to compute prefix sums and a hash map to record frequencies of each prefix sum. Each new prefix sum can be matched against previously seen sums in O(1) time, yielding an overall O(n) algorithm with O(n) auxiliary space.

This approach is a classic application of the "prefix sum + hashmap" pattern, often used in subarray sum problems such as "Subarray Sum Equals K". The key insight is that the equality condition can be expressed as a difference of two cumulative values, allowing us to transform the problem into counting equal prefix sums. By storing counts of prefix sums in a hash map, we avoid recomputing sums for every subarray, drastically reducing time complexity.

The algorithm also handles negative numbers and zeros seamlessly because the transformation and prefix sum logic are independent of sign. Since the hashmap stores integer keys, the space requirement remains linear in the number of distinct prefix sums, which is at most n+1 for an array of length n.

Interview Questions on This Problem

Q1How would you modify the algorithm if the array contains floating-point numbers and you need subarrays where the sum equals the count of even integers within a tolerance of 0.01?

You would first convert each element to the transformed value val[i] = nums[i] - (isEven(nums[i]) ? 1 : 0). Then, instead of looking for exact zero sums, you would maintain a hashmap of prefix sums rounded to two decimal places or use a balanced BST to query sums within the tolerance window. Each new prefix sum would be checked against existing sums that fall within ±0.01, counting matches accordingly. This adds a logarithmic factor for the range query but preserves linear overall complexity for practical input sizes.

Q2During a recent interview at a fintech startup, the interviewer asked: "Can you explain why the prefix sum approach works for this problem and what would happen if you used a sliding window instead?"

The prefix sum approach works because the condition sum(subarray) == evenCount(subarray) can be rewritten as sum(val) == 0, where val[i] = nums[i] - isEven(nums[i]). Prefix sums capture cumulative differences, so equal prefix sums indicate a zero-sum subarray. A sliding window would only work for non-negative transformed values; since val can be negative, the window size is not monotonic, making it impossible to maintain a fixed window without rechecking all possibilities. Thus, sliding window fails to guarantee correctness.

Q3A senior engineer at a high-growth startup asked: "If we need to support streaming data, how would you adapt the algorithm to count subarrays in real time?"

For streaming data, maintain a running prefix sum and a hash map of prefix sum frequencies. As each new element arrives, update the prefix sum, increment the answer by the current frequency of that sum, and then increment the frequency in the map. This allows O(1) amortized update per element, enabling real-time counting of qualifying subarrays.

Examples

Example 1

Input

[2, 3, 4]

Output

Explanation: Step-by-step: We first initialize two pointers, left and right, to 0. We then calculate the sum of the subarray from left to right and the count of even elements in that subarray. If the sum is equal to the count of even elements, we increment the count of subarrays. We then move the right pointer to the right and repeat the process until the right pointer is at the end of the array. Finally, we return the count of subarrays.

Example 2

Input

[0, 2, 0]

Output

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Traverse the array once, maintaining a running prefix sum of num - isEven(num). Use a hash map to store frequencies of each prefix sum. For each new prefix sum, add the current frequency to the answer and then increment the frequency. This runs in O(n) time and O(n) space.

Brute Force Approach

Check every possible subarray by nested loops, compute its sum and count of even numbers, and increment the answer if they match. This takes O(n²) time and O(1) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) {
   let count = 0;
   let left = 0;
   let sum = 0;
   let evenCount = 0;
   for (let right = 0; right < nums.length; right++) {
       sum += nums[right];
       if (nums[right] % 2 === 0) {
           evenCount++;
       }
       while (sum < evenCount) {
           sum -= nums[left];
           if (nums[left] % 2 === 0) {
               evenCount--;
           }
           left++;
       }
       if (sum === evenCount) {
           count++;
       }
   }
   return count;
}

class Solution {
   public:
       int solution(vector<int>& nums) {
           int count = 0;
           int left = 0;
           int sum = 0;
           int evenCount = 0;
           for (int right = 0; right < nums.size(); right++) {
               sum += nums[right];
               if (nums[right] % 2 == 0) {
                   evenCount++;
               }
               while (sum < evenCount) {
                   sum -= nums[left];
                   if (nums[left] % 2 == 0) {
                       evenCount--;
                   }
                   left++;
               }
               if (sum == evenCount) {
                   count++;
               }
           }
           return count;
       }
   };

class Solution {
   public int solution(int[] nums) {
       int count = 0;
       int left = 0;
       int sum = 0;
       int evenCount = 0;
       for (int right = 0; right < nums.length; right++) {
           sum += nums[right];
           if (nums[right] % 2 == 0) {
               evenCount++;
           }
           while (sum < evenCount) {
               sum -= nums[left];
               if (nums[left] % 2 == 0) {
                   evenCount--;
               }
               left++;
           }
           if (sum == evenCount) {
               count++;
           }
       }
       return count;
   }
}

def solution(nums):
   count = 0
   left = 0
   sum = 0
   evenCount = 0
   for right in range(len(nums)):
       sum += nums[right]
       if nums[right] % 2 == 0:
           evenCount += 1
       while sum < evenCount:
           sum -= nums[left]
           if nums[left] % 2 == 0:
               evenCount -= 1
           left += 1
       if sum == evenCount:
           count += 1
   return count

function solution(nums) {
   let count = 0;
   let left = 0;
   let sum = 0;
   let evenCount = 0;
   for (let right = 0; right < nums.length; right++) {
       sum += nums[right];
       if (nums[right] % 2 === 0) {
           evenCount++;
       }
       while (sum < evenCount) {
           sum -= nums[left];
           if (nums[left] % 2 === 0) {
               evenCount--;
           }
           left++;
       }
       if (sum === evenCount) {
           count++;
       }
   }
   return count;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Subarrays with Sum Equal to Even Count Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Subarrays with Sum Equal to Even Count — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor