Review the fundamentals: Arrays guide and time complexities.
Count Subarrays with Bounded Odd Surplus — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Prefix Sums, Subarray State Transformation, Hash Map Counting
O(n log n)O(n)Problem Description
Given an integer array nums and an integer k. The "odd surplus" of a contiguous subarray is defined as the count of odd elements minus the count of even elements within that subarray. Return the total number of contiguous subarrays that have an odd surplus of at least 1 and at most k.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Subarrays with Bounded Odd Surplus"
WHY DOES IT MATTER?
Counting bounded‑sum subarrays appears in many range‑query and frequency‑analysis problems.
OPTIMIZATION CHALLENGE
The key is reducing O(n²) enumeration to O(n log n) by turning the problem into prefix‑sum range counting.
REAL-WORLD CONNECTION
It mirrors monitoring net request deltas where positive events (odd) must not exceed a threshold over negatives (even).
Always compress prefix values first; it guarantees the BIT size stays linear and avoids large sparse arrays.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The naive solution enumerates every subarray, computes its odd‑minus‑even count, and checks the bound, leading to O(n²) time which explodes for n up to 10⁵. By mapping each element to +1 (odd) or -1 (even), the problem becomes counting subarrays whose sum lies in the interval [1, k].
Using prefix sums, a subarray sum equals prefix[j]‑prefix[i]; thus we need, for each j, the number of earlier i with prefix[i] in [prefix[j]‑k, prefix[j]‑1]. This is a classic range‑frequency query on a dynamic multiset, solvable in O(log n) per element with a Fenwick tree or balanced BST after coordinate compression, yielding an overall O(n log n) algorithm.
Interview Questions on This Problem
Q1How do you transform the original odd/even condition into a numeric subarray‑sum problem?
Replace each odd number with +1 and each even number with -1. The odd surplus of a subarray then equals the sum of its transformed values.
Q2Why can’t a sliding‑window two‑pointer technique solve this problem?
The transformed values can be negative, so the window sum is not monotonic when expanding or shrinking, breaking the invariant needed for two‑pointer.
Q3What data structure enables O(log n) queries of “how many previous prefix sums lie in a given range?”
A Fenwick tree (Binary Indexed Tree) or an ordered map with binary search after coordinate compression. Both support prefix‑count queries in logarithmic time.
Examples
Input
nums = [1, 2, 3], k = 1
Output
3
Explanation: The valid odd surplus must be exactly 1. The valid subarrays are [1] (surplus = 1), [3] (surplus = 1), and [1, 2, 3] (surplus = 2 - 1 = 1).
Input
nums = [1, 1, 2, 1], k = 2
Output
7
Explanation: Subarrays with a surplus of 1 or 2 are valid. These are [1] (at three different positions), [1, 1], [1, 1, 2], [1, 2, 1], and [1, 1, 2, 1].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= nums.length
Optimal Approach & Strategy
Convert to +1/‑1, maintain prefix sums, and use a Fenwick tree (or balanced BST) with coordinate compression to count prior prefixes in the required range for each position.
Brute Force Approach
Enumerate all O(n²) subarrays, compute odd‑minus‑even for each, and check if it lies in [1, k].
Code Solutions
function countSubarraysWithBoundedOddSurplus(nums, k) {
const n = nums.length;
const bitSize = 2 * n + 5;
const tree = new Int32Array(bitSize);
const offset = n + 1;
function update(idx, val) {
while (idx < bitSize) {
tree[idx] += val;
idx += idx & -idx;
}
}
function query(idx) {
let sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
function queryRange(l, r) {
if (l > r) return 0;
return query(r) - query(l - 1);
}
let ans = 0;
let currSum = 0;
update(currSum + offset, 1);
for (let i = 0; i < n; i++) {
const val = (nums[i] % 2 !== 0) ? 1 : -1;
currSum += val;
const l = currSum - k;
const r = currSum - 1;
ans += queryRange(l + offset, r + offset);
update(currSum + offset, 1);
}
return ans;
}#include <vector>
#include <algorithm>
class Solution {
private:
int bitSize;
std::vector<int> tree;
void update(int idx, int val) {
if (idx <= 0) return;
for (; idx < bitSize; idx += idx & -idx) {
tree[idx] += val;
}
}
int query(int idx) {
if (idx <= 0) return 0;
if (idx >= bitSize) idx = bitSize - 1;
int sum = 0;
for (; idx > 0; idx -= idx & -idx) {
sum += tree[idx];
}
return sum;
}
int queryRange(int l, int r) {
if (l > r) return 0;
return query(r) - query(l - 1);
}
public:
long long countSubarraysWithBoundedOddSurplus(std::vector<int>& nums, int k) {
int n = nums.size();
bitSize = 2 * n + 5;
tree.assign(bitSize, 0);
int offset = n + 1;
long long ans = 0;
int currSum = 0;
update(currSum + offset, 1);
for (int num : nums) {
int val = (num % 2 != 0) ? 1 : -1;
currSum += val;
int l = currSum - k;
int r = currSum - 1;
ans += queryRange(l + offset, r + offset);
update(currSum + offset, 1);
}
return ans;
}
};import java.util.*;
class Solution {
private int bitSize;
private int[] tree;
private void update(int idx, int val) {
while (idx < bitSize) {
tree[idx] += val;
idx += idx & -idx;
}
}
private int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
private int queryRange(int l, int r) {
if (l > r) return 0;
l = Math.max(1, l);
r = Math.min(bitSize - 1, r);
if (l > r) return 0;
return query(r) - query(l - 1);
}
public long countSubarraysWithBoundedOddSurplus(int[] nums, int k) {
int n = nums.length;
bitSize = 2 * n + 5;
tree = new int[bitSize];
int offset = n + 1;
long ans = 0;
int currSum = 0;
update(currSum + offset, 1);
for (int num : nums) {
int val = (num % 2 != 0) ? 1 : -1;
currSum += val;
int l = currSum - k;
int r = currSum - 1;
ans += queryRange(l + offset, r + offset);
update(currSum + offset, 1);
}
return ans;
}
}def count_subarrays_with_bounded_odd_surplus(nums: list[int], k: int) -> int:
n = len(nums)
if n == 0:
return 0
offset = n + 1
bit_size = 2 * n + 5
tree = [0] * bit_size
def update(idx, val):
while idx < bit_size:
tree[idx] += val
idx += idx & -idx
def query(idx):
s = 0
while idx > 0:
s += tree[idx]
idx -= idx & -idx
return s
def query_range(l, r):
if l > r:
return 0
return query(r) - query(l - 1)
ans = 0
curr_sum = 0
update(curr_sum + offset, 1)
for num in nums:
val = 1 if num % 2 != 0 else -1
curr_sum += val
l = max(-n, curr_sum - k)
r = min(n, curr_sum - 1)
ans += query_range(l + offset, r + offset)
update(curr_sum + offset, 1)
return ansfunction countSubarraysWithBoundedOddSurplus(nums, k) {
const n = nums.length;
const bitSize = 2 * n + 5;
const tree = new Int32Array(bitSize);
const offset = n + 1;
function update(idx, val) {
while (idx < bitSize) {
tree[idx] += val;
idx += idx & -idx;
}
}
function query(idx) {
let sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
function queryRange(l, r) {
if (l > r) return 0;
return query(r) - query(l - 1);
}
let ans = 0;
let currSum = 0;
update(currSum + offset, 1);
for (let i = 0; i < n; i++) {
const val = (nums[i] % 2 !== 0) ? 1 : -1;
currSum += val;
const l = currSum - k;
const r = currSum - 1;
ans += queryRange(l + offset, r + offset);
update(currSum + offset, 1);
}
return ans;
}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.