Find 3 Peak And Valley In An Array Separated By N Indices

Given an array of size n, we have to find 3 peak values and 3 trough values in the array such that each peak values are separated by another peak value by n entries.
Similarly, each trough value must be n days separated from the other trough values. For eg:

int arr[] = {1, 5, 6, 4, 3, 3, 10, 2, 8, 6, 11, 4, 10};
int distance = 2;

In above example, peak values are – 6, 10 and 11 (which are 2 indices apart).

valley values are – 1, 3 and 2 (which are 2 indices apart).

Let’s have a look at the program which solves above problem.

/*****************************************************************************************
 * 
 * Find peak and troughs in 60 items where,
 *      1) Each peak/troughs should have been atleast +/- 10 days
 * 
 *****************************************************************************************/

#include "iostream"


float prices[]  =  {341,
                    328.85,
                    353,
                    355.6,
                    358.55,
                    350.55,
                    353.55,
                    370.65,
                    364.3,
                    360.8,
                    357.2,
                    355.2,
                    359.85,
                    372.7,
                    367,
                    371.15,
                    367.1,
                    368.15,
                    378.55,
                    383.9,
                    381.1,
                    387.7,
                    387.6,
                    389.6,
                    383.65,
                    395.65,
                    405.05,
                    394.2,
                    394.95,
                    390.15,
                    407.25,
                    406.25,
                    395.6,
                    389.5,
                    399.55,
                    415.2,
                    411.75,
                    402.35,
                    406.95,
                    393.15,
                    390.15,
                    392.25,
                    394.8,
                    397.05,
                    393.1,
                    355.1,
                    335.95,
                    333.1,
                    310.7,
                    282.1,
                    282.35,
                    275.65,
                    280.95,
                    283.7,
                    294.85,
                    302.55,
                    298.6,
                    294.45,
                    303.85,
                    307.25};

#define DISTANCE 10
#define CHECK_RANGE(X) (X > peak_1_low && X < peak_1_high) || ((X > peak_2_low && X < peak_2_high))
#define CHECK_RANGE_TROUGH(X) (X > trough_1_low && X < trough_1_high) || ((X > trough_2_low && X < trough_2_high))
#define ASSIGN_VALUE(X) (X == 1 ? peak_1: X == 2 ? peak_2: peak_3)
#define ASSIGN_VALUE_TROUGH(X) (X == 1 ? trough_1: X == 2 ? trough_2: trough_3)

using namespace std;

void find_peak_troughs (float* arr, int size)
{
    /* Below items will contain the indexes */
    int peak_1 = 0;
    int peak_2 = 0;
    int peak_3 = 0;
    int trough_1 = 0;
    int trough_2 = 0;
    int trough_3 = 0;

    for (int i = 1; i < 4; i++)
    {
        int index = -1;
        int peak_1_low = (peak_1 == 0 ? 0 : peak_1 - DISTANCE);
        int peak_1_high = (peak_1 == 0 ? 0 : peak_1 + DISTANCE);
        int peak_2_low = (peak_2 == 0 ? 0 : peak_2 - DISTANCE);
        int peak_2_high = (peak_2 == 0 ? 0 : peak_2 + DISTANCE);
        for (int j = 0; j < size; j++)
        {
            if (CHECK_RANGE (j)) {
                continue;
            }
            if (index == -1 || arr[index] < arr[j]) {
                index = j;
            }
        }
        ASSIGN_VALUE(i) = index;
    }

    for (int i = 1; i < 4; i++)
    {
        int index = -1;
        int trough_1_low = (trough_1 == 0 ? 0 : trough_1 - DISTANCE);
        int trough_1_high = (trough_1 == 0 ? 0 : trough_1 + DISTANCE);
        int trough_2_low = (trough_2 == 0 ? 0 : trough_2 - DISTANCE);
        int trough_2_high = (trough_2 == 0 ? 0 : trough_2 + DISTANCE);
        for (int j = 0; j < size; j++)
        {
            if (CHECK_RANGE_TROUGH (j)) {
                continue;
            }
            if (index == -1 || arr[index] > arr[j]) {
                index = j;
            }
        }
        ASSIGN_VALUE_TROUGH(i) = index;
    }
    cout << "Peak 1 index: " << peak_1 << " Value: " << arr[peak_1] << endl;
    cout << "Peak 2 index: " << peak_2 << " Value: " << arr[peak_2] << endl;
    cout << "Peak 3 index: " << peak_3 << " Value: " << arr[peak_3] << endl;
    cout << "Trough 1 index: " << trough_1 << " Value: " << arr[trough_1] << endl;
    cout << "Trough 2 index: " << trough_2 << " Value: " << arr[trough_2] << endl;
    cout << "Trough 3 index: " << trough_3 << " Value: " << arr[trough_3] << endl;
}

int main ()
{
    find_peak_troughs (prices, sizeof(prices)/sizeof(prices[0]));
}

Let’s analyze the output of above program.

Peak 1 index: 35 Value: 415.2
Peak 2 index: 25 Value: 395.65
Peak 3 index: 13 Value: 372.7
Trough 1 index: 51 Value: 275.65
Trough 2 index: 1 Value: 328.85
Trough 3 index: 11 Value: 355.2

Leave a Reply

Your email address will not be published. Required fields are marked *