3907. Count Smaller Elements With Opposite Parity 🔒

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

The score of an index i is defined as the number of indices j that satisfy all of the following conditions at the same time:

i < j < n — the index j comes strictly after i.
nums[j] < nums[i] — the value at j is strictly smaller than the value at i.
nums[i] and nums[j] have different parity — one of them is even and the other is odd.

In other words, for each index i, you look at every element to its right, and count how many of those elements are both smaller in value and have the opposite parity (even vs. odd) compared to nums[i].

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

The straightforward way to solve this problem is to check, for each index i, every index j to its right and count how many satisfy the three conditions. This brute-force approach takes O(n^2) time, which can be too slow when n is large.

To speed things up, let's focus on what we actually need to count. For a given index i, we want the number of elements to the right that are both smaller than nums[i] and have opposite parity. Two observations help us here:

Whether an element has opposite parity only depends on whether it is even or odd. So we can group the elements to the right into two buckets: one for even values and one for odd values.
"Smaller than nums[i]" is a range query. If the elements in a bucket are kept in sorted order, then counting how many are smaller than a given value becomes a fast binary search.

This naturally leads to processing the array from right to left. As we move leftward, every element we have already seen is "to the right" of the current index i. So if we maintain two sorted structures — one holding all even values seen so far and one holding all odd values seen so far — then for the current element nums[i] we simply:

Look in the bucket of opposite parity (if nums[i] is even, look in the odd bucket, and vice versa).
Count how many values in that bucket are strictly smaller than nums[i]. With a sorted list, this is just bisect_left(nums[i]).

After computing the score for i, we insert nums[i] into its own parity bucket so that it becomes available for indices further to the left.

The trick nums[i] & 1 gives the parity (0 for even, 1 for odd), and nums[i] & 1 ^ 1 flips it to select the opposite-parity bucket. By keeping each bucket sorted, each query and insertion runs in O(log n), reducing the overall time to O(n log n).

Solution Approach

We use the Ordered List technique to separately maintain even and odd elements seen so far. For each element, we query the number of smaller elements in the opposite-parity list, then add the current element to its own list.

Data Structures

We keep two SortedList instances inside a small array sl:

sl[0] holds all even values encountered so far.
sl[1] holds all odd values encountered so far.

Indexing by parity directly lets us pick the right bucket using a bit operation: nums[i] & 1 is 0 for even and 1 for odd.

Step-by-step walkthrough

Initialize n = len(nums) and an answer array ans = [0] * n.
Create the two sorted lists: sl = [SortedList(), SortedList()].
Iterate i from n - 1 down to 0. Processing right to left guarantees that everything already stored in sl lies at an index greater than i, which satisfies the i < j < n requirement automatically.
For the current element nums[i]:
- Compute its opposite parity index with nums[i] & 1 ^ 1. If nums[i] is even (& 1 == 0), this gives 1 (the odd list); if it is odd, this gives 0 (the even list).
- Query that opposite-parity list with bisect_left(nums[i]). Since the list is sorted, bisect_left returns exactly how many stored values are strictly smaller than nums[i]. This count is the score, so we set ans[i].
After recording the score, insert the current value into its own parity bucket with sl[nums[i] & 1].add(nums[i]), making it available for indices further to the left.
Once the loop finishes, return ans.

Why it works

Each index i only needs the count of smaller, opposite-parity values to its right. By processing from the right and grouping values by parity in sorted order, the parity condition is handled by choosing the correct bucket, while the "smaller than" condition is handled by a binary search.

Complexity

Time: O(n log n). Each of the n iterations performs one bisect_left and one add, both O(log n) on a SortedList.
Space: O(n) for the two ordered lists holding all elements plus the answer array.

A Binary Indexed Tree (Fenwick Tree) could replace the ordered lists with the same overall complexity: maintain two trees indexed by value (after coordinate compression), query the prefix count of smaller values, and update the count for the current value.

Example Walkthrough

Let's trace through the solution with the small input:

nums = [4, 3, 1, 2]   (n = 4)

We process indices from right to left and keep two sorted lists:

sl[0] → even values seen so far
sl[1] → odd values seen so far

We start with ans = [0, 0, 0, 0], sl[0] = [], sl[1] = [].

Step 1: i = 3, nums[3] = 2 (even, parity 0)

Opposite parity index: 2 & 1 ^ 1 = 0 ^ 1 = 1 → look in the odd list sl[1] = [].
bisect_left(2) on [] → 0. So ans[3] = 0.
Insert 2 into its own bucket sl[0].

State: sl[0] = [2], sl[1] = [], ans = [0, 0, 0, 0]

Step 2: i = 2, nums[2] = 1 (odd, parity 1)

Opposite parity index: 1 & 1 ^ 1 = 1 ^ 1 = 0 → look in the even list sl[0] = [2].
bisect_left(1) on [2] → 0 (no even value is strictly smaller than 1). So ans[2] = 0.
Insert 1 into its own bucket sl[1].

State: sl[0] = [2], sl[1] = [1], ans = [0, 0, 0, 0]

Step 3: i = 1, nums[1] = 3 (odd, parity 1)

Opposite parity index: 3 & 1 ^ 1 = 0 → look in the even list sl[0] = [2].
bisect_left(3) on [2] → 1 (the value 2 is smaller than 3 and even). So ans[1] = 1.
Insert 3 into its own bucket sl[1].

State: sl[0] = [2], sl[1] = [1, 3], ans = [0, 1, 0, 0]

Step 4: i = 0, nums[0] = 4 (even, parity 0)

Opposite parity index: 4 & 1 ^ 1 = 1 → look in the odd list sl[1] = [1, 3].
bisect_left(4) on [1, 3] → 2 (both 1 and 3 are smaller than 4 and odd). So ans[0] = 2.
Insert 4 into its own bucket sl[0].

State: sl[0] = [2, 4], sl[1] = [1, 3], ans = [2, 1, 0, 0]

Final Result

ans = [2, 1, 0, 0]

Verification (brute force):

i = 0 (nums[0] = 4, even): elements to the right are 3, 1, 2. Smaller and odd → 3 and 1 → count 2. ✓
i = 1 (nums[1] = 3, odd): elements to the right are 1, 2. Smaller and even → 2 → count 1. ✓
i = 2 (nums[2] = 1, odd): elements to the right are 2. Smaller and even → none (2 > 1) → count 0. ✓
i = 3 (nums[3] = 2, even): no elements to the right → count 0. ✓

The walkthrough confirms how choosing the opposite-parity bucket handles the parity condition, while bisect_left over a sorted list handles the "strictly smaller" condition in O(log n) per index.

Solution Implementation

1from sortedcontainers import SortedList
2
3
4class Solution:
5    def countSmallerOppositeParity(self, nums: list[int]) -> list[int]:
6        n = len(nums)
7        ans = [0] * n
8
9        # Two sorted lists indexed by parity:
10        #   sorted_by_parity[0] -> even numbers seen so far (to the right)
11        #   sorted_by_parity[1] -> odd numbers seen so far (to the right)
12        sorted_by_parity = [SortedList(), SortedList()]
13
14        # Traverse from right to left so each list only holds
15        # elements located to the right of the current index.
16        for i in range(n - 1, -1, -1):
17            current_parity = nums[i] & 1          # 0 if even, 1 if odd
18            opposite_parity = current_parity ^ 1  # flip parity to look up the opposite list
19
20            # Count how many opposite-parity elements (already seen)
21            # are strictly smaller than nums[i].
22            ans[i] = sorted_by_parity[opposite_parity].bisect_left(nums[i])
23
24            # Record the current number in its own parity list
25            # so future (left-side) elements can count it.
26            sorted_by_parity[current_parity].add(nums[i])
27
28        return ans
29

1class BinaryIndexedTree {
2    // Size of the tree (number of valid indices, 1-based)
3    private int size;
4    // Internal storage for prefix sums (1-based indexing)
5    private int[] tree;
6
7    BinaryIndexedTree(int size) {
8        this.size = size;
9        this.tree = new int[size + 1];
10    }
11
12    /**
13     * Adds {@code delta} to the element at position {@code index}
14     * and propagates the change to all affected prefix nodes.
15     *
16     * @param index 1-based position to update
17     * @param delta value to add at that position
18     */
19    void update(int index, int delta) {
20        while (index <= size) {
21            tree[index] += delta;
22            // Move to the next node that covers this index
23            index += index & (-index);
24        }
25    }
26
27    /**
28     * Computes the prefix sum of all elements from index 1 to {@code index}.
29     *
30     * @param index 1-based upper bound (inclusive)
31     * @return the cumulative sum up to {@code index}
32     */
33    int query(int index) {
34        int sum = 0;
35        while (index > 0) {
36            sum += tree[index];
37            // Move to the parent node by stripping the lowest set bit
38            index -= index & (-index);
39        }
40        return sum;
41    }
42}
43
44class Solution {
45    /**
46     * For each element, counts how many elements to its right are
47     * both strictly smaller in value and of opposite parity (odd vs. even).
48     *
49     * @param nums the input array
50     * @return an array where ans[i] is the required count for nums[i]
51     */
52    public int[] countSmallerOppositeParity(int[] nums) {
53        int n = nums.length;
54
55        // Create a sorted copy used for coordinate compression
56        int[] sorted = nums.clone();
57        Arrays.sort(sorted);
58
59        // Remove duplicates in place; m is the count of distinct values
60        int m = 0;
61        for (int i = 0; i < n; i++) {
62            if (i == 0 || sorted[i] != sorted[i - 1]) {
63                sorted[m++] = sorted[i];
64            }
65        }
66
67        // Two Fenwick trees: index 0 tracks even numbers, index 1 tracks odd numbers
68        BinaryIndexedTree[] bit = {
69            new BinaryIndexedTree(m),
70            new BinaryIndexedTree(m)
71        };
72
73        int[] ans = new int[n];
74
75        // Traverse from right to left so the trees hold only "future" elements
76        for (int i = n - 1; i >= 0; i--) {
77            // Map nums[i] to its compressed 1-based rank
78            int x = Arrays.binarySearch(sorted, 0, m, nums[i]) + 1;
79
80            // Query the tree of the opposite parity for values strictly smaller than nums[i]
81            int oppositeParity = (nums[i] & 1) ^ 1;
82            ans[i] = bit[oppositeParity].query(x - 1);
83
84            // Insert the current element into the tree matching its own parity
85            int currentParity = nums[i] & 1;
86            bit[currentParity].update(x, 1);
87        }
88
89        return ans;
90    }
91}
92

1// Binary Indexed Tree (Fenwick Tree) for prefix sum queries and point updates
2struct BinaryIndexedTree {
3    int size;              // number of positions the tree covers
4    vector<int> tree;      // internal tree storage (1-indexed)
5
6    BinaryIndexedTree(int size)
7        : size(size)
8        , tree(size + 1, 0) {}
9
10    // Add delta to position pos, then propagate to affected nodes
11    void update(int pos, int delta) {
12        for (; pos <= size; pos += pos & -pos) {
13            tree[pos] += delta;
14        }
15    }
16
17    // Return the prefix sum over [1, pos]
18    int query(int pos) {
19        int sum = 0;
20        for (; pos > 0; pos -= pos & -pos) {
21            sum += tree[pos];
22        }
23        return sum;
24    }
25};
26
27class Solution {
28public:
29    vector<int> countSmallerOppositeParity(vector<int>& nums) {
30        int n = nums.size();
31
32        // Coordinate compression: build a sorted, deduplicated list of values
33        vector<int> sortedValues = nums;
34        sort(sortedValues.begin(), sortedValues.end());
35        sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()),
36                           sortedValues.end());
37
38        int m = sortedValues.size();
39
40        // Two BITs: one for even numbers, one for odd numbers
41        // bits[0] tracks even values, bits[1] tracks odd values
42        BinaryIndexedTree* bits[2] = {
43            new BinaryIndexedTree(m),
44            new BinaryIndexedTree(m)
45        };
46
47        vector<int> ans(n);
48
49        // Traverse from right to left so the BITs hold elements to the right of i
50        for (int i = n - 1; i >= 0; --i) {
51            // Compressed 1-based rank of nums[i]
52            int rank = lower_bound(sortedValues.begin(), sortedValues.end(), nums[i])
53                       - sortedValues.begin() + 1;
54
55            // Parity of the current value, and the opposite parity index
56            int parity = nums[i] & 1;
57            int oppositeParity = parity ^ 1;
58
59            // Count elements to the right that are smaller (rank < current rank)
60            // and have the opposite parity
61            ans[i] = bits[oppositeParity]->query(rank - 1);
62
63            // Insert the current element into the BIT matching its parity
64            bits[parity]->update(rank, 1);
65        }
66
67        // Release allocated memory
68        delete bits[0];
69        delete bits[1];
70
71        return ans;
72    }
73};
74

1// Binary Indexed Tree (Fenwick Tree) state, represented as global structures.
2// Each tree is stored as an Int32Array, and its size is tracked separately.
3let bitSize: number;
4
5/**
6 * Updates the Binary Indexed Tree by adding `delta` at position `index`.
7 * @param tree - The Int32Array backing the BIT.
8 * @param index - The 1-based position to update.
9 * @param delta - The value to add at the given position.
10 */
11function update(tree: Int32Array, index: number, delta: number): void {
12    // Traverse upward through the tree, adding delta to all affected nodes.
13    for (; index <= bitSize; index += index & -index) {
14        tree[index] += delta;
15    }
16}
17
18/**
19 * Queries the prefix sum from position 1 up to `index` in the BIT.
20 * @param tree - The Int32Array backing the BIT.
21 * @param index - The 1-based upper bound of the prefix sum.
22 * @returns The cumulative sum over [1, index].
23 */
24function query(tree: Int32Array, index: number): number {
25    let sum = 0;
26    // Traverse downward through the tree, accumulating partial sums.
27    for (; index > 0; index -= index & -index) {
28        sum += tree[index];
29    }
30    return sum;
31}
32
33/**
34 * Performs a lower-bound binary search to find the leftmost index in `sorted`
35 * at which `target` could be inserted to keep the array ordered.
36 * Equivalent to lodash's `_.sortedIndex`.
37 * @param sorted - A sorted array of numbers.
38 * @param target - The value to locate.
39 * @returns The leftmost insertion index for `target`.
40 */
41function sortedIndex(sorted: number[], target: number): number {
42    let low = 0;
43    let high = sorted.length;
44    while (low < high) {
45        const mid = (low + high) >> 1;
46        if (sorted[mid] < target) {
47            low = mid + 1;
48        } else {
49            high = mid;
50        }
51    }
52    return low;
53}
54
55/**
56 * For each element, counts how many subsequent elements (to its right) are
57 * both smaller in value and of opposite parity (odd vs. even).
58 * @param nums - The input array of integers.
59 * @returns An array where ans[i] is the count described above for nums[i].
60 */
61function countSmallerOppositeParity(nums: number[]): number[] {
62    const n = nums.length;
63
64    // Build a sorted, de-duplicated copy of nums for coordinate compression.
65    const sorted = Array.from(new Set(nums)).sort((a, b) => a - b);
66    const m = sorted.length;
67
68    // Set the shared BIT size, then create two BITs:
69    // bits[0] tracks counts of even numbers, bits[1] tracks counts of odd numbers.
70    bitSize = m;
71    const bits: Int32Array[] = [new Int32Array(m + 1), new Int32Array(m + 1)];
72
73    const ans: number[] = new Array(n);
74
75    // Iterate from right to left so each query only sees already-processed
76    // elements lying to the right of the current index.
77    for (let i = n - 1; i >= 0; i--) {
78        // Compute the 1-based compressed rank of nums[i].
79        const rank = sortedIndex(sorted, nums[i]) + 1;
80
81        // Query the BIT of the opposite parity for counts strictly smaller
82        // than nums[i] (i.e., over ranks [1, rank - 1]).
83        const oppositeParity = (nums[i] & 1) ^ 1;
84        ans[i] = query(bits[oppositeParity], rank - 1);
85
86        // Record the current element's contribution in its own parity's BIT.
87        update(bits[nums[i] & 1], rank, 1);
88    }
89
90    return ans;
91}
92

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array nums. The code iterates over the array once with a single loop running n times. In each iteration, two operations are performed on a SortedList: a bisect_left query and an add insertion. The bisect_left operation takes O(log n) time since it performs a binary search on the underlying sorted structure. The add operation takes O(log n) amortized time (binary search to locate the position plus the internal block-based insertion of the SortedList). Therefore, each iteration costs O(log n), and the total time complexity is O(n × log n).
Space Complexity: O(n), where n is the length of the array nums. Two SortedList instances are maintained in sl, partitioned by parity. Together they store at most n elements across all iterations, requiring O(n) space. The output array ans also occupies O(n) space. Hence, the overall space complexity is O(n).

Common Pitfalls

Pitfall 1: Querying the same-parity list instead of the opposite-parity list

The most frequent mistake is forgetting the different parity requirement and counting smaller elements regardless of parity (or accidentally querying the same parity bucket).

# WRONG: counts smaller elements of the SAME parity
ans[i] = sorted_by_parity[current_parity].bisect_left(nums[i])

This silently produces wrong answers because the structure of the code still "looks" correct — it compiles and runs, but it violates the opposite-parity condition.

Solution: Always flip the parity bit before querying, then insert into the original parity bucket:

current_parity = nums[i] & 1
opposite_parity = current_parity ^ 1

ans[i] = sorted_by_parity[opposite_parity].bisect_left(nums[i])  # query opposite
sorted_by_parity[current_parity].add(nums[i])                    # insert into own

Keep the two operations conceptually distinct: query the opposite, store in your own.

Pitfall 2: Using `bisect_right` instead of `bisect_left`

The condition requires nums[j] < nums[i] — a strict inequality. Using bisect_right would also count elements equal to nums[i].

# WRONG: counts elements <= nums[i], including equal values
ans[i] = sorted_by_parity[opposite_parity].bisect_right(nums[i])

Although elements of opposite parity can never be equal to nums[i] (an even number can't equal an odd number), relying on that coincidence is fragile reasoning. If the parity logic is ever loosened or the lists merged, bisect_right would introduce a bug.

Solution: Use bisect_left, which returns the count of values strictly less than nums[i], matching the problem statement directly:

ans[i] = sorted_by_parity[opposite_parity].bisect_left(nums[i])

Pitfall 3: Processing left to right (or inserting before querying)

If you iterate from index 0 to n - 1, the sorted lists will contain elements to the left of i, violating the i < j constraint. A related mistake is inserting nums[i] before querying, which would let an element count itself or pollute the result.

# WRONG: left-to-right traversal counts elements before i, not after
for i in range(n):
    sorted_by_parity[nums[i] & 1].add(nums[i])   # inserted too early
    ans[i] = sorted_by_parity[(nums[i] & 1) ^ 1].bisect_left(nums[i])

Solution: Iterate right to left so that everything stored already lies at an index greater than i, and always query before inserting:

for i in range(n - 1, -1, -1):
    ans[i] = sorted_by_parity[opposite_parity].bisect_left(nums[i])  # query first
    sorted_by_parity[current_parity].add(nums[i])                    # then insert

Pitfall 4: Negative values breaking a Fenwick Tree alternative

If you swap the SortedList approach for a Binary Indexed Tree, indexing directly by value fails when nums contains negative numbers or large values (BIT indices must be small, non-negative integers).

Solution: Apply coordinate compression before building the trees — map each distinct value to a rank in [1, k], maintain two BITs (one per parity), and query the prefix count of smaller ranks. The SortedList version sidesteps this entirely, which is why it is the safer default.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know