Given an array of integers, write a function to count the number of inversions in the array, where an inversion is defined as a pair of indices (i, j) such that i arr[j]. Your solution should optimize for time complexity and handle large input sizes efficiently. Return the total count of inversions as an integer.

To solve the problem of counting inversions in an array, we can utilize the **Merge Sort** algorithm. The key observation is that while merging two sorted halves, we can count how many elements from the right half are smaller than elements from the left half. This is because for any element in the left half that is greater than an element in the right half, all subsequent elements in the left half will also be greater, thus forming inversions. This approach effectively reduces the time complexity to O(n log n), which is optimal for this problem, especially given the constraints that might involve large input sizes. 1. **Divide**: Recursively split the array into two halves until you have subarrays of size one. 2. **Conquer**: While merging the two halves back together, count the inversions: - Initialize two pointers, one for each half. - Compare the elements pointed by the two pointers. If the left element is greater than the right element, it indicates that all remaining elements in the left half (to the right of the current pointer) will also be greater than the right element, so we count these as inversions. - Continue merging until all elements are in the sorted order. 3. **Combine**: Return the total count of inversions found from both halves and during the merge. **Example**: For the array `[2, 3, 8, 6, 1]`, when merging `[2, 3, 8]` and `[6, 1]`, we find: - Compare `8` (left) and `6` (right): `8 > 6`, so we have 3 inversions (8, 6), (3, 6), (2, 6). - Compare `8` and `1`: `8 > 1`, so we have another 3 inversions (8, 1), (3, 1), (2, 1). - The total inversions count would be 6. Here’s the implementation in Python: ```python def merge_and_count(arr, temp_arr, left, mid, right): i = left # Starting index for left subarray j = mid + 1 # Starting index for right subarray k = left # Starting index to be sorted inv_count = 0 while i <= mid and j <= right: if arr[i] <= arr[j]: temp_arr[k] = arr[i] i += 1 else: temp_arr[k] = arr[j] inv_count += (mid - i + 1) # Count inversions j += 1 k += 1 while i <= mid: temp_arr[k] = arr[i] i += 1 k += 1 while j <= right: temp_arr[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp_arr[i] return inv_count def merge_sort_and_count(arr, temp_arr, left, right): inv_count = 0 if left < right: mid = (left + right) // 2 inv_count += merge_sort_and_count(arr, temp_arr, left, mid) inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right) inv_count += merge_and_count(arr, temp_arr, left, mid, right) return inv_count def count_inversions(arr): temp_arr = [0]*len(arr) return merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1) ``` This code defines a function to count inversions using the merge sort approach. The time complexity of the solution is O(n log n) due to the divide-and-conquer strategy of merge sort, where we split the array in half logarithmically (log n) and process each element during the merge phase (O(n)). The space complexity is O(n) because we use an auxiliary array to store the merged results. This is efficient and suitable for large input sizes, as it balances both time and space efficiently. 1. **Empty Array**: If the input array is empty, the function should return `0` as there are no elements to compare. 2. **Single Element**: An array with a single element should also return `0`, as there are no pairs to form. 3. **Already Sorted Array**: An already sorted array (e.g., `[1, 2, 3, 4]`) should return `0`, as there are no inversions. 4. **All Elements Same**: An array where all elements are the same (e.g., `[2, 2, 2, 2]`) should also return `0`, as there are no inversions. 5. **Maximum Size Array**: Consider performance and correctness for the largest possible input size (e.g., 10^6 elements) to verify that the implementation runs within time limits.

Optimize inversion for with follow-up | Amazon Software Engineer Interview

Optimize inversion for with follow-up

Last updated: January 9, 2026

Quick Overview

Given an array of integers, write a function to count the number of inversions in the array, where an inversion is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Your solution should optimize for time complexity and handle large input sizes efficiently. Return the total count of inversions as an integer.

Amazon

Coding & Algorithms

Software Engineer

Amazon

January 9, 2026

Software Engineer

Phone Screen

Coding & Algorithms

Medium

161

198 solved

This coding problem is frequently asked during Phone Screen at Amazon. The interviewer is testing your ability to translate a problem into clean, working code while discussing time and space complexity. Amazon expects candidates to write production-quality code, not just solve the puzzle.

What the Interviewer Expects

Recognize the underlying problem pattern (sliding window, two pointers, BFS/DFS, etc.)
Discuss multiple approaches and trade-offs before coding
Implement an optimal solution with clean, production-quality code
Handle all edge cases including boundary conditions and invalid input
Optimize both time and space complexity with clear justification
Test your solution systematically with well-chosen examples

Key Topics to Cover

Graph algorithms and traversal

Dynamic programming and memoization

Tree structures and recursion

Time and space complexity analysis

Edge cases and input validation

Data structure selection and trade-offs

How to Approach This

Clarify input constraints and edge cases before writing code.
Walk through your approach verbally and confirm with the interviewer before coding.
Start with a brute force solution, then optimize. Mention time and space complexity.
Test your solution with examples, including edge cases like empty input or duplicates.
Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.

Possible Follow-up Questions

What happens if the input contains duplicates?
How would your solution change if the input was sorted?
What if the input doesn't fit in memory?

Sharpen Your Skills on Codemia

Practice similar problems with our interactive workspace, get AI feedback, and track your progress.

Practice DSA Problems

Sample Answer

Problem Analysis

To solve the problem of counting inversions in an array, we can utilize the Merge Sort algorithm. The key observation is that while merging two sorted halves, we can count how many elements from t...

Approach

Divide: Recursively split the array into two halves until you have subarrays of size one.
Conquer: While merging the two halves back together, count the inversions:
- Initialize two p...

Submit Your Answer

Markdown supported

Amazon Software Engineer Interview Guide

Interview process, tips, and preparation timeline

Optimize inversion for with follow-up

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string