Count Inversions
Updated
Problem statement
You are given an integer array arr whose values are all different. Two positions i < j form an inversion if arr[i] > arr[j], so a larger value comes before a smaller one.
Count every such pair and return the total.
The answer can be larger than 2^31 - 1, so return it as a 64-bit integer.
Function
countInversions(arr: int[]) → longExamples
Example 1
arr = [4,1,3,2]return = 4There are six pairs of positions. Four of them have the larger value first: (4, 1), (4, 3), (4, 2) and (3, 2). The pairs (1, 3) and (1, 2) are already in order, so the answer is 4.
Example 2
arr = [5,10,15]return = 0Each value is larger than every value before it, so no pair is an inversion.
Example 3
arr = [9,7,5,3]return = 6The values only go down, so every pair is an inversion. Four values make 4 * 3 / 2 = 6 pairs.
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^9- All values in
arrare different.
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
Similar questions at other companies
- Count InversionsNutanix · OANutanix 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
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)