Given an array of integers, implement an in-place algorithm to optimize the inversion count, which is defined as the number of pairs (i, j) such that i arr[j]. Your solution should modify the array directly and return the total count of inversions. Ensure that your algorithm operates with a time complexity better than O(n^2).

To solve the inversion count problem, we can leverage the **merge sort** algorithm, which naturally divides the array and counts inversions during the merge step. This approach applies here because: 1. **Divide and Conquer**: Merge sort splits the array into smaller subarrays, allowing us to efficiently count inversions while merging. 2. **Inversion Counting**: While merging two sorted halves, if an element from the right half is smaller than one from the left half, it indicates that all remaining elements in the left half are also greater, leading to multiple inversions. This gives us a way to count inversions in O(n log n) time. 3. **In-Place Modification**: The merge process can be adapted to modify the array directly, meeting the problem's requirement. Here’s a step-by-step breakdown of the algorithm: 1. **Recursive Merge Sort**: Implement a merge sort that divides the array until we have subarrays of size 1. 2. **Merge and Count**: In the merge function, count inversions: - Initialize pointers for the left and right subarrays. - Compare elements from both subarrays. If an element from the left subarray is larger than the one from the right, count how many elements are left in the left subarray (all of these will be inversions). - Continue until all elements are merged. 3. **Modify In-Place**: During the merge step, directly modify the original array to place elements in sorted order. **Example**: For the array [2, 4, 1, 3, 5]: - Split to [2, 4] and [1, 3, 5]. Count inversions in each half. - Merge [2, 4] with [1, 3, 5], counting the inversions (in this case, there are 3 inversions: (2,1), (4,1), and (4,3)). Here is 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) # All remaining elements in left are greater 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(arr, temp_arr, left, right): inv_count = 0 if left < right: mid = (left + right) // 2 inv_count += merge_sort(arr, temp_arr, left, mid) inv_count += merge_sort(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(arr, temp_arr, 0, len(arr) - 1) ``` This function modifies `arr` in place and returns the total inversion count. The time complexity of this solution is **O(n log n)** due to the merge sort algorithm, which divides the array into halves and takes linear time for merging and counting inversions. - Each merge operation counts inversions in linear time, leading to the log factor from the number of levels in the recursion tree. The space complexity is **O(n)** because of the temporary array used for merging. We need additional space proportional to the number of elements in the input array. Consider the following edge cases: 1. **Empty Array**: An input of `[]` should return 0 since there are no elements to compare. 2. **Single Element**: An input of `[1]` should also return 0, as there are no pairs to form. 3. **Already Sorted**: An already sorted array like `[1, 2, 3, 4]` should return 0 inversions. 4. **All Elements Same**: An input like `[2, 2, 2]` should return 0, as there are no valid pairs. 5. **Worst Case**: An input in completely reverse order like `[5, 4, 3, 2, 1]` should return the maximum number of inversions, which is `n(n-1)/2` for n elements.

Optimize inversion for in-place | HubSpot Software Engineer Interview

Optimize inversion for in-place

Last updated: March 28, 2026

Quick Overview

Given an array of integers, implement an in-place algorithm to optimize the inversion count, which is defined as the number of pairs (i, j) such that i < j and arr[i] > arr[j]. Your solution should modify the array directly and return the total count of inversions. Ensure that your algorithm operates with a time complexity better than O(n^2).

HubSpot

Coding & Algorithms

Software Engineer

HubSpot

March 28, 2026

Software Engineer

Onsite

Coding & Algorithms

Hard

211

2,745 solved

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

What the Interviewer Expects

Quickly identify the optimal approach and its theoretical basis
Handle complex algorithm design with multiple interacting components
Write concise, elegant code under time pressure
Prove correctness of your approach and discuss alternative solutions
Optimize beyond the obvious: discuss constant factor improvements
Address follow-up variations and explain how the solution generalizes

Key Topics to Cover

Hash maps and frequency counting

Common algorithm patterns (sliding window, two pointers, BFS/DFS)

Time and space complexity analysis

Graph algorithms and traversal

Sorting and searching

Edge cases and input validation

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?
What is the worst-case input for your solution?
Can you solve this iteratively instead of recursively (or vice versa)?

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 inversion count problem, we can leverage the merge sort algorithm, which naturally divides the array and counts inversions during the merge step. This approach applies here because:

...

Approach

Here’s a step-by-step breakdown of the algorithm:

Recursive Merge Sort: Implement a merge sort that divides the array until we have subarrays of size 1.
Merge and Count: In the merge fun...

Submit Your Answer

Markdown supported

HubSpot Software Engineer Interview Guide

Interview process, tips, and preparation timeline

Optimize inversion for in-place

HubSpot

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

HubSpot 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