Count of triplets in an Array (i, j, k) such that i < j < k and a[k] < a[i] < a[j]
Given an array arr[] of N integers, the task is to count number of triplets (i, j, k) in the array such that a[k] < a[i] < a[j] and i < j < k.
Examples:
Input: arr[] = {2, 5, 1, 3, 0}
Output: 4
Explanation:
Below are the triplets (i, j, k) such that i < j < k and a[k] < a[i] < a[j]:
1. (0, 1, 2) and arr[2] < arr[0] 1 < 2 < 5.
2. (0, 1, 4) and arr[4] < arr[0] 0 < 2 < 5.
3. (0, 3, 4) and arr[4] < arr[0] 0 < 2 < 3.
4. (2, 3, 4) and arr[4] < arr[2] 0 < 1 < 3.
Input: arr[] = {2, 5, 1, 2, 0, 3, 10, 1, 5, 0 }
Output: 25
Naive Approach: The idea is to iterate 3 loops and check for each triplet (i, j, k) satisfy the given conditions or not. If yes then increment for that triplet and print the final count after checking all the triplets.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count triplets with the // given conditions int CountTriplets( int arr[], int n) { int cnt = 0; for ( int i = 0; i < n; i++) for ( int j = i + 1; j < n; j++) for ( int k = j + 1; k < n; k++) // If it satisfy the // given conditions if (arr[k] < arr[i] && arr[i] < arr[j]) { cnt += 1; } // Return the final count return cnt; } // Driver Code int main() { // Given array arr[] int arr[] = { 2, 5, 1, 3, 0 }; int n = sizeof (arr) / sizeof (arr[0]); // Function Call cout << CountTriplets(arr, n) << endl; return 0; } |
Java
// Java program for the above approach class GFG{ // Function to count triplets // with the given conditions static int CountTriplets( int arr[], int n) { int cnt = 0 ; for ( int i = 0 ; i < n; i++) for ( int j = i + 1 ; j < n; j++) for ( int k = j + 1 ; k < n; k++) // If it satisfy the // given conditions if (arr[k] < arr[i] && arr[i] < arr[j]) { cnt += 1 ; } // Return the final count return cnt; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = new int []{ 2 , 5 , 1 , 3 , 0 }; int n = arr.length; System.out.print(CountTriplets(arr, n)); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach # Function to count triplets with the # given conditions def CountTriplets(arr, n): cnt = 0 ; for i in range ( 0 , n): for j in range (i + 1 , n): for k in range (j + 1 , n): # If it satisfy the # given conditions if (arr[k] < arr[i] and arr[i] < arr[j]): cnt + = 1 ; # Return the final count return cnt; # Driver Code # Given array arr[] arr = [ 2 , 5 , 1 , 3 , 0 ]; n = len (arr); # Function Call print (CountTriplets(arr, n)) # This code is contributed by Code_Mech |
C#
// C# program for the above approach using System; class GFG{ // Function to count triplets // with the given conditions static int CountTriplets( int []arr, int n) { int cnt = 0; for ( int i = 0; i < n; i++) for ( int j = i + 1; j < n; j++) for ( int k = j + 1; k < n; k++) // If it satisfy the // given conditions if (arr[k] < arr[i] && arr[i] < arr[j]) { cnt += 1; } // Return the final count return cnt; } // Driver Code public static void Main( string [] args) { // Given array arr[] int []arr = new int []{ 2, 5, 1, 3, 0 }; int n = arr.Length; Console.Write(CountTriplets(arr, n)); } } // This code is contributed by Ritik Bansal |
Javascript
<script> // Javascript program for the above approach // Function to count triplets with the // given conditions function CountTriplets(arr, n) { let cnt = 0; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) for (let k = j + 1; k < n; k++) // If it satisfy the // given conditions if (arr[k] < arr[i] && arr[i] < arr[j]) { cnt += 1; } // Return the final count return cnt; } // Given array arr[] let arr = [ 2, 5, 1, 3, 0 ]; let n = arr.length; // Function Call document.write(CountTriplets(arr, n)); </script> |
4
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: We can reduce the complexity from N^3 to N^2, using the below steps:
- Run two loops to find pairs (i, j) such that i < j and arr[j] > arr[i] and keep the count of these pairs as cnt.
- While in the above loop if there exists any element such arr[j] < arr[i] then increment the count of triplets by cnt as the current element is the Kth element such that a[k] < a[i] < a[j] for triplet i < j < k.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count triplets int CountTriplets( int a[], int n) { // To store count of total triplets int ans = 0; for ( int i = 0; i < n; i++) { // Initialize count to zero int cnt = 0; for ( int j = i + 1; j < n; j++) { // If a[j] > a[i] then, // increment cnt if (a[j] > a[i]) cnt++; // If a[j] < a[i], then // it mean we have found a[k] // such that a[k] < a[i] < a[j] else ans += cnt; } } // Return the final count return ans; } // Driver code int main() { int arr[] = { 2, 5, 1, 3, 0 }; int n = sizeof (arr) / sizeof (arr[0]); cout << CountTriplets(arr, n) << endl; return 0; } |
Java
// Java program for the above approach class GFG{ // Function to count triplets static int CountTriplets( int a[], int n) { // To store count of total triplets int ans = 0 ; for ( int i = 0 ; i < n; i++) { // Initialize count to zero int cnt = 0 ; for ( int j = i + 1 ; j < n; j++) { // If a[j] > a[i] then, // increment cnt if (a[j] > a[i]) cnt++; // If a[j] < a[i], then // it mean we have found a[k] // such that a[k] < a[i] < a[j] else ans += cnt; } } // Return the final count return ans; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 5 , 1 , 3 , 0 }; int n = arr.length; System.out.print(CountTriplets(arr, n)); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 program for # the above approach # Function to count triplets def CountTriplets(a, n): # To store count # of total triplets ans = 0 for i in range (n): # Initialize count to zero cnt = 0 for j in range (i + 1 , n): # If a[j] > a[i] then, # increment cnt if (a[j] > a[i]): cnt + = 1 # If a[j] < a[i], then # it mean we have found a[k] # such that a[k] < a[i] < a[j] else : ans + = cnt # Return the final count return ans # Driver code if __name__ = = "__main__" : arr = [ 2 , 5 , 1 , 3 , 0 ] n = len (arr) print (CountTriplets(arr, n)) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; class GFG{ // Function to count triplets static int CountTriplets( int []a, int n) { // To store count of total triplets int ans = 0; for ( int i = 0; i < n; i++) { // Initialize count to zero int cnt = 0; for ( int j = i + 1; j < n; j++) { // If a[j] > a[i] then, // increment cnt if (a[j] > a[i]) cnt++; // If a[j] < a[i], then // it mean we have found a[k] // such that a[k] < a[i] < a[j] else ans += cnt; } } // Return the final count return ans; } // Driver code public static void Main() { int []arr = { 2, 5, 1, 3, 0 }; int n = arr.Length; Console.Write(CountTriplets(arr, n)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program for the above approach // Function to count triplets function CountTriplets(a, n) { // To store count of total triplets let ans = 0; for (let i = 0; i < n; i++) { // Initialize count to zero let cnt = 0; for (let j = i + 1; j < n; j++) { // If a[j] > a[i] then, // increment cnt if (a[j] > a[i]) cnt++; // If a[j] < a[i], then // it mean we have found a[k] // such that a[k] < a[i] < a[j] else ans += cnt; } } // Return the final count return ans; } // Driver code let arr = [ 2, 5, 1, 3, 0 ]; let n = arr.length; document.write(CountTriplets(arr, n)); // This code is contributed by rameshtravel07 </script> |
4
Time Complexity: O(N2)
Auxiliary Space: O(1)