Detect local minima and maxima, java

Question

Hi,

given is any sequence of integers like 23 7 13 4 8 6. I want to detect local minima and maxima with the following rules:

• the first number in the sequence is a local minimum when the following number is greater
• the last number in the sequence is a local minimum when the previous number is greater
• a number in the sequence is a local minimum when it is smaller than the previous and the following number

I can use the methods hasNextInt and getNextInt.

Currently I am thinking about the algorithm. But I am not sure whether I understand the logic. First I build a tuple and compare its numbers. E.g. I compare 23 and 7. 7 is the local minimum. What would I do then? Build a triple? But what numbers has that triple, 23 7 13 or 13 4 8? I am not sure.

Any ideas?

Update:

Let's say we store the left neighbour and the number in the middle of three numbers:

left    middle    current

0        0         23

23       0         7

23       7         13 <- you have a triple, compare => minimum 7

What would happen then? Set the vars to 0 and start with the next number 4? Or store 7 in left, 13 in the middle to have 4 as current?

Update (this code seems to work):

    int left   = 0;
    int center = 0;
    while(hasNextInt()){
        int current = getNextInt();

        if((left != 0) && (center != 0)){
            if(current > center && center < left){
                System.out.println("Min: "+center);
                left = center; center = current;
            }else{
                left = center; center = current;
            }
        }else if((left != 0) && (center == 0)){
            if(left < current){
                System.out.println("Min: "+left);
                center = current;
            }else{
                center = current;
            }
        }else if((left == 0) && (center == 0)){
            left = current;
        }
    }

    if(left > center){
        System.out.println("Min: "+center);
    }

Thanks for your help!

Answer 1

What you have there looks like a good start.

However, only looking at tuples will no be enough, because you must look at three numbers to detect a local minimum - so you will have to extend your algorithm.

To understand how to do this, try to work a simple example on paper. How would you go about manually finding the local minima? Can you do something similar in your program?

Feel free to post an updated version of your program (by editing the question, adding the new code to the bottom), then we can help if you are still stuck.

Answer to your edit:

What would happen then? Set the vars to 0 and start with the next number 4? Or store 7 in left, 13 in the middle to have 4 as current?

You cannot just set everything to 0; you still need the last two numbers of your triple to start the next triple, because your triples behave like a windows sliding over the list of numbers (this is often referred to as a "sliding window" technique, as many algorithms use it).

You can copy the numbers to their new variables manually.

For more elegance, you could implement this in a separate "Triplet" class. Ideas to consider: That class could check for minima, and let you add a new number, automatically "pushing out" the oldest number.

Answer 2

Keep track of whether you have previously increased or decreased using two booleans. When you read the next number in the array, check again and compare the 4 booleans as so:

local_minimum = previously_decreased && just_increased;
local_maximum = previously_increased && just_decreased;

Then store just -> previously and continue.

At the beginning, both previous_ booleans should be set to true. At the end you will require another pass of the loop setting both just_ booleans to true.

Obviously, these increase/decrease booleans are strict, so equal values will give both booleans as false.

Hope that helps.

Answer 3

Here is a suggestion:

private void findMin() {

    int count = 0; // To handle special case of singleton list

    int left  = Integer.MAX_VALUE;
    int mid   = Integer.MAX_VALUE;
    int right = Integer.MAX_VALUE;

    while (hasNextInt()) {
        count++;
        left = mid;
        mid = right;
        right = getNextInt();

        if (right > mid && mid < left)
            System.out.println("local min: " + mid);
    }

    if (count > 1 && right < mid)
        System.out.println("local min: " + right);
}

(Ideone demo available here.)

Answer 4

Following the definitions think of a triplet somewhere in the middle of the sequence:

... A, B, C,  ...

obviously B local minima iff (if and only if): A-B > 0 && B-C <0

otherwise B local maxima iff: A-B < 0 && B-C >0

nothing particular otherwise

If you implement this logic, and iterate over the list, specially handling the cases at the ends you should be able to find all the local optima in O(n).