Problem with finding array's local maximas and their positions Python

Question

So basically I'm trying to complete this assignment: https://www.codewars.com/kata/5279f6fe5ab7f447890006a7

The question: Why does my function count position 11 as a local maxima of this particular array? Here is my code:

def main():
    arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
    maxes = []
    positions = []
    dic = {"pos":positions, "peaks":maxes}
    for i in range(1,len(arr)-1):
        try:
            if arr[i] > arr[i+1] and arr[i] > arr[i-1]:
                maxes.append(arr[i])
                positions.append(i)
            elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:
                for a in range(i+1,len(arr)):
                    if arr[a] > arr[a+1]:
                        maxes.append(arr[i])
                        positions.append(i)
                        break
        except IndexError:
            pass
    print(dic)
main()

My output:

{'pos': [2, 7, 11, 14, 20], 'peaks': [5, 6, 3, 5, 5]}

Correct output:

{'pos': [2, 7, 14, 20], 'peaks': [5, 6, 5, 5]}

Answer 1

When you find a following value that is equal and continue to search for a lesser value you should also break the loop if you find a greater value. It's not a peak if the group of equals are followed by a greater value.

A small addition is enough to make your code work.

def main():
    arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
    maxes = []
    positions = []
    dic = {"pos":positions, "peaks":maxes}
    for i in range(1,len(arr)-1):
        try:
            if arr[i] > arr[i+1] and arr[i] > arr[i-1]:
                maxes.append(arr[i])
                positions.append(i)
            elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:
                for a in range(i+1,len(arr)):
                    if arr[a] > arr[a+1]:
                        maxes.append(arr[i])
                        positions.append(i)
                        break
                    # also break if a greater value is found
                    elif arr[a] < arr[a+1]:
                        break
        except IndexError:
            pass
    print(dic)
main()

A simpler approach may be to iterate just once and take note of the position every time you find an increase. Then save that position and its value when you find a decrease afterwards.

def pick_peaks(arr):
    dic = {"pos":[], "peaks":[]}
    possible_peak = None
    for i in range(1,len(arr)):
        if arr[i] > arr[i-1]:
            # Value is going up. Remember position
            possible_peak = i
        elif arr[i] < arr[i-1] and possible_peak != None:
            # It was indeed a peak. Save it.
            dic["pos"].append(possible_peak)
            dic["peaks"].append(arr[possible_peak])
            # reset memory until new increase is found
            possible_peak = None
    return dic

input_arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
print(pick_peaks(input_arr))

Answer 2

When you see a situation like "2,3,3, 4,5,3...?" you save the position and run further try to find out: 1) at the end the value is less (then this is the peak and the saved value came in handy), 2) the value is larger (not a peak, plateau, the saved value was not useful).

In you particular situation in second condition: elif arr[i] > arr[i-1] and arr[i] == arr[i+1]: you begin to iterate from second 3 and stop only when arr[a] > arr[a+1]. In this moment you append you old i value (which indicates first 3):

maxes.append(arr[i]); positions.append(i)

that is, you do not take into account that the value further may be greater and you need to interrupt.

A working example of the function can be seen below:

def main():
    arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
    dic = {'pos' : [], 'peaks' : []}

    i, n = 1, len(arr)

    while i < n - 1:
        if arr[i-1] < arr[i] > arr[i+1]:
            dic['peaks'].append(arr[i])
            dic['pos'].append(i)
            i += 1
        else:
            if arr[i-1] < arr[i] and arr[i] == arr[i+1]:
                mem = i
                while i < n -1 and arr[i] == arr[i+1]:
                    i += 1
            
                if i == n - 1:
                    return dic
            
                if arr[i] > arr[i+1]:
                    dic['peaks'].append(arr[mem])
                    dic['pos'].append(mem)
                else:
                    i += 1  
            else:
                i += 1

    return dic

print(main())