Frontend School

Count Dominant Pairs

DSA
hard

Count Dominant Pairs

Hard
Divide and Conquer
Merge Sort
Arrays

Overview

In data analysis and financial modeling, identifying significant relationships where one entity's value substantially outweighs another's is crucial. Such relationships can indicate strong influence, imbalance, or potential for specific interventions. This problem challenges you to find "dominant pairs" within a dataset, representing instances where one data point is more than twice the value of a subsequent one. An efficient algorithm is key for processing large datasets in real-world applications.

What you need to do / Task

Implement a function countDominantPairs that takes an array of integers nums and returns the total number of "dominant pairs". A pair of indices (i, j) is considered dominant if:

  1. i < j (the first element appears before the second in the array)
  2. nums[i] > 2 * nums[j] (the value at index i is strictly greater than twice the value at index j)

Your solution should be optimized for performance, especially for large input arrays.

Input & output

  • Input: nums: number[]
    • An array of integers.
  • Output: number
    • The total count of dominant pairs (i, j) satisfying the conditions.

Clarifications

  • Empty or Single-Element Array: If nums is empty or contains only one element, there can be no pairs (i, j) where i < j. In such cases, the function should return 0.
  • Negative Numbers and Zero: The array can contain negative numbers and zero. The dominance condition nums[i] > 2 * nums[j] must hold true even with these values.
  • Duplicates: The array may contain duplicate numbers. Each pair (i, j) is counted uniquely based on its indices.
  • Integer Overflow: Be mindful of potential integer overflow when performing 2 * nums[j] if nums[j] is very large, though standard number types in JavaScript/TypeScript can handle values up to 2^53 - 1 safely, which covers the given constraints.

Examples

1

Example 1

Input:

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

Output:

2

Note:

The dominant pairs are:

  • (1,4): nums[1] = 3, nums[4] = 1. Condition: 3 > 2 * 1 (3 > 2) is true.
  • (3,4): nums[3] = 3, nums[4] = 1. Condition: 3 > 2 * 1 (3 > 2) is true. All other pairs (i, j) where i < j do not satisfy nums[i] > 2 * nums[j].
2

Example 2

Input:

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

Output:

3

Note:

The dominant pairs are:

  • (1,4): nums[1] = 4, nums[4] = 1. Condition: 4 > 2 * 1 (4 > 2) is true.
  • (2,4): nums[2] = 3, nums[4] = 1. Condition: 3 > 2 * 1 (3 > 2) is true.
  • (3,4): nums[3] = 5, nums[4] = 1. Condition: 5 > 2 * 1 (5 > 2) is true.
3

Example 3

Input:

nums = [2,1,1]

Output:

0

Note:

No pairs (i, j) exist where i < j and nums[i] > 2 * nums[j].

4

Example 4

Input:

nums = [5,0,0]

Output:

2

Note:

The dominant pairs are:

  • (0,1): nums[0] = 5, nums[1] = 0. Condition: 5 > 2 * 0 (5 > 0) is true.
  • (0,2): nums[0] = 5, nums[2] = 0. Condition: 5 > 2 * 0 (5 > 0) is true.

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), where N is the length of nums.
  • The solution should use O(N) auxiliary space complexity at most.

Out of scope

  • Handling non-integer inputs or inputs that are not arrays.
  • Concurrency or multi-threading optimizations.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies all dominant pairs under various input conditions, including edge cases.
  • Time Complexity: The algorithm achieves the optimal O(N log N) time complexity, demonstrating a strong understanding of efficient algorithms.
  • Space Complexity: The solution uses auxiliary space efficiently, ideally O(N).
  • Code Quality: The code is clean, readable, well-structured, and easy to understand.

Loading editor...