Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Inversion Count in an Array

Explore how to count inversions in an array efficiently by applying divide-and-conquer strategies like merge sort. This lesson helps you understand and implement a faster O(n log n) algorithm compared to the naive O(n²) approach, improving your problem-solving skills for coding interviews.

We'll cover the following...

Solution 1

The naive solution to this problem involves the following:

  1. We pick an element from the array.
  2. We compare it with all elements to its right.
  3. If the element on the right is smaller, we increment the inversion count.
C# 9.0
using System;
public class Program
{
    /// <summary>
    /// Finds the inversion count in the array.
    /// </summary>
    /// <param name="arr">Array of integers.</param>
    /// <returns>The inversion count of the array.</returns>
    public static int InversionCount(int[] arr)
    {
        int size = arr.Length;
        int invCount = 0;  // variable to store inversion count
        for (int curr = 0; curr < size - 1; curr++)
        {
            for (int right = curr + 1; right < size; right++)
            {
                if (arr[curr] > arr[right])
                {
                    invCount++;
                }
            }
        }
        return invCount;
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        int[] arr = { 3, 8, 2, 7, 5, 6 };
        int result = InversionCount(arr);
        Console.WriteLine("Number of inversions are " + result);
    }
}

Time complexity

The array is traversed once for each element in it. It runs in O(n2)O(n^2) ...