Frontend School

Count Special Inversions

DSA
medium

Count Special Inversions

Medium
Arrays
Divide and Conquer
Merge Sort

Overview

In data analysis and algorithm design, understanding the relative order of elements within a dataset is crucial. Sometimes, we're interested in specific types of 'disorder' or 'inversions' that highlight particular patterns. This problem asks you to identify and count a special kind of inversion pair, where the left element is not only greater than the right element but also satisfies an additional property: being an even number. This type of analysis can be useful in scenarios like anomaly detection or performance metric evaluation, where specific conditions must be met for a 'negative' relationship to be significant.

What you need to do / Task

You are tasked with implementing a function countSpecialInversions that takes an array of integers nums and returns the total count of 'special inversion' pairs. A pair (i, j) is considered a special inversion if:

  1. 0 <= i < j < nums.length (the elements are distinct and nums[i] appears before nums[j]).
  2. nums[i] is an even number.
  3. nums[i] > nums[j].

Your solution should be efficient enough to handle large datasets.

Input & output

  • Input: nums - An array of integers.
  • Output: An integer representing the total count of special inversion pairs.

Clarifications

  • Duplicates: nums may contain duplicate numbers. Each distinct pair (i, j) satisfying the conditions should be counted.
  • Negative Numbers: nums may contain negative integers. The 'even number' condition applies to both positive and negative even numbers (e.g., -2, 0, 4 are even).
  • Zero: 0 is considered an even number.

Examples

1

Example 1

Input:

nums = [4, 1, 3, 2]

Output:

2

Note:

Pairs (i, j) where i < j, nums[i] is even, and nums[i] > nums[j]:

  • (0, 1): nums[0]=4 (even) > nums[1]=1.
  • (0, 3): nums[0]=4 (even) > nums[3]=2. Total special inversions: 2.
2

Example 2

Input:

nums = [2, 5, 1, 6, 3]

Output:

2

Note:

Pairs (i, j) where i < j, nums[i] is even, and nums[i] > nums[j]:

  • (0, 2): nums[0]=2 (even) > nums[2]=1.
  • (3, 4): nums[3]=6 (even) > nums[4]=3. Total special inversions: 2.
3

Example 3

Input:

nums = [1, 3, 5, 7]

Output:

0

Note:

All numbers are odd, so no nums[i] can be an even number. Total special inversions: 0.

4

Example 4

Input:

nums = [10, 8, 6, 4, 2]

Output:

10

Note:

All numbers are even and sorted in descending order. Each even number nums[i] will be greater than all nums[j] where j > i.

  • For nums[0]=10: (10,8), (10,6), (10,4), (10,2) -> 4 pairs
  • For nums[1]=8: (8,6), (8,4), (8,2) -> 3 pairs
  • For nums[2]=6: (6,4), (6,2) -> 2 pairs
  • For nums[3]=4: (4,2) -> 1 pair Total special inversions: 4 + 3 + 2 + 1 = 10.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -2 * 10^9 <= nums[i] <= 2 * 10^9
  • The solution should aim for an optimal time complexity of O(N log N).
  • The solution should aim for an optimal space complexity of O(N).

Out of scope

  • You do not need to modify the original nums array in place if your approach requires auxiliary space. However, if an in-place modification is naturally part of an optimal solution (e.g., during a merge sort), that is acceptable.
  • Extensive error handling for invalid input types (e.g., nums not being an array of numbers) is not required; assume valid input as per constraints.

What interviewers evaluate

  • Correctness: The solution accurately counts all special inversion pairs under various scenarios, including edge cases.
  • Efficiency: The implementation meets the O(N log N) time complexity and O(N) space complexity requirements.
  • Divide and Conquer Application: Demonstrates a clear understanding and correct application of the Divide and Conquer paradigm, particularly in the merge step.
  • Code Quality: Writes clean, readable, and maintainable code with appropriate variable names and structure.

Loading editor...