Java arrays question with multiple answers

Question

I have a java problem at codewars.

In this kata, you will write a function that returns the positions and the values of the "peaks" (or local maxima) of a numeric array.

For example, the array arr = [0, 1, 2, 5, 1, 0] has a peak at position 3 with a value of 5 (since arr[3] equals 5).

The output will be returned as a Mapwith two key-value pairs:"pos"and"peaks". If there is no peak in the given array, simply return `{"pos" => [], "peaks" => []}.

Example: pickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) should return {pos: [3, 7], peaks: [6, 3]} (or equivalent in other languages)

All input arrays will be valid integer arrays (although it could still be empty), so you won't need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don't know what is after and before and therefore, we don't know if it is a peak or not).

Also, beware of plateaus! [1, 2, 2, 2, 1] has a peak while [1, 2, 2, 2, 3] and [1, 2, 2, 2, 2] do not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1, 2, 2, 2, 1]) returns {pos: [1], peaks: [2]} (or equivalent in other languages)

Here is my answer:

public static Map> getPeaks(int[] arr) {
    HashMap> stringListHashMap = new HashMap<>();
    List positions = new ArrayList<>();
    List values = new ArrayList<>();
    values.add(arr[1]);
    positions.add(1);

    for (int i = 2; i < arr.length - 1; i++) {
        if (values.get(values.size() - 1) < arr[i]) {
            values.clear();
            positions.clear();
            values.add(arr[i]);
            positions.add(i);
        }
    }
    stringListHashMap.put("pos", positions);
    stringListHashMap.put("peaks", values);

    return stringListHashMap;
}

The above code works fine, but I don't pass the unit tests because of this ->

should support finding peaks expected:<{pos=[3, 7], peaks=[6, 3]}> but was:<{pos=[3], peaks=[6]}>

I have narrowed down the problem to this ->

Example: pickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) should return {pos: [3, 7], peaks: [6, 3]} (or equivalent in other languages)

There is clearly only one peak which is 6 and its index 3. Then what is the person asking the question trying to say? I feel like I'm missing something.

user_108326 · Answer

The question is asking for local maxima, not global maxima. If a value is larger than its neighbours (and is not the first or last value), it's a peak, even if there is another value elsewhere that is even greater. Hence, with the input [3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3], the eighth value (pos 7) is a peak, since the value 3 is greater than both the preceding neighbour (2) and following neighbour (2).

user_11820819 · Answer

From what I understand, peak is surrounded by valley. So if you go up than down you have a peak, if you again go up and again down you have another peak. If you go up and than horizontal and than down, first position is peak, you just walk on plateau. It's like when you go mountain. You can climb 2 or 3 peaks in one trip.

Here is the solution:

public static Map> getPeaks(int[] arr) {
    Map> result = new HashMap<>();

    int peak = 0;
    for (int i = 1; i < arr.length - 1; i++) {
        if (arr[i-1] < arr[i]){
            peak = i;
        }
        if(arr[i] > arr[i+1] && peak !=0) {
            result.computeIfAbsent("pos", k -> new ArrayList<>()).add(peak);
            result.computeIfAbsent("peaks", k -> new ArrayList<>()).add(arr[i]);
            peak = 0;
        }
    }
    return result;
}

I had to keep the current peak, as you can go horizontal and we need first position when you reach peak. And I reset it when I go down. So if arr[i-1] < arr[i] it means I reach a peak and if arr[i] > arr[i+1] && peak !=0 it means I went down.

Another mention, use Map as reference instead of HashMap. Same as you proceed for List.

Java arrays question with multiple answers

2 Answers