Frontend School

Count Dominant Pairs

DSA
hard

Count Dominant Pairs

Hard
Arrays
Divide and Conquer
Merge Sort
Counting

Overview

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.

What you need to do / Task

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:

  1. i < j (the first element appears before the second)
  2. 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.

Input & output

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:

  • A single integer, the total count of dominant pairs (i, j) satisfying the conditions.

Clarifications

  • Empty 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.
  • Large 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

1

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:

  • (i=1, j=4): nums[1]=4, nums[4]=1. Condition: 4 > 2*1 (True).
  • (i=2, j=4): nums[2]=3, nums[4]=1. Condition: 3 > 2*1 (True).
  • (i=3, j=4): nums[3]=5, nums[4]=1. Condition: 5 > 2*1 (True). Total count = 3.
2

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].

3

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:

  • (0,1): 5>4; (0,2): 5>3; (0,3): 5>2; (0,4): 5>1 (4 pairs)
  • (1,2): 4>3; (1,3): 4>2; (1,4): 4>1 (3 pairs)
  • (2,3): 3>2; (2,4): 3>1 (2 pairs)
  • (3,4): 2>1 (1 pair) Total count = 4 + 3 + 2 + 1 = 10.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 100
  • The solution must have a time complexity of O(N log N), where N is the length of nums.
  • The solution should aim for a space complexity of O(N).

Out of scope

  • Handling non-integer inputs or k values. All inputs will conform to the specified integer types and ranges.
  • Negative numbers in nums array are not expected.

What interviewers evaluate

  • Algorithmic Correctness: The ability to correctly apply and adapt the Divide and Conquer paradigm (specifically, a modified Merge Sort) to solve the problem.
  • Efficiency: The solution should meet the O(N log N) time complexity and O(N) space complexity requirements.
  • Edge Case Handling: Correctly identifying and managing edge cases, such as k=1 or arrays with all equal elements.
  • Code Structure and Readability: Clean, well-organized code with appropriate variable names and comments where necessary.
  • Problem-Solving Approach: Clear articulation of the thought process, including how the D&C strategy is chosen and implemented.

Loading editor...