Frontend School

Count Valued Inversions

DSA
medium

Count Valued Inversions

Medium
Divide and Conquer
Sorting
Arrays

Overview

In data analysis, identifying relationships where one data point significantly outweighs another can be crucial. This problem asks you to count specific pairs of elements in an array that exhibit such a 'dominant' relationship, generalized beyond simple inversions. Your solution will leverage a classic algorithmic paradigm to efficiently process large datasets.

What you need to do / Task

Implement a function countValuedInversions that takes an array of integers nums and an integer K. The function should return the total count of pairs (i, j) such that i < j and nums[i] > nums[j] + K. Your solution must employ a Divide and Conquer strategy, similar to how merge sort operates.

Input & output

  • nums: An array of integers.
  • K: An integer representing the threshold for the 'valued' comparison.
  • Return: An integer, representing the total count of pairs (i, j) satisfying the condition i < j and nums[i] > nums[j] + K.

Clarifications

  • Empty or single-element array: If nums is empty or contains only one element, no such pairs can exist, so the function should return 0.
  • Value ranges: nums[i] and K can be positive, negative, or zero.

Examples

Examples

1

Example 1

Input:

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

Output:

4

Note:

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

  • (0, 1): nums[0]=5, nums[1]=3. 5 > 3 + 1 (5 > 4) is True.
  • (0, 2): nums[0]=5, nums[2]=2. 5 > 2 + 1 (5 > 3) is True.
  • (0, 3): nums[0]=5, nums[3]=1. 5 > 1 + 1 (5 > 2) is True.
  • (1, 3): nums[1]=3, nums[3]=1. 3 > 1 + 1 (3 > 2) is True. Total count = 4.
2

Example 2

Input:

nums = [1, 2, 3, 4], K = 0

Output:

0

Note:

Pairs (i, j) with i < j and nums[i] > nums[j] + 0 (i.e., nums[i] > nums[j]): Since the array is sorted in ascending order, no element is strictly greater than any subsequent element. Total count = 0.

3

Example 3

Input:

nums = [10, 2, 8, 1, 5], K = 3

Output:

5

Note:

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

  • (0, 1): nums[0]=10, nums[1]=2. 10 > 2 + 3 (10 > 5) is True.
  • (0, 3): nums[0]=10, nums[3]=1. 10 > 1 + 3 (10 > 4) is True.
  • (0, 4): nums[0]=10, nums[4]=5. 10 > 5 + 3 (10 > 8) is True.
  • (2, 3): nums[2]=8, nums[3]=1. 8 > 1 + 3 (8 > 4) is True.
  • (2, 4): nums[2]=8, nums[4]=5. 8 > 5 + 3 (8 > 8) is False. Total count = 5.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= K <= 10^9
  • Your solution should aim for O(N log N) time complexity.
  • Your solution should aim for O(N) space complexity.

Out of scope

  • Optimizations beyond O(N log N) time or O(N) space complexity are not required.
  • Handling non-integer inputs or non-array inputs is not necessary.

What interviewers evaluate

  • Correct application of the Divide and Conquer paradigm.
  • Efficiency of the algorithm, particularly the O(N) merge and count step.
  • Clarity and correctness of code implementation.
  • Ability to analyze and articulate the time and space complexity.

Loading editor...