# Count triplets which form an inversion in an array

Posted in  Vinay Khatri
Last updated on December 4, 2023

## Problem

Given an array, you need to count all inversion triplets. Inversion triplets are such that ``` i<j<k ``` and ``` arr[i]>arr[j]>arr[k] ``` , for some indices ``` i ``` , ``` j ``` , and ``` k ``` .

#### Sample Input

`[1, 2, 4, 3, 2]`

`1`

### Brute Force Approach

You can consider every triplet present in the array and check the condition mentioned in the problem statement. This approach takes O(N3) time and is inefficient. Let’s look at a more efficient approach to solve this problem.

### Efficient Approach

If we consider each element as the middle element one by one, we can iterate to the left and right side of this index and see which elements satisfy the given condition. The number of triplets formed using this element as middle of the triplet are: number of greater elements to the left * number of smaller elements to the right. The time complexity of this approach is O(N2).

#### C

```#include <stdio.h>

int solve(int arr[], int n)
{
int ans = 0;
for (int j = 1; j < n - 1; j++)
{
int larger = 0;
for (int i = 0; i < j; i++)
{
if (arr[i] > arr[j]) {
larger++;
}
}

int smaller = 0;
for (int k = j + 1; k < n; k++)
{
if (arr[k] < arr[j]) {
smaller++;
}
}

ans += (larger * smaller);
}

return ans;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 2, 1 };
int n = sizeof(arr) / sizeof(arr);

printf("Number of inversions are %d", solve(arr, n));

return 0;
}```

#### Output

`Number of inversions are 2`

#### C++

```#include <bits/stdc++.h>
using namespace std;
int solve(int arr[], int n)
{
int ans = 0;
for (int j = 1; j < n - 1; j++)
{
int larger = 0;
for (int i = 0; i < j; i++)
{
if (arr[i] > arr[j]) {
larger++;
}
}

int smaller = 0;
for (int k = j + 1; k < n; k++)
{
if (arr[k] < arr[j]) {
smaller++;
}
}

ans += (larger * smaller);
}

return ans;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 2, 1 };
int n = sizeof(arr) / sizeof(arr);

cout<<"Number of inversions are "<<solve(arr, n);

return 0;}```

#### Output

`Number of inversions are 2`

#### Python

```def solve(arr):

ans = 0

for j in range(1, len(arr) - 1):

larger = 0
for i in range(j):
if arr[i] > arr[j]:
larger = larger + 1

smaller = 0
for k in range(j + 1, len(arr)):
if arr[k] < arr[j]:
smaller = smaller + 1

ans += (larger * smaller)

return ans

arr = [1, 2, 3, 4, 2, 1]
print("Number of inversions are", solve(arr))```

#### Output

`Number of inversions are 2`