Count Data Inversions
In Salesforce, maintaining data integrity and understanding the 'flow' of information is crucial for reporting and analytics. Imagine a scenario where we track the chronological order of customer interactions, sales stages, or product feature adoption. An 'inversion' in this sequence could indicate an anomaly, a process bottleneck, or an unexpected user journey that needs investigation. For instance, if a customer interaction is logged after a later stage interaction, it's an inversion. Identifying these inversions helps us pinpoint areas for process improvement or data quality checks.
You are tasked with implementing a function countInversions that takes an array of integers representing a sequence of data points (e.g., timestamps, stage numbers, arbitrary values) and returns the total number of inversions present in the array.
An inversion is a pair of indices (i, j) such that i < j and nums[i] > nums[j].
Input:
nums: number[] - An array of integers representing a sequence of data points.Output:
number - The total count of inversions in the nums array.0.nums[i] > nums[j]. If nums[i] == nums[j], it is not an inversion.nums can have up to 10^5 elements. An efficient algorithm is required.Examples
Example 1
Input:
nums = [1, 3, 2]
Output:
1
Note:
The only inversion is (3, 2) at indices (1, 2).
Example 2
Input:
nums = [2, 1, 3, 1]
Output:
3
Note:
The inversions are: (2, 1) at (0, 1), (2, 1) at (0, 3), and (3, 1) at (2, 3).
Example 3
Input:
nums = [5, 4, 3, 2, 1]
Output:
10
Note:
All possible pairs (i, j) with i < j form an inversion.
Example 4
Input:
nums = []
Output:
0
Note:
An empty array has no inversions.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^92^31 - 1. The return type number in JavaScript/TypeScript is sufficient to hold such values (up to 2^53 - 1 for integers).nums array in-place is acceptable if it's part of your chosen algorithm, but the primary goal is to count inversions, not to sort the array.O(N log N)) and space (O(N)) limits for large inputs?Loading editor...