Frontend School

Ixigo Dominating Pairs Count

DSA
hard

Ixigo Dominating Pairs Count

Hard
Divide and Conquer
Arrays
Merge Sort
Counting

Overview

At Ixigo, we often deal with ranking and comparing various entities like flights, hotels, or user preferences. Sometimes, a significant disparity in value between two items indicates a 'dominance' of one over the other. This problem models such a scenario where we need to count pairs exhibiting a strong form of dominance within a given sequence of values.

What you need to do / Task

Your task is to implement a function countDominatingPairs that identifies and counts specific pairs within an array of integers. A pair (i, j) is considered "dominating" if it satisfies two conditions:

  1. The index i must be strictly less than the index j (i < j).
  2. The value at index i must be strictly greater than twice the value at index j (nums[i] > 2 * nums[j]).

Implement the countDominatingPairs function to return the total number of such dominating pairs found in the input array nums.

Input & output

  • Input: nums — An array of integers.
  • Output: An integer representing the total count of dominating pairs (i, j) where i < j and nums[i] > 2 * nums[j].

Clarifications

  • The input array nums can contain positive, negative, or zero values.
  • Duplicate values are allowed in the array.
  • The order of indices i and j is crucial: i must always precede j.
  • Pay attention to potential integer overflow issues if nums[j] is very large, especially when multiplied by 2. In JavaScript/TypeScript, number type handles values up to 2^53 - 1 without precision loss for integers, which is sufficient for the given constraints.

Examples

1

Example 1

Input:

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

Output:

3

Note:

The dominating pairs are:

  • (4,1) from (nums[1]=4, nums[4]=1) because 1 < 4 and 4 > 2 * 1
  • (3,1) from (nums[2]=3, nums[4]=1) because 2 < 4 and 3 > 2 * 1
  • (5,1) from (nums[3]=5, nums[4]=1) because 3 < 4 and 5 > 2 * 1
2

Example 2

Input:

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

Output:

2

Note:

The dominating pairs are:

  • (3,1) from (nums[1]=3, nums[4]=1) because 1 < 4 and 3 > 2 * 1
  • (3,1) from (nums[3]=3, nums[4]=1) because 3 < 4 and 3 > 2 * 1
3

Example 3

Input:

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

Output:

4

Note:

The dominating pairs are:

  • (5,1) from (nums[0]=5, nums[4]=1) because 0 < 4 and 5 > 2 * 1
  • (5,2) from (nums[0]=5, nums[3]=2) because 0 < 3 and 5 > 2 * 2
  • (4,1) from (nums[1]=4, nums[4]=1) because 1 < 4 and 4 > 2 * 1
  • (3,1) from (nums[2]=3, nums[4]=1) because 2 < 4 and 3 > 2 * 1

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -2 * 10^9 <= nums[i] <= 2 * 10^9
  • The total count of dominating pairs will fit within a standard 64-bit integer type (e.g., number in JavaScript/TypeScript, long in Java/C++).

Out of scope

  • Optimizing for memory usage beyond O(N) auxiliary space is not required.
  • Handling non-integer or non-numeric input types.

What interviewers evaluate

  • Correctness and efficiency of the algorithm, aiming for optimal time complexity (typically O(N log N)).
  • Effective application of Divide and Conquer principles to solve the problem.
  • Clarity, structure, and readability of the code.
  • Robustness in handling various input scenarios, including edge cases like arrays with identical elements, negative numbers, or very large/small values.

Loading editor...