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(N2)
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 conditionsvoid 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 Codeint 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 Codearr = [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 conditionsfunction 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:
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
