Frontend School

Count Significant Inversions

DSA
hard

Count Significant Inversions

Hard
Arrays
Divide and Conquer
Merge Sort
Counting

Overview

At Airbnb, understanding user behavior and identifying significant trends in sequential data is crucial. For instance, we might analyze booking values over time and detect when a user's recent booking value is disproportionately smaller than an earlier one, indicating a shift in preference or a potential issue. This problem asks you to identify "significant inversions" in a sequence of numerical data, which can model such scenarios.

What you need to do / Task

Given an array of integers nums representing a sequence of data points (e.g., booking values, user engagement scores), and an integer k, your task is to count the number of "significant inversion" pairs (i, j). A pair (i, j) is considered a significant inversion if:

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

You must implement a function countSignificantInversions that returns this total count.

Input & output

Function Signature:

function countSignificantInversions(nums: number[], k: number): number;

Input:

  • nums: An array of integers. Represents the sequence of data points.
  • k: An integer. The multiplier threshold for defining a significant inversion.

Output:

  • An integer, representing the total count of significant inversion pairs (i, j) where i < j and nums[i] > k * nums[j].

Clarifications

  • Empty input: If nums is empty or has only one element, no inversions are possible, so the count should be 0.
  • k value: k will always be a positive integer.
  • Integer overflow: The count of inversions can be large. Ensure your solution handles counts up to 2 * 10^9 (or Number.MAX_SAFE_INTEGER in JavaScript/TypeScript). The values in nums can also be large, so intermediate calculations like k * nums[j] should be handled carefully to avoid overflow. For this problem, nums[j] values will be positive.

Examples

1

Example 1

Input:

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

Output:

4

Note:

Pairs (i, j) with i < j and nums[i] > 2 * nums[j]: (0, 2): nums[0]=5 > 2nums[2]=4 (true) (0, 4): nums[0]=5 > 2nums[4]=2 (true) (1, 4): nums[1]=3 > 2nums[4]=2 (true) (3, 4): nums[3]=4 > 2nums[4]=2 (true) Total count = 4.

2

Example 2

Input:

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

Output:

4

Note:

Pairs (i, j) with i < j and nums[i] > 1 * nums[j]: (1, 2): nums[1]=3 > 1nums[2]=2 (true) (1, 4): nums[1]=3 > 1nums[4]=1 (true) (2, 4): nums[2]=2 > 1nums[4]=1 (true) (3, 4): nums[3]=3 > 1nums[4]=1 (true) Total count = 4.

3

Example 3

Input:

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

Output:

2

Note:

Pairs (i, j) with i < j and nums[i] > 3 * nums[j]: (1, 4): nums[1]=4 > 3nums[4]=3 (true) (3, 4): nums[3]=5 > 3nums[4]=3 (true) Total count = 2.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 2 * 10^9 (all numbers are positive)
  • 1 <= k <= 100
  • The total number of significant inversions will fit within a standard 32-bit signed integer for typical test cases, but the maximum possible value could exceed it. For JavaScript/TypeScript, number type handles large integers up to 2^53 - 1 safely. For other languages, consider long long or similar.

What interviewers evaluate

  • Correctness and Efficiency: The solution must correctly count all significant inversions and be asymptotically efficient, especially for large inputs.
  • Divide and Conquer Mastery: Demonstrates a strong understanding of how to apply the divide and conquer paradigm, specifically adapting techniques like merge sort for counting specific pairs.
  • Edge Case Handling: Correctly handles base cases, empty inputs, and scenarios where k might lead to specific interactions (e.g., k=1, values close to k * nums[j]).
  • Code Quality: Writes clean, well-structured, and readable code with appropriate variable names and comments where necessary.

Loading editor...