Count Smaller Elements With Opposite Parity - Solution & Explanation

Problem Overview: You are given an array of integers and need to count how many elements are smaller than a given value while also having the opposite parity (odd vs even). The core challenge is efficiently comparing values while filtering by parity.

Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)

Check every pair of elements using two nested loops. For each element nums[i], iterate through the entire array and test two conditions: the other value must be smaller and its parity must be opposite. Parity can be checked with x % 2. This approach directly models the problem and is easy to reason about, but the quadratic time becomes slow once the array grows beyond a few thousand elements.

Approach 2: Sorting with Prefix Parity Counts (O(n log n) time, O(n) space)

Sort the numbers while keeping track of their original values. As you scan the sorted array from smallest to largest, maintain running counts of how many odd and even numbers you have already processed. For the current number, if it is even, the answer is the number of previously seen odd values; if it is odd, use the count of even values. Because the array is processed in increasing order, all processed values are guaranteed to be smaller. Sorting dominates the complexity at O(n log n). This pattern combines ordering with fast category counting.

Approach 3: Fenwick Tree / Binary Indexed Tree (O(n log n) time, O(n) space)

When the problem requires dynamic queries or maintaining counts while processing values in arbitrary order, a Fenwick Tree works well. First apply coordinate compression so values map to a compact range. Maintain two trees: one for even values and one for odd values. For each number, query the tree of the opposite parity to count how many elements with smaller compressed indices have appeared. Then update the current parity tree. This approach is common in problems related to prefix sums and order statistics.

Recommended for interviews: Start with the brute force explanation to demonstrate understanding of the parity condition and comparison logic. Then move to the sorting + prefix counting approach. It reduces the complexity from O(n²) to O(n log n) and uses a simple counting technique that interviewers expect when combining ordering with category tracking. Advanced discussions may reference a Binary Indexed Tree for scalable range queries.