Frontend School

Count Data Inversions

DSA
medium

Count Data Inversions

Medium
Arrays
Divide and Conquer
Merge Sort

Overview

In Salesforce, maintaining data integrity and understanding the 'flow' of information is crucial for reporting and analytics. Imagine a scenario where we track the chronological order of customer interactions, sales stages, or product feature adoption. An 'inversion' in this sequence could indicate an anomaly, a process bottleneck, or an unexpected user journey that needs investigation. For instance, if a customer interaction is logged after a later stage interaction, it's an inversion. Identifying these inversions helps us pinpoint areas for process improvement or data quality checks.

What you need to do / Task

You are tasked with implementing a function countInversions that takes an array of integers representing a sequence of data points (e.g., timestamps, stage numbers, arbitrary values) and returns the total number of inversions present in the array.

An inversion is a pair of indices (i, j) such that i < j and nums[i] > nums[j].

Input & output

Input:

  • nums: number[] - An array of integers representing a sequence of data points.

Output:

  • number - The total count of inversions in the nums array.

Clarifications

  • Empty or single-element array: If the input array is empty or contains only one element, there are no inversions. The function should return 0.
  • Duplicate values: Duplicate values are handled according to the definition: nums[i] > nums[j]. If nums[i] == nums[j], it is not an inversion.
  • Large N: The input array nums can have up to 10^5 elements. An efficient algorithm is required.

Examples

1

Example 1

Input:

nums = [1, 3, 2]

Output:

1

Note:

The only inversion is (3, 2) at indices (1, 2).

2

Example 2

Input:

nums = [2, 1, 3, 1]

Output:

3

Note:

The inversions are: (2, 1) at (0, 1), (2, 1) at (0, 3), and (3, 1) at (2, 3).

3

Example 3

Input:

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

Output:

10

Note:

All possible pairs (i, j) with i < j form an inversion.

4

Example 4

Input:

nums = []

Output:

0

Note:

An empty array has no inversions.

Constraints

Constraints & assumptions

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The total number of inversions can be large, potentially exceeding 2^31 - 1. The return type number in JavaScript/TypeScript is sufficient to hold such values (up to 2^53 - 1 for integers).

Out of scope

  • Modifying the original nums array in-place is acceptable if it's part of your chosen algorithm, but the primary goal is to count inversions, not to sort the array.

What interviewers evaluate

  • Correctness: Does the solution accurately count all inversions for various inputs, including edge cases?
  • Algorithm Choice: Is an appropriate Divide and Conquer algorithm (e.g., a variation of Merge Sort) used to achieve optimal time complexity?
  • Efficiency: Does the solution run within acceptable time (O(N log N)) and space (O(N)) limits for large inputs?
  • Code Quality: Is the code well-structured, readable, and maintainable, demonstrating good programming practices?

Loading editor...