Skip to main content
Talentd

Count Subarrays With Even Odd Ratio II - Solution & Explanation

HardArrayDivide and ConquerBinary Indexed TreeSegment Tree14 min read
Practice this problem

Problem Statement

You are given an integer array nums and two integers a and b.

For a subarray, let:

  • x be the number of even elements.
  • y be the number of odd elements.

The ratio of even to odd elements in a subarray is defined as x / y, where ratios are compared by their exact rational values.

A subarray is considered valid if:

  • y > 0, and
  • x / y <= a / b.

Return the number of valid subarrays in nums.

 

Example 1:

Input: nums = [1,2,1,2], a = 3, b = 2

Output: 7

Explanation:

The following are the valid subarrays:

Subarray Values Even Count Odd Count Ratio
nums[0..0] [1] 0 1 0 / 1
nums[0..1] [1, 2] 1 1 1 / 1
nums[0..2] [1, 2, 1] 1 2 1 / 2
nums[0..3] [1, 2, 1, 2] 2 2 2 / 2
nums[1..2] [2, 1] 1 1 1 / 1
nums[2..2] [1] 0 1 0 / 1
nums[2..3] [1, 2] 1 1 1 / 1

Thus, the number of valid subarrays is 7.

Example 2:

Input: nums = [2,2,1], a = 2, b = 1

Output: 3

Explanation:

The following are the valid subarrays:

Subarray Values Even Count Odd Count Ratio
nums[0..2] [2, 2, 1] 2 1 2 / 1
nums[1..2] [2, 1] 1 1 1 / 1
nums[2..2] [1] 0 1 0 / 1

Thus, the number of valid subarrays is 3.

Example 3:

Input: nums = [2,2,2], a = 1, b = 1

Output: 0

Explanation:

Every subarray contains 0 odd numbers, so no subarray is valid.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= a, b <= 109​​​​​​​

Approach Overview

Problem Overview: You need to count the number of subarrays in which the ratio of even to odd numbers satisfies a given condition.

Approach 1: Brute Force (O(n^2))

Iterate through all possible subarrays and count the even and odd numbers in each. Check if the ratio meets the condition. This approach is straightforward but inefficient for large arrays.

Approach 2: Prefix Sum with Hash Map (O(n))

Use a prefix sum array to store cumulative counts of even and odd numbers. Employ a hash map to store the frequency of specific ratios. This allows you to efficiently count valid subarrays in linear time. This is the optimal approach for large datasets.

Recommended for interviews: Interviewers expect you to discuss the brute force approach to show understanding, but the optimal solution using prefix sum and hash map demonstrates advanced problem-solving skills.

Solution

For a subarray, let x be the number of even elements and y be the number of odd elements. The problem requires y > 0 and \frac{x}{y} \le \frac{a}{b}. Since b > 0 and y > 0, the inequality is equivalent to a cdot y - b cdot x \ge 0.

When y = 0, since the subarray is non-empty, we must have x > 0. In this case, a cdot y - b cdot x = -b cdot x < 0, so the inequality does not hold. Therefore, the two conditions in the problem can be merged into a single one: a cdot y - b cdot x \ge 0.

We treat the odd numbers in nums as a and the even numbers as -b, resulting in an array arr. The original problem is then equivalent to counting the number of non-empty contiguous subarrays of arr whose element sum is at least 0.

Let s be the prefix sum array of arr. The element sum of the subarray [L, R - 1] equals s[R] - s[L], so the problem is further transformed into: how many index pairs (L, R) satisfy 0 \le L < R \le n and s[R] - s[L] \ge 0, i.e., s[L] \le s[R]?

We enumerate R and need to quickly count the number of indices L to the left of R that satisfy s[L] \le s[R]. This can be maintained with a Binary Indexed Tree: we first discretize all values in s (sort and deduplicate), then traverse s from left to right. For each value v = s[R], we query the number of inserted elements not greater than v from the Binary Indexed Tree and add it to the answer, then insert v into the tree.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)Small arrays
Prefix Sum with Hash MapO(n)O(n)Large arrays

Video Solution

Super Hard💀DSA Question asked by Leetcode in Weekly Contest 513(Q4,4013) • DSA with Kumar K • 492 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Count Subarrays With Even Odd Ratio II easy or hard?
This problem is classified as hard due to its requirement for an optimal O(n) solution.
Count Subarrays With Even Odd Ratio II Python/Java solution
Solutions in Python and Java are available on FleetCode, using the prefix sum and hash map approach.
How to solve Count Subarrays With Even Odd Ratio II in O(n)?
Use a prefix sum array to track cumulative counts of even and odd numbers and a hash map to store frequency of specific ratios.
What is the best approach for Count Subarrays With Even Odd Ratio II?
The best approach is using prefix sum with a hash map, which achieves O(n) time complexity.
Is Count Subarrays With Even Odd Ratio II asked at Google/Amazon/Meta?
Yes, this problem is known to be asked at top tech companies like Google, Amazon, and Meta.
What data structure is used in Count Subarrays With Even Odd Ratio II?
A hash map is used to store the frequency of specific ratios in the optimal solution.
What is the time complexity of Count Subarrays With Even Odd Ratio II?
The optimal time complexity is O(n) using the prefix sum and hash map approach.

Ready to solve this problem?

Practice Count Subarrays With Even Odd Ratio II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Subarrays With Even Odd Ratio I