Frontend School

Count Advantageous Pairs

DSA
medium

Count Advantageous Pairs

Medium
Arrays
Divide and Conquer
Merge Sort

Overview

In the dynamic world of e-commerce, understanding product performance and market positioning is crucial. Imagine you're analyzing sales data, where each number represents a product's performance metric. We want to identify 'advantageous' pairs of products to understand potential market dominance or opportunities for bundling.

This problem challenges you to efficiently count pairs of products (i, j) in a given list such that product i appears before product j (i.e., i < j), and product i's performance metric is significantly greater than product j's. Specifically, nums[i] must be strictly greater than X times nums[j], where X is a given multiplier.

What you need to do / Task

Implement a function countAdvantageousPairs that takes an array of numbers nums and an integer X as input. Your task is to return the total count of all pairs (i, j) that satisfy the following conditions:

  1. i < j (product i appears before product j in the original array)
  2. nums[i] > nums[j] * X (product i's performance is strictly greater than X times product j's performance)

Your solution should be efficient enough to handle large datasets.

Input & output

Input:

  • nums: An array of numbers representing product performance metrics.
  • X: A number representing the multiplier.

Output:

  • A number representing the total count of advantageous pairs.

Function Signature (TypeScript):

function countAdvantageousPairs(nums: number[], X: number): number

Clarifications

  • Empty array: If nums is empty or contains only one element, no pairs can be formed, so the count should be 0.
  • X value: X will always be a positive integer. If X=1, the condition simplifies to nums[i] > nums[j], which counts standard inversions.
  • Negative numbers: All elements in nums will be non-negative integers. 0 is a possible value for nums[i] and nums[j].
  • Large values: nums[i] can be quite large, ensure your comparisons handle potential intermediate products like nums[j] * X correctly without overflow if using fixed-size integer types (though JavaScript/TypeScript numbers handle this well).

Examples

1

Example 1

Input:

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

Output:

2

Note:

The advantageous pairs (i, j) are:

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

Example 2

Input:

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

Output:

5

Note:

The advantageous pairs (i, j) with nums[i] > nums[j] are:

  • (0, 4): 2 > 1
  • (1, 2): 4 > 3
  • (1, 4): 4 > 1
  • (2, 4): 3 > 1
  • (3, 4): 5 > 1
3

Example 3

Input:

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

Output:

0

Note:

No pairs (i, j) satisfy nums[i] > nums[j] * 3.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= X <= 100
  • The solution should aim for an optimal time complexity, typically O(N log N) where N is the length of nums.
  • The solution should aim for an optimal space complexity, typically O(N) for auxiliary storage.

What interviewers evaluate

  • Correctness: The solution must correctly identify and count all advantageous pairs for all valid inputs.
  • Algorithmic Efficiency: Optimal time complexity (O(N log N)) and efficient space usage (O(N)) are expected.
  • Divide and Conquer Application: Demonstrates a clear understanding and correct application of the Divide and Conquer paradigm, specifically a Merge Sort-like approach.
  • Code Quality: Clean, readable, well-structured code with appropriate variable names and comments where necessary.
  • Edge Case Handling: Correctly handles edge cases such as empty arrays, arrays with identical elements, and different values of X.

Loading editor...