Number of Groups Consisting of 3 Decreasing values

Question

This question already has an answer here:

• How to find 3 numbers in increasing order and increasing indices in an array in linear time 13 answers
• is it possible to find all the triplets in the given array for the O (n) time? 1 answer

A decreasing triple is defined as a set of 3 values {a, b, c} that decrease in magnitude from left to right such that a > b > c.

How could one find the number of these triples in an array of integers where the indices of the triple {i, j, k} are increasing such that i < j < k.

For example, consider the following examples:

{4, 5, 2, 1}
2 decreasing triples: {4, 2, 1} and {5, 2, 1}

{6, 1, 2, 4, 5, 3}
2 decreasing triples: {6, 5, 3} and {6, 4, 3}

{5, 4, 3, 2, 1}
10 decreasing triples:
{5, 4, 3}, {5, 4, 2}, {5, 4, 1}, {5, 3, 2}, {5, 3, 1},
{5, 2, 1}, {4, 3, 2}, {4, 3, 1}, {4, 2, 1}, {3, 2, 1}

The O(n^3) solution is trivial of course; here is an implementation in java: *note: the arrays are of longs, but that is a minor implementation detail

public static long countTriples(long[] measurements)
{
     // O(n^3)
     long count = 0L;

     for(int i = 0; i < measurements.length; i++)
     {
         for(int j = i + 1; j < measurements.length; j++)
         {
             if ( measurements[j] < measurements[i] )
             {

                 for(int k = j + 1; k < measurements.length; k++)
                 {
                     if ( measurements[k] < measurements[j] )
                     {
                         count++;
                     }
                 }
             }
         }
      }   
     return count;
  }
}

I began an O(n) method to locate decreasing triples; it successfully identified triples, but I couldn't get it to count right when the middle value of a given triple was involved in more than one. Here is what I have of that right now:

public static long countTriples(long[] measurements)
{
      ArrayList<Long> greaterOnLeft = new ArrayList<Long>();
      ArrayList<Long> lessOnRight = new ArrayList<Long>();

      HashSet<Long> min = new HashSet<Long>();
      min.add(measurements[measurements.length - 1]);
      HashSet<Long> max = new HashSet<Long>();
      max.add(measurements[0]);

      for(int i = 0; i < measurements.length; i++)
      {
          min.add(measurements[measurements.length - i - 1]);
          max.add(measurements[i]);
          System.out.println("max: " + max + ", min: " + min);
          for(long n : max)
              if (measurements[i] < n) greaterOnLeft.add(measurements[i]);
          for(long n : min)
              if (measurements[measurements.length - i - 1] > n) lessOnRight.add(measurements[measurements.length - i - 1]);
      }

      long count = 0;
      for(long n : greaterOnLeft)
      {
          if(lessOnRight.contains(n)) count++;
      }
      return count;
}

The idea for this approach came from a HashSet method for locating the middle indices of such tripples from this post:

How to find 3 numbers in increasing order and increasing indices in an array in linear time

Answer 1

I believe this can be solved in O(n^2) time rather trivially:

public static long countTriples(long[] measurements)
{
  // O(n^2)
      long count = 0;
      for(int i = 1; i < measurements.length - 1; i++)
      {
          long right = 0, left = 0;

          for(int j = 0; j < measurements.length; j++)
          {
              if(j < i && measurements[j] > measurements[i]) right++;
              else if (j > i && measurements[j] < measurements[i]) left++;
          }
          count += right * left;
      }
      return count;
}