Count Dominant Pairs
Clevertap's platform processes vast amounts of user behavior data, often represented as sequences of numerical metrics. Identifying specific patterns, such as a user's activity at one point significantly 'dominating' their activity later on, can be crucial for targeted engagement strategies. This problem challenges you to find such 'dominant' relationships within a given sequence of metrics.
You are given an array of positive integers nums and a positive integer k. Your task is to count the total number of "dominant pairs" (i, j) such that:
i < j (the first element appears before the second)nums[i] > k * nums[j] (the value at index i is strictly greater than k times the value at index j)Implement a function countDominantPairs that returns this total count.
Function Signature:
function countDominantPairs(nums: number[], k: number): number
Parameters:
nums: An array of positive integers representing a sequence of metrics.k: A positive integer multiplier.Returns:
(i, j) satisfying the conditions.nums array: The constraints specify nums.length >= 1, so nums will never be empty.k value: k will always be a positive integer (k >= 1). If k=1, the condition simplifies to nums[i] > nums[j], which is a classic inversion count problem.N: The input array nums can be quite large, implying that an O(N^2) brute-force solution will be too slow. An O(N log N) solution is expected.Examples
Example 1
Input:
nums = [2, 4, 3, 5, 1], k = 2
Output:
3
Note:
The dominant pairs (i, j) where i < j and nums[i] > 2 * nums[j] are:
Example 2
Input:
nums = [1, 2, 3, 4], k = 1
Output:
0
Note:
No pairs (i, j) satisfy i < j and nums[i] > 1 * nums[j].
Example 3
Input:
nums = [5, 4, 3, 2, 1], k = 1
Output:
10
Note:
When k=1, we count pairs (i, j) where i < j and nums[i] > nums[j]. This is a standard inversion count. All possible pairs are dominant:
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= k <= 100O(N log N), where N is the length of nums.O(N).k values. All inputs will conform to the specified integer types and ranges.nums array are not expected.O(N log N) time complexity and O(N) space complexity requirements.k=1 or arrays with all equal elements.Loading editor...