Day 56: Magic Triplets

/*
Magic Triplets

Given an array of size n, a triplet (a[i], a[j], a[k]) is called a Magic Triplet if a[i] < a[j] < a[k] and i < j < k.  Count the number of magic triplets in a given array.
 

Example 1:

Input: arr = [3, 2, 1]
Output: 0
Explanation: There is no magic triplet.

Example 2:

Input: arr = [1, 2, 3, 4]
Output: 4
Explanation: Fours magic triplets are 
(1, 2, 3), (1, 2, 4), (1, 3, 4) and 
(2, 3, 4).
 

Your Task:
You don't need to read or print anything. Your task is to complete the function countTriplets() which takes the array nums[] as input parameter and returns the number of magic triplets in the array.

 

Expected Time Complexity: O(N2) 
Expected Space Complexity: O(1)
 

Constraints:
1 <= length of array <= 1000
1 <= arr[i] <= 100000
*/

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            int n = Integer.parseInt(br.readLine().trim());
            String s = br.readLine().trim();
            String[] S = s.split(" ");
            int[] nums = new int[n];
            for(int i = 0; i < n; i++){
                nums[i] = Integer.parseInt(S[i]);
            }
            Solution ob = new Solution();
            int ans = ob.countTriplets(nums);
            System.out.println(ans);         
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution{
    public int countTriplets(int[] nums){
        int ans = 0;
        int n = nums.length;
       
         
       for(int i = 1;i<n-1;i++)
       {    int smaller= 0;
           for(int j = i-1;j>=0;j--)
           {
               if(nums[j]<nums[i])
                smaller++;
           }
           int larger = 0;
           for(int k = i+1;k<n;k++)
           {
               if(nums[k]>nums[i])
               larger++;
           }
        ans += smaller * larger ;   
           
       }
      
       return ans;
    }
}