LeetCode Problem 3917

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3917 - Count Indices With Opposite Parity

Problem Understanding

The problem gives us an integer array nums of length n. For every index i, we must determine how many indices to its right contain a number with the opposite parity.

Parity refers to whether a number is even or odd:

• Even numbers have a remainder of 0 when divided by 2.
• Odd numbers have a remainder of 1 when divided by 2.

For a particular index i, its score is the number of indices j such that:

• j is strictly greater than i
• nums[i] and nums[j] have different parity

The output is an array answer where answer[i] contains the score for index i.

For example, if nums[i] is odd, then we need to count how many even numbers appear after position i. Similarly, if nums[i] is even, we need to count how many odd numbers appear after position i.

The constraints are very small:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Since the array length is only 100, even quadratic solutions would comfortably fit within the limits. However, it is still useful to identify a more efficient approach.

Some important edge cases include:

• An array containing only one element.
• An array where all numbers are even.
• An array where all numbers are odd.
• Arrays with alternating parity.
• Arrays where the desired opposite parity appears only near the beginning or end.

The problem guarantees that the array is non-empty and all values are positive integers.

Approaches

Brute Force

The most direct solution is to evaluate the score for every index independently.

For each index i, we scan every later index j > i. Whenever nums[i] and nums[j] have opposite parity, we increment the score for i.

This approach is correct because it directly implements the definition of the score given in the problem statement. Every valid pair (i, j) is examined exactly once.

However, for every index we may scan the remainder of the array, resulting in quadratic time complexity.

Optimal Observation

Instead of repeatedly scanning the suffix of the array, we can process the array from right to left.

Suppose we know how many odd and even numbers exist to the right of the current position.

• If the current number is odd, its answer is the number of even values to its right.
• If the current number is even, its answer is the number of odd values to its right.

After computing the answer for the current position, we add the current number to the appropriate parity count so that it becomes part of the suffix for future indices.

This allows every position to be processed in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every pair (i, j) with i < j
Optimal	O(n)	O(1)	Maintain counts of odd and even numbers to the right

Algorithm Walkthrough

Optimal Algorithm

1. Create an answer array of length n, initialized with zeros.
2. Maintain two counters:

• odd_count, the number of odd elements to the right of the current position.
• even_count, the number of even elements to the right of the current position.

3. Start traversing the array from right to left.
4. For the current element:

• If it is odd, then every even number already counted in even_count forms a valid opposite-parity pair. Set answer[i] = even_count.
• If it is even, then every odd number already counted in odd_count forms a valid opposite-parity pair. Set answer[i] = odd_count.

5. After computing the answer for the current index, update the appropriate parity counter:

• Increment odd_count if the current value is odd.
• Increment even_count if the current value is even.

6. Continue until all indices have been processed.
7. Return the completed answer array.

Why it works

When processing index i, the counters contain exactly the numbers that appear strictly to the right of i. Therefore:

• odd_count equals the number of odd elements in the suffix (i+1 ... n-1).
• even_count equals the number of even elements in the suffix (i+1 ... n-1).

If nums[i] is odd, every even number in that suffix contributes one valid pair. If nums[i] is even, every odd number contributes one valid pair. Since the counters always represent the current suffix correctly, each answer is computed exactly according to the problem definition.

Python Solution

class Solution:
    def countOppositeParity(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [0] * n

        odd_count = 0
        even_count = 0

        for i in range(n - 1, -1, -1):
            if nums[i] % 2 == 1:
                answer[i] = even_count
                odd_count += 1
            else:
                answer[i] = odd_count
                even_count += 1

        return answer

The implementation begins by creating the result array and initializing counters for odd and even values appearing to the right of the current position.

The array is then traversed from right to left. At each index, the current parity determines which counter represents valid opposite-parity elements. That value becomes the answer for the current index.

After recording the answer, the current element is added to the appropriate counter. This ensures that when earlier indices are processed, the current element is correctly considered part of their suffix.

Finally, the populated answer array is returned.

Go Solution

func countOppositeParity(nums []int) []int {
	n := len(nums)
	answer := make([]int, n)

	oddCount := 0
	evenCount := 0

	for i := n - 1; i >= 0; i-- {
		if nums[i]%2 == 1 {
			answer[i] = evenCount
			oddCount++
		} else {
			answer[i] = oddCount
			evenCount++
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. The result slice is allocated with make, and two integer counters track the number of odd and even elements seen while traversing from right to left.

There are no special concerns regarding integer overflow because the maximum possible answer is at most n - 1, and n <= 100. Go slices are used directly, and there is no distinction that affects correctness between nil and empty slices because the input always contains at least one element.

Worked Examples

Example 1

Input:

nums = [1, 2, 3, 4]

Process from right to left.

Index	Value	Parity	odd_count Before	even_count Before	answer[i]	odd_count After	even_count After
3	4	Even	0	0	0	0	1
2	3	Odd	0	1	1	1	1
1	2	Even	1	1	1	1	2
0	1	Odd	1	2	2	2	2

Final result:

[2, 1, 1, 0]

Example 2

Input:

nums = [1]

Process from right to left.

Index	Value	Parity	odd_count Before	even_count Before	answer[i]
0	1	Odd	0	0	0

Final result:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only two counters are used beyond the output array

The algorithm performs a single pass through the array from right to left. Every iteration executes a constant amount of work, resulting in linear time complexity. Aside from the required output array, only two integer counters are maintained, so the auxiliary space usage is constant.

Test Cases

sol = Solution()

assert sol.countOppositeParity([1, 2, 3, 4]) == [2, 1, 1, 0]  # provided example
assert sol.countOppositeParity([1]) == [0]  # single element

assert sol.countOppositeParity([2, 4, 6, 8]) == [0, 0, 0, 0]  # all even
assert sol.countOppositeParity([1, 3, 5, 7]) == [0, 0, 0, 0]  # all odd

assert sol.countOppositeParity([1, 2]) == [1, 0]  # minimal opposite parity pair
assert sol.countOppositeParity([2, 1]) == [1, 0]  # reversed parity pair

assert sol.countOppositeParity([1, 2, 1, 2, 1]) == [2, 2, 1, 1, 0]  # alternating pattern
assert sol.countOppositeParity([2, 1, 2, 1, 2]) == [2, 2, 1, 1, 0]  # alternating starting even

assert sol.countOppositeParity([1, 1, 1, 2]) == [1, 1, 1, 0]  # only one opposite parity at end
assert sol.countOppositeParity([2, 2, 2, 1]) == [1, 1, 1, 0]  # single odd at end

assert sol.countOppositeParity([1, 4, 6, 8, 3]) == [3, 1, 1, 1, 0]  # mixed distribution

Test Summary

Test	Why
[1, 2, 3, 4]	Validates the primary example
[1]	Smallest allowed input
[2, 4, 6, 8]	All even numbers
[1, 3, 5, 7]	All odd numbers
[1, 2]	Smallest non-trivial opposite parity case
[2, 1]	Opposite parity with reversed ordering
[1, 2, 1, 2, 1]	Alternating parity pattern
[2, 1, 2, 1, 2]	Alternating pattern starting with even
[1, 1, 1, 2]	Single opposite-parity element at the end
[2, 2, 2, 1]	Single odd element at the end
[1, 4, 6, 8, 3]	General mixed case

Edge Cases

Single Element Array

When the array contains only one element, there are no indices to the right. Therefore, the score must be zero. A common mistake is assuming every index has at least one later element. The algorithm naturally handles this because both counters start at zero, so the lone element receives a score of zero.

All Numbers Have The Same Parity

If every element is even, or every element is odd, no valid opposite-parity pairs exist. Every answer should therefore be zero. The algorithm handles this correctly because the counter representing the opposite parity never increases, so every score remains zero.

Opposite Parity Appears Only Near The End

Consider an input such as [1, 1, 1, 2]. Every odd number should count the single even number at the end. Implementations that scan in the wrong direction or update counts before computing the current answer can easily introduce off-by-one errors. By computing the answer first and then updating the counters, the algorithm ensures only elements strictly to the right are counted.

Alternating Parity Arrays

Arrays such as [1, 2, 1, 2, 1] contain many valid opposite-parity pairs. These cases verify that the counters correctly accumulate all future elements of the opposite parity. Since the algorithm maintains exact suffix counts at every step, it correctly computes all scores without repeatedly scanning the remainder of the array.