FastPrepCount Inversions With Merge Sort
Problems/Count Inversions With Merge Sort

Count Inversions With Merge Sort

Adobe logoAdobe● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Counting inversions (pairs that appear out of order) with a merge-sort style split was one of three coding items in a combined DSA and low-level-design first round. The post names it only; the other two items, a search over a large unsorted array and a problem it does not name, carry no detail.

The post gives no statement, limits or examples. Here an inversion is a pair of positions i < j with nums[i] > nums[j], equal values never count, the array has 1 to 10^4 values from -10^5 to 10^5, and the count is returned as a 64-bit integer. The examples are our own.

The judged task matches the report at about 90%.

You are given an integer array nums. An inversion is a pair of positions i < j where nums[i] > nums[j]: a larger value that comes before a smaller one.

Return the number of inversions. Two equal values never form an inversion.

Function

countInversions(nums: int[]) → long

Examples

Example 1

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

The pairs out of order are (4, 1), (4, 3), (4, 2) and (3, 2): 4 in total. The pair (1, 3) and the pair (1, 2) are already in order.

Example 2

nums = [5,5,2]return = 2

Each 5 comes before the smaller 2, which gives 2 inversions. The two 5s are equal, so they are not an inversion.

Example 3

nums = [-1,0,7]return = 0

The values already go up, so no pair is out of order.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public long countInversions(int[] nums) {
    // Write your code here.
}
Checking account…