Print all triplets in sorted array that form AP

The problem “Print all triplets in sorted array that form AP” states that we have given a sorted integer array. The task is to find out all the possible triplets that can form an Arithmetic Progression.

Table of Contents

Example

arr[] = {1,3,5,7,8,12,15,16,20,30}

(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

Explanation

These all are the triplets that form an A.P.

arr[] = {2,4,5,6,9,14,18,24}

(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

Explanation

These all are the triplets that form an A.P.

Algorithm

Loop from i=1 to n-1(not included).
Set the value of j to one less than i and value of k to one more than i.
While j > = 0 && k < n.
1. Check if the sum of the two current array elements is equal to twice of the other array element,
  1. If true, then print the current three elements and decrease and increase the value of k and j respectively.
2. Check if the sum of the two elements is less than twice of another element, then, increase k by 1.
3. Check if the sum of the two elements is greater than twice of another element, then, decrease j by 1.

Explanation

We have given a sorted array. We are asked to find out all the triplets that can form an Arithmetic Progression. An arithmetic progression can be defined as a number sequence in which all the elements come consecutively with a particular distance between them along the whole sequence. We will find the triplet by the formula of an AP which states a + c = 2b that is if the sum of the two numbers is equal to the twice of the third number.

Traverse the whole array with one for loop and a while loop, ‘while loop’ is going to check if we find the three of the elements can form AP or not. We will set the value of j to one less than the value of i and value of k to one more than the value of i, whenever we traverse through the for loop. It will pick up an element for us to check, so every time we have three elements to check arr[i], arr[j], and arr[k], the value of i, j, and k that will vary for each traversal whether in for loop or in while loop.

If we found the sum of two elements is equal to the third element, we are going to print those three array elements, they can form an AP. We will update the value of j and k according to our algorithm. If we found the sum of two elements less than twice of the third element. We will increase the value of k, or if we found the sum greater than twice of the third element, we decrease the value of j. This will go on until we traverse the whole array and find out all the possible elements that can form an AP.

Code

C++ code to print all triplets in sorted array that form AP

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}

Java code to Print all triplets in sorted array that form AP

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}

Complexity Analysis

Time Complexity

O(n²) where “n” is the number of elements in the array. Because we have two nested loop where the first loop runs until we reach the end and then the second nested loop is used to find the elements of AP.

Space Complexity

O(1) as no extra space is required.