Problem Statement
Given a list of integers, we need to find which indices contain a local mimima or local maxima and return a list of all of those indices. A local minima is an index of a value where the previous and subsequent values are both larger than the value iteslf. A local maxima is an index where the previous and next values are both smaller. In this article, we'll also consider the first and last indices minima and/or maxima if they are different than the values immediately preceding / superceding them. This algorithm can be useful in questions on LeetCode and other similar sites, as well as on actual interviews, either as a direct question, or as a part of a larger problem to solve.
A few example inputs and outputs are given below:
Input List | Indices of Local Minima and Maxima |
---|---|
[3, 2, 1, 2, 3] | Indices [0, 2, 4] with values of [3, 1, 3] |
[1, 2, 3, 1] | Indices [0, 2, 3] with values of [1, 3, 1] |
[1, 3, 2, 3, 4] | Indices of [0, 1, 2, 4] with values of [1, 3, 2, 4] |
[1, 1, 1, 1, 1] | [] |
[1, 0, 0, 0, 1] | Indices of [0, 1, 4] with values of [1, 0, 1] |
Note the last example above: in cases of repeats, we will include the first element of the repeats as the index for the minima / maxima.
Analysis and Approach
We will iterate through the input exactly once to collect the indices. While iterating, we'll use two variables to keep track of the direction of the previous comparison: -1 or 1, and a boolean indicating if the last two values are equal. We're seperating these two variables so that we can preserve the direction of the last non-equal comparison. In each iteration, we'll check if the comparison between this value and the next is different than the direction previously recorded. If it is, we'll mark this index as a local minima / maxima. If the next direction is 0 and the previous value is not, then we'll still add this index, as this is a case where we've reached a minima or maxima with a series of repeated terms, such as index 1 in the last example above.
In our implementation below, we'll return a single array with indices containing both local minima and local maxima. However, the code can be modified to return two seperate arrays, one for each type, by implementing logic to select the appropriate array based on the direction change. It could also be modified depending upon how we would need it to behave: should repeats be considered minima / maxima, should we include the first and last indices, etc.
Note on An Approach Which Ignores Subsequent Duplicates
In our algorithm, we are account for minima / maxima which have subsequent duplicate values, such as the last example above. If we wanted to ignore those, our code can simply iterate through the array and add each index where:
- The value is greater than the previous value and greater than the next, indicating a local maxima.
- The value is less than the previous value and less than the next, indicating a local minima.
Full Code Implementation
The algorithm described above is implemented below in multiple programming languages. Note that there will be some slight differences; each language provides its own types of data structures and comparison algorithms.