Magic Triplets

Problem Statement

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.

Problem statement: https://practice.geeksforgeeks.org/problems/magic-triplets4003/1

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).

Approach

Example

[1, 2, 3] -> 1
  1,2,3

[1, 2, 3, 4] -> 4
  1,2,3
  1,2,4
  1,3,4
  2,3,4

So Naive Solution can be via approaching all 3 variables independently.

Like,

  for i in [0, n]:
    first_number = a[i]          # first number
    for j in [i+1, n]:
      if a[j] > first_number:
        second_number = a[j]     # second number
        for k in [j+1, n]:
          if a[k] > second_number:
            third_number = a[k]
            overall_count += 1   # as we got all three numbers

This as we could see costs us O(N³) time complexity

Could we avoid it,
Yes, we could.

We do not need to display all three numbers, we just wanted to count such triplets. Let's think this way, if we got first_number and then second_number we just wanted to know how many numbers are next to second_number which are greater than second_number.
For this, we need to have a pre-iteration of the list to know how many numbers next to the current are greater in value, let's call this array as lookupTable.

Know how to generate the lookup table.

Once we got lookupTable we just need to find the first two numbers and for the second number need to look into the lookup table.

class Solution {
    private int[] generateLookupTable(int[] a) {
        int[] res = new int[a.length]; // result array

        // for every element
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = i+1; j < a.length; j++) {
                // previous value is lesser than new value
                if (a[i] < a[j]) 
                    count++;
            }
            res[i] = count;
        }

        return res;
    }

    public int countTriplets(int[] a) {
        final int[] lookupTable = generateLookupTable(a);
        int res = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = i+1; j < a.length; j++) {
                if (a[i] < a[j])
                    res += lookupTable[j];
            }
        }

        return res;
    }
}

Time Complexity: O(N²)

Space Complexity: O(N)