LeetCode Problem 2495

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

LeetCode 2495 - Number of Subarrays Having Even Product

Problem Understanding

The problem gives us an integer array nums and asks us to count how many contiguous subarrays have an even product.

A subarray is a continuous segment of the array. For each possible subarray, we compute the product of all its elements. If that product is even, then the subarray contributes to the final answer.

The key mathematical observation is that a product is even if and only if at least one number in the product is even. This property completely changes how we think about the problem. Instead of multiplying numbers together, which could become expensive and unnecessary, we only need to determine whether a subarray contains an even number.

The input constraints are important:

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

An array of size 10^5 means an O(n^2) solution will be far too slow in the worst case. There are roughly 10^10 possible subarrays in that scenario, which is not computationally feasible.

The problem guarantees that all numbers are positive integers, so we do not need to worry about zeros, negative values, or floating point behavior.

Several edge cases are important:

• Arrays containing only odd numbers, because the answer should be 0
• Arrays containing only even numbers, because every subarray is valid
• Arrays with a single element
• Arrays where even numbers appear sparsely
• Very large arrays, where performance matters significantly

A naive implementation that explicitly computes every product would be extremely inefficient and could also risk integer overflow in some languages.

Approaches

Brute Force Approach

The brute force solution examines every possible subarray.

For each starting index i, we extend the subarray one element at a time toward the right. We maintain the running product and check whether it is even.

This approach is correct because it explicitly evaluates every possible contiguous subarray and counts exactly those whose product is even.

However, the performance is poor. There are O(n^2) subarrays, and even with incremental multiplication, the algorithm still requires quadratic time. With n = 10^5, this becomes impractical.

Another issue is that repeatedly multiplying values creates unnecessary work. Since parity alone determines whether a product is even, computing the full product is wasteful.

Optimal Approach

The key insight is:

A product is even if the subarray contains at least one even number.

This means we do not need to compute products at all.

Instead, for every position in the array, we determine how many subarrays ending at that position contain an even number.

Suppose we are at index i:

• If nums[i] is even, then every subarray ending at i has an even product, because the current element itself guarantees evenness.
• If nums[i] is odd, then only subarrays that already contained a previous even number remain valid.

We can track the most recent even index encountered. Once we know the latest even position, we immediately know how many subarrays ending at the current index are valid.

This leads to a simple linear time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Enumerates all subarrays and checks products
Optimal	O(n)	O(1)	Tracks the most recent even index

Algorithm Walkthrough

1. Initialize a variable last_even_index to -1.

This variable stores the index of the most recent even number seen so far. If no even number has appeared yet, it remains -1. 2. Initialize a variable answer to 0.

This will accumulate the total number of valid subarrays. 3. Traverse the array from left to right using index i. 4. For each element:

• If nums[i] is even, update last_even_index = i.
• This means every subarray ending at i and starting anywhere from 0 to i will contain at least one even number.

5. Add last_even_index + 1 to the answer.

Why does this work?

• If the latest even number is at index k, then every subarray ending at i and starting at any position from 0 through k contains that even number.
• There are exactly k + 1 such starting positions.

6. Continue until the entire array has been processed.
7. Return the accumulated answer.

Why it works

The algorithm maintains the invariant that last_even_index always stores the most recent even number before or at the current position.

For every index i, a subarray ending at i has an even product if and only if its range includes at least one even number. Since the latest even number is sufficient to determine all valid starting positions, counting last_even_index + 1 precisely counts all valid subarrays ending at i.

Because every valid subarray is counted exactly once, the algorithm produces the correct result.

Python Solution

from typing import List

class Solution:
    def evenProduct(self, nums: List[int]) -> int:
        last_even_index = -1
        total_subarrays = 0

        for index, value in enumerate(nums):
            if value % 2 == 0:
                last_even_index = index

            total_subarrays += last_even_index + 1

        return total_subarrays

The implementation closely follows the algorithm described earlier.

The variable last_even_index tracks the latest position where an even number appeared. Initially, it is set to -1 because no even numbers have been seen.

As we iterate through the array, each even value updates this index.

For every position, we add last_even_index + 1 to the total count. This directly represents how many subarrays ending at the current position contain at least one even number.

The implementation uses only constant extra memory and processes the array exactly once.

Go Solution

func evenProduct(nums []int) int64 {
    lastEvenIndex := -1
    var totalSubarrays int64 = 0

    for i, value := range nums {
        if value%2 == 0 {
            lastEvenIndex = i
        }

        totalSubarrays += int64(lastEvenIndex + 1)
    }

    return totalSubarrays
}

The Go implementation mirrors the Python solution very closely.

One important difference is the return type. The function returns int64 because the number of subarrays can become very large. For an array of size 10^5, the total number of subarrays can exceed the range of a standard 32 bit integer.

Go slices naturally represent dynamic arrays, so no special handling is needed for memory allocation.

Worked Examples

Example 1

Input: nums = [9,6,7,13]

We process the array step by step.

Index	Value	Even?	last_even_index	Added Count	Total
0	9	No	-1	0	0
1	6	Yes	1	2	2
2	7	No	1	2	4
3	13	No	1	2	6

Final answer:

6

The valid subarrays are:

• [9,6]
• [9,6,7]
• [9,6,7,13]
• [6]
• [6,7]
• [6,7,13]

Example 2

Input: nums = [7,3,5]

Index	Value	Even?	last_even_index	Added Count	Total
0	7	No	-1	0	0
1	3	No	-1	0	0
2	5	No	-1	0	0

Final answer:

0

No subarray contains an even number, so every product remains odd.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed once
Space	O(1)	Only a few variables are used

The algorithm performs constant work per element, making the runtime linear in the size of the array.

No auxiliary data structures proportional to input size are required, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def evenProduct(self, nums: List[int]) -> int:
        last_even_index = -1
        total_subarrays = 0

        for index, value in enumerate(nums):
            if value % 2 == 0:
                last_even_index = index

            total_subarrays += last_even_index + 1

        return total_subarrays

solution = Solution()

assert solution.evenProduct([9,6,7,13]) == 6  # Provided example with one even number
assert solution.evenProduct([7,3,5]) == 0  # All odd numbers
assert solution.evenProduct([2]) == 1  # Single even element
assert solution.evenProduct([1]) == 0  # Single odd element
assert solution.evenProduct([2,4,6]) == 6  # Every subarray is valid
assert solution.evenProduct([1,2,3]) == 4  # Even number in the middle
assert solution.evenProduct([1,3,5,2]) == 4  # Even number at the end
assert solution.evenProduct([2,1,1,1]) == 4  # Even number at the start
assert solution.evenProduct([1,1,2,1,1]) == 9  # Sparse even occurrence
assert solution.evenProduct([2,2,2,2]) == 10  # All even numbers

Test	Why
[9,6,7,13]	Verifies the provided example
[7,3,5]	Ensures all odd arrays return zero
[2]	Smallest valid even case
[1]	Smallest valid odd case
[2,4,6]	Every subarray should be counted
[1,2,3]	Tests an even value in the middle
[1,3,5,2]	Tests an even value at the end
[2,1,1,1]	Tests an even value at the beginning
[1,1,2,1,1]	Verifies propagation of valid subarrays
[2,2,2,2]	Dense even distribution

Edge Cases

One important edge case occurs when the array contains only odd numbers. In this situation, no subarray can have an even product because multiplying odd numbers always produces another odd number. The implementation handles this naturally because last_even_index remains -1, causing zero to be added at every step.

Another critical edge case is when every number is even. In this case, every possible subarray is valid. The algorithm correctly counts all subarrays because every position updates last_even_index, and all subarrays ending at each index become valid.

A third important case is when there is exactly one even number in the array. This can be tricky because only subarrays that include that specific index should be counted. The implementation handles this efficiently by remembering the latest even position and counting all starting positions up to that index.

Large inputs also matter because quadratic solutions will time out. Since the implementation processes each element exactly once and uses constant extra memory, it scales efficiently to the maximum constraint size of 10^5.