Count triplets (i, j, k) in an array of distinct elements such that a[i]

0 0 6 minutes read

Given an array arr[] consisting of N distinct integers, the task is to count the number of triplets (i, j, k) possible from the array arr[] such that i < j < k and arr[i] < arr[j] > arr[k].

Examples:

Input: arr[] = {2, 3, 1, -1}
Output: 2
Explanation: From the given array, all possible triplets satisfying the property (i, j, k) and arr[i] < arr[j] > arr[k] are:

(0, 1, 2): arr[0](= 2) < arr[1](= 3) > arr[2](= 1).

(0, 1, 3): arr[0](= 2) < arr[1](= 3) > arr[3](= -1).

Therefore, the count of triplets is 2.

Input: arr[] = {2, 3, 4, 6, 7, 9, 1, 12, 10, 8}
Output: 41

Naive Approach: The simplest approach to solve the problem is to traverse the given array and for each element arr[i], the product of the count of smaller elements on the left side of arr[i] and the count of smaller elements on the right side of arr[i] gives the count of triplets for the element arr[i] as the middle element. The sum of all the counts obtained for each index is the required number of valid triplets. Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by finding the count of smaller elements using a Policy-based data structure (PBDS). Follow the steps below to solve the problem:

Initialize the variable, say ans to 0 that stores the total number of possible pairs.
Initialize two containers of the Policy-based data structure, say P and Q.
Initialize a vector of pairs V, where V[i]. first and V[i].second stores the count of smaller elements on the left and the right side of every array element arr[i].
Traverse the given array and for each element arr[i], update the value of V[i].first as P.order_of_key(arr[i]) and insert arr[i] to set P.
Traverse the array from right to left and for each element arr[i], update the value of V[i].first as P.order_of_key(arr[i]) and insert arr[i] to set Q.
Traverse the vector of pairs V and add the value of V[i].first * V[i].second to the variable ans.
After completing the above steps, print the value of ans as the total number of pairs.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
 
// Function to find the count of triplets
// satisfying the given conditions
void findTriplets(int arr[], int n)
{
    // Stores the total count of pairs
    int ans = 0;
 
    // Declare the set
    tree<int, null_type, less<int>, rb_tree_tag,
         tree_order_statistics_node_update>
        p, q;
 
    // Declare the vector of pairs
    vector<pair<int, int> > v(n);
 
    // Iterate over the array from
    // left to right
    for (int i = 0; i < n; i++) {
 
        // Find the index of element
        // in sorted array
        int index = p.order_of_key(arr[i]);
 
        // Assign to the left
        v[i].first = index;
 
        // Insert into the set
        p.insert(arr[i]);
    }
 
    // Iterate from right to left
    for (int i = n - 1; i >= 0; i--) {
 
        // Find the index of element
        // in the sorted array
        int index = q.order_of_key(arr[i]);
 
        // Assign to the right
        v[i].second = index;
 
        // Insert into the set
        q.insert(arr[i]);
    }
 
    // Traverse the vector of pairs
    for (int i = 0; i < n; i++) {
        ans += (v[i].first * v[i].second);
    }
 
    // Print the total count
    cout << ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 1, -1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, N);
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
 
public class Main 
{
 
  // Function to find the count of triplets
  // satisfying the given conditions
  public static void findTriplets(int[] arr, int n) 
  {
 
    // Stores the total count of pairs
    int ans = 0;
 
    // Declare the list of pairs
    List<Pair<Integer, Integer>> v = new ArrayList<>();
 
    // Iterate over the array from
    // left to right
    for (int i = 0; i < n; i++) {
      // Find the index of element
      // in sorted array
      int index = 0;
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
          index++;
        }
      }
 
      // Assign to the left
      v.add(new Pair<>(index, 0));
    }
 
    // Iterate from right to left
    for (int i = n - 1; i >= 0; i--) {
      // Find the index of element
      // in the sorted array
      int index = 0;
      for (int j = n - 1; j > i; j--) {
        if (arr[j] < arr[i]) {
          index++;
        }
      }
 
      // Assign to the right
      v.get(i).setValue(index);
    }
 
    // Traverse the list of pairs
    for (int i = 0; i < n; i++) {
      ans += (v.get(i).getKey() * v.get(i).getValue());
    }
 
    // Print the total count
    System.out.println(ans);
  }
 
  public static void main(String[] args) {
    int[] arr = { 2, 3, 1, -1 };
    int N = arr.length;
    findTriplets(arr, N);
  }
}
 
class Pair<K, V> {
  private K key;
  private V value;
 
  public Pair(K key, V value) {
    this.key = key;
    this.value = value;
  }
 
  public void setKey(K key) {
    this.key = key;
  }
 
  public void setValue(V value) {
    this.value = value;
  }
 
  public K getKey() {
    return key;
  }
 
  public V getValue() {
    return value;
  }
}
 
// This code is contributed by aadityaburujwale.

Python3

import bisect
 
def findTriplets(arr, n):
    # Stores the total count of pairs
    ans = 0
    # Declare the lists
    p = []
    q = []
 
    # Iterate over the array from left to right
    for i in range(n):
        # Find the index of element in sorted array
        index = bisect.bisect_left(p, arr[i])
        # Insert into the list
        p.insert(index, arr[i])
    # Iterate from right to left
    for i in range(n-1, -1, -1):
        # Find the index of element in the sorted array
        index = bisect.bisect_left(q, arr[i])
        # Insert into the list
        q.insert(index, arr[i])
 
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if arr[i] < arr[j] > arr[k]:
                    ans += 1
    print(ans)
 
# Driver Code
arr = [2, 3, 1, -1]
n = len(arr)
findTriplets(arr, n)
 
# This code is contributed by Vikram_Shirsat

C#

using System;
using System.Collections.Generic;
 
class GFG {
 
  public static void findTriplets(int[] arr, int n) 
  {
 
    // Stores the total count of pairs
    int ans = 0;
 
    // Declare the list of pairs
    List<KeyValuePair<int, int>> v = new List<KeyValuePair<int, int>>();
 
    // Iterate over the array from
    // left to right
    for (int i = 0; i < n; i++) {
      // Find the index of element
      // in sorted array
      int index = 0;
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
          index++;
        }
      }
 
      // Assign to the left
      v.Add(new KeyValuePair<int, int>(index, 0));
    }
 
    // Iterate from right to left
    for (int i = n - 1; i >= 0; i--) {
      // Find the index of element
      // in the sorted array
      int index = 0;
      for (int j = n - 1; j > i; j--) {
        if (arr[j] < arr[i]) {
          index++;
        }
      }
 
      // Assign to the right
      v[i] = new KeyValuePair<int, int>(v[i].Key, index);
    }
 
    // Traverse the list of pairs
    for (int i = 0; i < n; i++) {
      ans += (v[i].Key * v[i].Value);
    }
 
    // Print the total count
    Console.WriteLine(ans);
  }
 
  public static void Main(string[] args) {
    int[] arr = { 2, 3, 1, -1 };
    int N = arr.Length;
    findTriplets(arr, N);
  }
}
 
// This code is contributed by phasing17.

Javascript

// Function to find the count of triplets
// satisfying the given conditions
function findTriplets(arr, n) {
    // Stores the total count of pairs
    let ans = 0;
   
    // Declare the list of pairs
    let v = new Array();
   
    // Iterate over the array from left to right
    for (let i = 0; i < n; i++) {
        // Find the index of element in sorted array
        let index = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                index++;
            }
        }
   
        // Assign to the left
        v.push({ left: index, right: 0 });
    }
   
    // Iterate from right to left
    for (let i = n - 1; i >= 0; i--) {
        // Find the index of element in the sorted array
        let index = 0;
        for (let j = n - 1; j > i; j--) {
            if (arr[j] < arr[i]) {
                index++;
            }
        }
   
        // Assign to the right
        v[i].right = index;
    }
   
    // Traverse the list of pairs
    for (let i = 0; i < n; i++) {
        ans += (v[i].left * v[i].right);
    }
   
    // Print the total count
    console.log(ans);
}
 
let arr = [2, 3, 1, -1];
let N = arr.length;
findTriplets(arr, N);
// this code is contributed by devendra

Output:

Time Complexity: O(N * log N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!