Frontend School

Count Dominant Pairs

DSA
hard

Count Dominant Pairs

Hard
Arrays
Divide and Conquer
Sorting
Merge Sort

Overview

In data analysis, identifying relationships between data points is crucial. Imagine we have a sequence of sensor readings, and we want to find how many times an earlier reading is significantly higher than a later reading. This problem asks us to count such "dominant" pairs where an element nums[i] at an earlier index i is strictly greater than nums[j] + k for a later index j, where k is a given threshold. This type of analysis helps in understanding trends and significant drops in data, which is vital for system monitoring and anomaly detection.

What you need to do / Task

  1. Implement a function countDominantPairs that takes an array of numbers nums and an integer k.
  2. The function should return the total count of pairs (i, j) such that i < j and nums[i] > nums[j] + k.
  3. Your solution should be optimized for performance, particularly for large input arrays, aiming for a time complexity better than O(N^2).

Input & output

  • nums: An array of integers representing the sequence of readings.
  • k: An integer representing the dominance threshold.
  • Returns: An integer, the total count of dominant pairs (i, j) where i < j and nums[i] > nums[j] + k.

Clarifications

  • The array nums can contain positive, negative, or zero integers.
  • k can be positive, negative, or zero.
  • A pair (i, j) implies i and j are 0-indexed positions in the array.
  • The condition is nums[i] > nums[j] + k, which is equivalent to nums[i] - k > nums[j].

Examples

1

Example 1

Input:

nums = [5, 2, 8, 1], k = 2

Output:

3

Note:

Pairs (i, j) with i < j and nums[i] > nums[j] + k:

  • (0, 1): nums[0]=5, nums[1]=2. 5 > 2 + 2 (5 > 4). This is a dominant pair.
  • (0, 3): nums[0]=5, nums[3]=1. 5 > 1 + 2 (5 > 3). This is a dominant pair.
  • (2, 3): nums[2]=8, nums[3]=1. 8 > 1 + 2 (8 > 3). This is a dominant pair. No other pairs satisfy the condition. Total count = 3.
2

Example 2

Input:

nums = [1, 3, 2, 3, 1], k = 0

Output:

2

Note:

Pairs (i, j) with i < j and nums[i] > nums[j] + k:

  • (1, 2): nums[1]=3, nums[2]=2. 3 > 2 + 0 (3 > 2). This is a dominant pair.
  • (3, 4): nums[3]=3, nums[4]=1. 3 > 1 + 0 (3 > 1). This is a dominant pair. Total count = 2.
3

Example 3

Input:

nums = [10, 3, 1, 8], k = 5

Output:

2

Note:

Pairs (i, j) with i < j and nums[i] > nums[j] + k:

  • (0, 1): nums[0]=10, nums[1]=3. 10 > 3 + 5 (10 > 8). This is a dominant pair.
  • (0, 2): nums[0]=10, nums[2]=1. 10 > 1 + 5 (10 > 6). This is a dominant pair. No other pairs satisfy the condition. Total count = 2.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= k <= 10^9
  • The total count of dominant pairs will fit within a 32-bit signed integer.

What interviewers evaluate

  • Correctness: The solution accurately counts all dominant pairs under various test cases and edge conditions.
  • Algorithm Design: Demonstrates a clear understanding and application of the Divide and Conquer paradigm, specifically adapting Merge Sort for counting.
  • Time and Space Complexity: Achieves optimal O(N log N) time complexity and O(N) auxiliary space complexity.
  • Code Quality: Provides clean, readable, well-structured code with appropriate variable names and comments where necessary.

Loading editor...