Selecting Three People

Posted: 3 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

There are ‘N’ people standing in a row having heights that may or may not be the same. You have to find the number of ways to select three people with heights in strictly increasing order along with their positions. Formally, the height of first people < the height of second people < the height of third people and the position of first people < the position of second people < the position of third people.

Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’, which denotes the number of people in the row.

The second line of each test case will contain ‘N’ integers that denote each particular person’s height in the row.
Output Format :
For each test case, print the number of ways to select three people according to the condition given in the description.

Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
3 <= N <= 100
1 <= ARR[i] <= 10 ^ 5

Where 'ARR[i]' denotes the height of the i-th people in the row.

Time limit: 1 sec
Approach 1

The basic idea is to iterate through all possible triplet of people in the row using three loops. 

 

The steps are as follows:

 

  1. Create a variable named “count” to count the number of ways.
  2. Iterate through “arr” (say, iterator = ‘i’)
    • Iterate through “arr” from (‘i’ + 1) to the end of the ARR (say, iterator = ‘j’)
      • Iterator through “arr” from (‘j’ + 1) to the end of the ARR (say, iterator = ‘k’)
        • Check if arr[ i ] < arr[ j ] < arr[ k ] then increment the “count” by 1.
  3. Return “count”.
Try Problem