Given an array arr[] consisting of N integers, the task is to find the number of triplets whose indices and elements at that indices are in increasing order.
Examples:
Input: arr[] = {1, 2, 4, 3}
Output: 2
Explanation: There are 2 possible triplets in the given array such that the elements are in increasing order, i.e, {1, 2, 4} and {1, 2, 3}.Input: arr[] = {1, 2, 3, 4, 5}
Output: 10
Naive Approach: The given problem can be solved by iterating over all the possible triplets (i, j, k) of the given array and keep track of the number of triplets whose indices and elements at that indices are in increasing order. After checking for all the triplets, print the total count of triplets obtained.
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order int countTriplets( int arr[], int n) { // Stores the count of valid triplets int totalCount = 0; // Iterating over all the possible triplets // (i, j, k) of the given array and finding // increasing order for ( int i=0;i<n;i++) { for ( int j=0;j<n;j++) { for ( int k=0;k<n;k++) { if (arr[i]<arr[j]&&arr[j]<arr[k]) totalCount++; } } } // Return Answer return totalCount; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); cout << countTriplets(arr, N); return 0; } // This code is contributed by Utkarsh Kumar |
Java
// Java program of the above approach import java.util.*; public class Main { // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order static int countTriplets( int arr[], int n) { // Stores the count of valid triplets int totalCount = 0 ; // Iterating over all the possible triplets // (i, j, k) of the given array and finding // increasing order for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { for ( int k = 0 ; k < n; k++) { if (arr[i] < arr[j] && arr[j] < arr[k]) { totalCount++; } } } } // Return Answer return totalCount; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = arr.length; System.out.println(countTriplets(arr, N)); } } |
C#
// C# program of the above approach using System; public class GFG{ // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order static int countTriplets( int [] arr, int n) { // Stores the count of valid triplets int totalCount = 0; // Iterating over all the possible triplets // (i, j, k) of the given array and finding // increasing order for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { for ( int k = 0; k < n; k++) { if (arr[i] < arr[j] && arr[j] < arr[k]) { totalCount++; } } } } // Return Answer return totalCount; } // Driver Code static public void Main() { int [] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.WriteLine(countTriplets(arr, N)); } } // This code is contributed by Pushpesh Raj. |
Python3
# Python program of the above approach # Function to find the count of triplets # whose indices and elements at that indices # are also in increasing order def countTriplets(arr, n): # Stores the count of valid triplets totalCount = 0 # Iterating over all the possible triplets # (i, j, k) of the given array and finding # increasing order for i in range (n): for j in range (n): for k in range (n): if (arr[i] < arr[j] and arr[j] < arr[k]): totalCount + = 1 # Return Answer return totalCount # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 ] N = len (arr) print (countTriplets(arr, N)) |
Javascript
// Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order function countTriplets(arr, n) { // Stores the count of valid triplets let totalCount = 0; // Iterating over all the possible triplets // (i, j, k) of the given array and finding // increasing order for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { for (let k = 0; k < n; k++) { if (arr[i] < arr[j] && arr[j] < arr[k]) { totalCount++; } } } } // Return Answer return totalCount; } // Driver Code const arr = [1, 2, 3, 4, 5]; const N = arr.length; console.log(countTriplets(arr, N)); |
10
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by the observation that for any given index i, the number of triplets having arr[i] as their middle element will be the count of integers smaller than arr[i] in the range [1, i – 1] * count of integers larger that arr[i] in the range [i + 1, N]. Below are the steps to follow to solve the given problem using the above observation:
- Initialize a variable, totalCount as 0 which stores the count of valid triplets.
- Iterate array arr[] over the range [1, N – 2] using the variable i and perform the following steps:
- Count the number of values less than arr[i] over the range [0, i – 1] and store the value in a variable K1.
- Count the number of values greater than arr[i] over the range [i + 1, N – 1], and store the value in a variable K2.
- Add the value of K1*K2 to the totalCount.
- The value stored in totalCount is the required answer.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find number of integers // smaller than value in range [0, N] int countSmaller( int arr[], int N, int value) { // Stores the count of integers int count = 0; // Iterate the given array for ( int i = 0; i < N; i++) { if (arr[i] < value) count++; } // Return total count return count; } // Function to find number of integers // greater than value in range [i, N] int countLarger( int arr[], int i, int N, int value) { // Stores the count of integers int count = 0; // Iterate the given array while (i < N) { if (arr[i] > value) count++; i++; } // Return total count return count; } // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order int countTriplets( int arr[], int N) { // Stores the count of valid triplets int totalCount = 0; // Loop to iterate over the array for ( int i = 1; i < N - 1; i++) { // Count of smaller elements than // arr[i] in range [0, i-1] int K1 = countSmaller(arr, i, arr[i]); // Count of greater elements than // arr[i] in range [i+1, N] int K2 = countLarger(arr, i + 1, N, arr[i]); // Add to total count totalCount += K1 * K2; } // Return Answer return totalCount; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); cout << countTriplets(arr, N); return 0; } |
Java
// Java program of the above approach import java.io.*; class GFG { // Function to find number of integers // smaller than value in range [0, N] static int countSmaller( int arr[], int N, int value) { // Stores the count of integers int count = 0 ; // Iterate the given array for ( int i = 0 ; i < N; i++) { if (arr[i] < value) count++; } // Return total count return count; } // Function to find number of integers // greater than value in range [i, N] static int countLarger( int arr[], int i, int N, int value) { // Stores the count of integers int count = 0 ; // Iterate the given array while (i < N) { if (arr[i] > value) count++; i++; } // Return total count return count; } // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order static int countTriplets( int arr[], int N) { // Stores the count of valid triplets int totalCount = 0 ; // Loop to iterate over the array for ( int i = 1 ; i < N - 1 ; i++) { // Count of smaller elements than // arr[i] in range [0, i-1] int K1 = countSmaller(arr, i, arr[i]); // Count of greater elements than // arr[i] in range [i+1, N] int K2 = countLarger(arr, i + 1 , N, arr[i]); // Add to total count totalCount += K1 * K2; } // Return Answer return totalCount; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = arr.length; System.out.println(countTriplets(arr, N)); } } // This code is contributed by Dharanendra L V. |
Python3
# Python program of the above approach # Function to find number of integers # smaller than value in range [0, N] def countSmaller(arr, N, value): # Stores the count of integers count = 0 # Iterate the given array for i in range (N): if (arr[i] < value): count + = 1 # Return total count return count # Function to find number of integers # greater than value in range [i, N] def countLarger( arr, i, N, value): # Stores the count of integers count = 0 # Iterate the given array while (i < N): if (arr[i] > value): count + = 1 i + = 1 # Return total count return count # Function to find the count of triplets # whose indices and elements at that indices # are also in increasing order def countTriplets( arr, N): # Stores the count of valid triplets totalCount = 0 # Loop to iterate over the array for i in range ( 0 , N - 1 ): # Count of smaller elements than # arr[i] in range [0, i-1] K1 = countSmaller(arr, i, arr[i]) # Count of greater elements than # arr[i] in range [i+1, N] K2 = countLarger(arr, i + 1 , N, arr[i]) # Add to total count totalCount + = K1 * K2 # Return Answer return totalCount # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 ]; N = len (arr) print (countTriplets(arr, N)) # This code is contributed by shivanisinghss2110 |
C#
// C# program of the above approach using System; class GFG { // Function to find number of integers // smaller than value in range [0, N] static int countSmaller( int [] arr, int N, int value) { // Stores the count of integers int count = 0; // Iterate the given array for ( int i = 0; i < N; i++) { if (arr[i] < value) count++; } // Return total count return count; } // Function to find number of integers // greater than value in range [i, N] static int countLarger( int [] arr, int i, int N, int value) { // Stores the count of integers int count = 0; // Iterate the given array while (i < N) { if (arr[i] > value) count++; i++; } // Return total count return count; } // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order static int countTriplets( int [] arr, int N) { // Stores the count of valid triplets int totalCount = 0; // Loop to iterate over the array for ( int i = 1; i < N - 1; i++) { // Count of smaller elements than // arr[i] in range [0, i-1] int K1 = countSmaller(arr, i, arr[i]); // Count of greater elements than // arr[i] in range [i+1, N] int K2 = countLarger(arr, i + 1, N, arr[i]); // Add to total count totalCount += K1 * K2; } // Return Answer return totalCount; } // Driver Code public static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.WriteLine(countTriplets(arr, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find number of integers // smaller than value in range [0, N] function countSmaller(arr, N, value) { // Stores the count of integers let count = 0; // Iterate the given array for (let i = 0; i < N; i++) { if (arr[i] < value) count++; } // Return total count return count; } // Function to find number of integers // greater than value in range [i, N] function countLarger(arr, i, N, value) { // Stores the count of integers let count = 0; // Iterate the given array while (i < N) { if (arr[i] > value) count++; i++; } // Return total count return count; } // Function to find the count of triplets // whose indices and elements at that indices // are also in increasing order function countTriplets(arr, N) { // Stores the count of valid triplets let totalCount = 0; // Loop to iterate over the array for (let i = 1; i < N - 1; i++) { // Count of smaller elements than // arr[i] in range [0, i-1] let K1 = countSmaller(arr, i, arr[i]); // Count of greater elements than // arr[i] in range [i+1, N] let K2 = countLarger(arr, i + 1, N, arr[i]); // Add to total count totalCount += K1 * K2; } // Return Answer return totalCount; } // Driver Code let arr = [1, 2, 3, 4, 5]; let N = arr.length; document.write(countTriplets(arr, N)); // This code is contributed by Potta Lokesh </script> |
10
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!