Binary Search to Find Next Greater Element V

You can use the .BinarySearch method of List<T>. It works well, there is a bit of a trick that you need to do when the return index is negative (just assign it to its complement, ~index). No need to perform the Binary Search "by hand" anymore. Achieves a good NLogN, fast solution. LC suggests a Tree to be used but this approach (two lists, one for even, one for odd) works well.
Code is down below, cheers, ACC.

Count Smaller Elements With Opposite Parity - LeetCode

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​​​​​​​

public class Solution {
    public int[] CountSmallerOppositeParity(int[] nums)
    {
        List evenSortedList = new List();
        List oddSortedList = new List();

        int[] retVal = new int[nums.Length];
        if (nums[nums.Length - 1] % 2 == 0) evenSortedList.Add(nums[nums.Length - 1]);
        else oddSortedList.Add(nums[nums.Length - 1]);

        for (int i = retVal.Length - 2; i >= 0; i--)
        {
            if (nums[i] % 2 == 0)
            {
                retVal[i] = FindNumberOfGreaterElements(oddSortedList, nums[i]);
                AddSortedList(evenSortedList, nums[i]);
            }
            else
            {
                retVal[i] = FindNumberOfGreaterElements(evenSortedList, nums[i]);
                AddSortedList(oddSortedList, nums[i]);
            }
        }

        return retVal;
    }

    private int FindNumberOfGreaterElements(List sortedList, int x)
    {
        int index = sortedList.BinarySearch(x);
        if (index < 0) index = ~index;
        return index;
    }

    private void AddSortedList(List sortedList, int x)
    {
        int index = sortedList.BinarySearch(x);
        if (index < 0) index = ~index;
        sortedList.Insert(index, x);
    }
}