Find the sorted triplet in an array

Posted in

Find the sorted triplet in an array
maazbinasad

Maaz Bin Asad
Last updated on May 30, 2024

    Problem

    Given an integer array arr , find a sorted triplet such that arr [i] < arr [j] < arr [k] and 0 <= i < j < k < n , where n is the size of the array.

    Sample Input

    [ 2, 5, 4, 6 ]

    Sample Output

    2 5 6

    Brute Force Approach

    We can traverse the array and consider each element of the array as the middle element and see if we can find one element smaller than it on its left side and one element greater than it on the right side. This approach will take O(N2) time.

    Efficient Approach

    We can traverse through the array and keep track of the minimum element so far. low will store the minimum value index in the triplet, mid will store the index of the middle element of the triplet. If we encounter a variable that is more than the minimum element so far, update low and mid.

    If we find better candidates for the same, we update these two variables. While traversing the array, if we find some element as greater than the element at mid, we find our triplet.

    C++

    #include <iostream>
    #include <vector>
    #include <tuple>
    usingnamespacestd;
    vector<int>ans;
    voidfindTriplet(int arr[], int n)
    {
     int minIndex = 0;
     int low, mid = -1;
     for (int i = 1; i < n; i++)
     {
     if (arr[i] <= arr[minIndex]) {
     minIndex = i;
     }
     elseif (mid == -1) {
     low = minIndex;
     mid = i;
     }
     elseif (arr[i] <= arr[mid]) {
     low = minIndex;
     mid = i;
     }
     else {
     ans.push_back(arr[low]);
     ans.push_back(arr[mid]);
     ans.push_back(arr[i]);
     return;
     }
     }
     return;
    }
    intmain()
    {
     int arr[] = {1, 4, 3, 5 };
     int n = sizeof(arr)/sizeof(arr[0]);
     findTriplet(arr, n);
     cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2];
    }
    

    Output

    1 3 5

    C

    #include<stdio.h>
    int ans[3];
    voidfindTriplet(int arr[], int n)
    {
     int minIndex = 0;
     int low, mid = -1;
     for (int i = 1; i < n; i++)
     {
     if (arr[i] <= arr[minIndex]) {
     minIndex = i;
     }
     elseif (mid == -1) {
     low = minIndex;
     mid = i;
     }
     elseif (arr[i] <= arr[mid]) {
     low = minIndex;
     mid = i;
     }
     else {
     ans[0] = arr[low];
     ans[1] = arr[mid];
     ans[2] = arr[i];
     return;
     }
     }
     return;
    }
    intmain()
    {
     int arr[] = {1, 4, 3, 5 };
     int n = sizeof(arr)/sizeof(arr[0]);
     findTriplet(arr, n);
     printf("%d %d %d", ans[0], ans[1], ans[2]);
    }

    Output

    1 3 5

    Python

    ans = []
    def findTriplet(arr):
     n = len(arr)
     if n < 3:
     return None
     minIndex = 0
     low = 0
     mid = -1
     for i in range(1, n):
     if arr[i] <= arr[minIndex]:
     minIndex = i
     elif mid == -1:
     low = minIndex
     mid = i
     elif arr[i] <= arr[mid]:
     low = minIndex
     mid = i
     else:
     ans.append(arr[low])
     ans.append(arr[mid])
     ans.append(arr[i])
     return
    input = [1, 4, 3, 5]
    findTriplet(input)
    print(ans)

    Output

    [1, 3, 5]

    People are also reading:

    Leave a Comment on this Post

    0 Comments