Count Inversions
Updated
Problem statement
You are given an integer array nums. A pair of indices (i, j) is an inversion when i < j and nums[i] > nums[j]. In other words, a larger number appears before a smaller one.
Return the number of inversions in nums. Two equal numbers never form an inversion.
The answer can be too large for a 32-bit integer.
Function
countInversions(nums: int[]) → longExamples
Example 1
nums = [3,1,2]return = 2The pairs that count are (3, 1) and (3, 2): in each one the larger number comes first. The pair (1, 2) is already in order, so the answer is 2.
Example 2
nums = [4,4,2,4]return = 2Both 4s at indices 0 and 1 come before the 2 at index 2, which gives 2 inversions. Pairs of equal values, such as the 4s at indices 0 and 3, do not count. Nothing after the 2 is smaller than it, so the answer is 2.
Example 3
nums = [-1,5,0,-3]return = 4The inversions are (-1, -3), (5, 0), (5, -3) and (0, -3), so the answer is 4.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Count InversionsExpedia · OAExpedia interview questions
- Temporal AnomaliesInMobi · OAInMobi interview questions
- Minimum Euclidean Distance Between PointsLuma AI · OALuma AI interview questions
- Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
- K Largest Elements with QuickselectAMD · ONSITE INTERVIEWAMD interview questions
- Implement Merge SortSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Closest Pair of PointsCitadel · PHONE SCREENCitadel interview questions
- Generalized N-SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Count Inversions With Merge SortAdobe · PHONE SCREENAdobe interview questions
- Capping Portfolio WeightsCapstone Investment Advisors · OA