Local Min and Max Sequence Ordering

Given an integer array arr[] representing a sequence of elevations, Return an array that includes:

The first and last elements of the array.
Every element where the trend of the sequence changes that is, where the direction of change switches from increasing to decreasing or from decreasing to increasing.

Note: Consecutive equal elements (flat segments) should be treated as a single elevation and ignored for detecting direction changes.

Input: arr[] = [6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4]
Output: [6, -2, 5, -1, 4]
Explanation: Starts from 6 goes down to -2, -2 is the breaking point then 5, 5 is the breaking point then from 5 goes down to -1, -1 is breaking point then 4.

Input: arr[] = [6, 10, 11, 13]
Output: [6, 13]
Explanation: 6 is the starting point and 13 is last point.
Input: arr[] = [1, 1]
Output: [1]
Explanation: Since we start from 1 but do not move further.

Try it on GfG Practice

[Approach] Traversal with Turning Point Detection - O(n) Time and O(1) Space

The idea is to follow the changes in elevation as we move through the array. We start by adding the first point. Then, for each point, we check if it forms a peak or a valley—that means the direction of the trail is changing there. If it does, we include it. At the end, we add the last point if it’s not already there. This way, we keep only the important turning points and ignore the flat or straight parts.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> extractPoints(vector<int>& arr) {
    int n = arr.size();
    vector<int> ans;

    if (n == 0) return ans;

    ans.push_back(arr[0]);

    for (int i = 1; i < n - 1; i++) {

        // check for a peak: strictly greater 
        // than both the last added and the next element
        if (arr[i] > ans.back()
                && arr[i] > arr[i + 1]) {
            ans.push_back(arr[i]);
        }

        // check for strictly smaller than 
        // both the last added and the next element
        else if (ans.back() > arr[i]
                && arr[i] < arr[i + 1]){
            ans.push_back(arr[i]);
        }
    }

    // include the last point if it is 
    // different from the last added point
    if (ans.back() != arr[n - 1]) {
        ans.push_back(arr[n - 1]);
    }

    return ans;
}

int main() {
    vector<int> arr = {6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4};
    vector<int> result = extractPoints(arr);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    return 0;
}

Java

import java.util.ArrayList;

class GfG {
    public static ArrayList<Integer> extractPoints(int[] arr) {
        int n = arr.length;
        ArrayList<Integer> ans = new ArrayList<>();

        if (n == 0) return ans;

        // Always include the first point
        ans.add(arr[0]);

        for (int i = 1; i < n - 1; i++) {

            // check for a peak: strictly greater 
            // than both the last added and the next element
            if (arr[i] > ans.get(ans.size() - 1)
                            && arr[i] > arr[i + 1]) {
                ans.add(arr[i]);
            }

            // check for a valley: strictly smaller 
            // than both the last added and the next element
            else if (ans.get(ans.size() - 1) > arr[i]
                                && arr[i] < arr[i + 1]) {
                ans.add(arr[i]);
            }
        }

        // include the last point if it is 
        // different from the last added point
        if (ans.get(ans.size() - 1) != arr[n - 1]) {
            ans.add(arr[n - 1]);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4};
        ArrayList<Integer> result = extractPoints(arr);

        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

def extractPoints(arr):
    n = len(arr)
    result = []

    if n == 0:
        return result

    # Always include the first point
    result.append(arr[0])

    for i in range(1, n - 1):

        # check for a peak: strictly greater 
        # than both the last added and the next element
        if arr[i] > result[-1] and arr[i] > arr[i + 1]:
            result.append(arr[i])

        # check for a valley: strictly smaller 
        # than both the last added and the next element
        elif result[-1] > arr[i] and arr[i] < arr[i + 1]:
            result.append(arr[i])

    # include the last point if it is 
    # different from the last added point
    if result[-1] != arr[-1]:
        result.append(arr[-1])

    return result

if __name__ == "__main__":
    arr = [6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4]
    print(*extractPoints(arr))

using System;
using System.Collections.Generic;

class GfG {
    public List<int> extractPoints(int[] arr) {
        int n = arr.Length;
        List<int> result = new List<int>();

        if (n == 0) return result;

        // always include the first point
        result.Add(arr[0]);

        for (int i = 1; i < n - 1; i++) {

            // check for a peak: strictly greater 
            // than both the last added and the next element
            if (arr[i] > result[result.Count - 1]
                                && arr[i] > arr[i + 1]) {
                result.Add(arr[i]);
            }

            // check for a valley: strictly smaller 
            // than both the last added and the next element
            else if (result[result.Count - 1] > arr[i]
                                && arr[i] < arr[i + 1]) {
                result.Add(arr[i]);
            }
        }

        // include the last point if it is 
        // different from the last added point
        if (result[result.Count - 1] != arr[n - 1]) {
            result.Add(arr[n - 1]);
        }

        return result;
    }

    static void Main() {
        int[] arr = {6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4};

        GfG obj = new GfG();
        List<int> result = obj.extractPoints(arr);

        foreach (int val in result) {
            Console.Write(val + " ");
        }
    }
}

JavaScript

function extractPoints(arr) {
    const n = arr.length;
    const result = [];
    if (n === 0) return result;

    // Always include the first point
    result.push(arr[0]);
    for (let i = 1; i < n - 1; i++) {

        // check for a peak: strictly greater 
        // than both the last added and the next element
        if (arr[i] > result[result.length - 1]
                                && arr[i] > arr[i + 1]) {
            result.push(arr[i]);
        }

        // check for a valley: strictly smaller 
        // than both the last added and the next element
        else if (result[result.length - 1] > arr[i]
                                && arr[i] < arr[i + 1]) {
            result.push(arr[i]);
        }
    }

    // include the last point if it is 
    // different from the last added point
    if (result[result.length - 1] !== arr[n - 1]) {
        result.push(arr[n - 1]);
    }

    return result;
}

// Driver Code
const arr = [6, 4, 2, -2, 5, 3, 2, 2, -1, -1, 4];
const result = extractPoints(arr);
console.log(...result);

Output

6 -2 5 -1 4

Local Min and Max Sequence Ordering

[Approach] Traversal with Turning Point Detection - O(n) Time and O(1) Space

Explore