Skip to main content
Talentd

Count Smaller Elements With Opposite Parity - Solution & Explanation

MediumPremiumFree on FleetCode7 min read
Practice this problem

Problem Statement

You are given an integer array nums of length n.

The score of an index i is defined as the number of indices j such that:

  • i < j < n
  • nums[j] < nums[i]
  • nums[i] and nums[j] have different parity (one is even and the other is odd).

Return an integer array answer of length n, where answer[i] is the score of index i.

 

Example 1:

Input: nums = [5,2,4,1,3]

Output: [2,1,2,0,0]

Explanation:

  • For i = 0, the elements nums[1] = 2 and nums[2] = 4 are smaller and have different parity.
  • For i = 1, the element nums[3] = 1 is smaller and has different parity.
  • For i = 2, the elements nums[3] = 1 and nums[4] = 3 are smaller and have different parity.
  • No valid elements exist for the remaining indices.

Thus, the answer = [2, 1, 2, 0, 0].

Example 2:

Input: nums = [4,4,1]

Output: [1,1,0]

Explanation:ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

For i = 0 and i = 1, the element nums[2] = 1 is smaller and has different parity. Thus, the answer = [1, 1, 0].

Example 3:

Input: nums = [7]

Output: [0]

Explanation:

No elements exist to the right of index 0, so its score is 0. Thus, the answer = [0].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Approach Overview

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.

Solution

We can use two ordered lists (or Binary Indexed Trees) to separately maintain even and odd elements. For each element, we query the number of smaller elements in the other list, and then add the current element to its corresponding list.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(nĀ²)O(1)Small arrays or quick correctness validation
Sorting with Prefix Parity CountsO(n log n)O(n)General case where ordering helps count smaller elements efficiently
Fenwick Tree / Binary Indexed TreeO(n log n)O(n)When processing streaming data or performing repeated smaller-element queries

Frequently Asked Questions

Is Count Smaller Elements With Opposite Parity easy or hard?
The problem is usually categorized as Medium because it combines two ideas: ordering elements and filtering by parity. The brute force solution is simple, but recognizing that sorting or prefix counting reduces the complexity is the key step.
Count Smaller Elements With Opposite Parity Python/Java solution
Typical implementations sort the array and maintain two counters: one for even numbers and one for odd numbers. While scanning the sorted list, query the counter of the opposite parity to compute the result, then update the current parity counter. This pattern translates directly to Python, Java, and C++ with identical logic.
How to solve Count Smaller Elements With Opposite Parity in O(n)?
Pure O(n) solutions are uncommon unless the value range is small enough for counting arrays. If values are bounded, you can maintain frequency counts for even and odd numbers and compute prefix totals directly. In the general case with arbitrary integers, sorting or a Fenwick Tree leads to O(n log n) complexity.
What is the best approach for Count Smaller Elements With Opposite Parity?
The most practical solution sorts the numbers and keeps running counts of odd and even values encountered so far. Because the array is processed in ascending order, every processed element is guaranteed to be smaller. Checking parity determines which counter to use. This approach runs in O(n log n) time due to sorting and uses O(n) space.
Is Count Smaller Elements With Opposite Parity asked at Google/Amazon/Meta?
Problems involving counting smaller elements and parity filtering appear frequently in technical interviews. Variants of this pattern show up at companies like Amazon, Google, and Meta when discussing order statistics, prefix counting, or Binary Indexed Tree usage.
What data structure is used in Count Smaller Elements With Opposite Parity?
Common implementations rely on sorting plus simple counters for odd and even values. More advanced solutions use a Fenwick Tree (Binary Indexed Tree) or segment tree to support efficient prefix queries while tracking parity groups.
What is the time complexity of Count Smaller Elements With Opposite Parity?
The brute force method compares every pair of elements and runs in O(n^2) time with O(1) space. The optimized solution sorts the array and tracks parity counts, reducing the complexity to O(n log n). Advanced implementations using Fenwick Trees also run in O(n log n).

Ready to solve this problem?

Practice Count Smaller Elements With Opposite Parity with our built-in code editor and test cases.

Practice on FleetCode