Problem statement

https://binarysearch.com/problems/Find-Local-Peaks-Sequel/

Solution

For each element find the left and the right closest element not equal to it. Then traverse array and find elements.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        def check(arr):
            d = [-1] * n
            i, j = 0, 0
            while i < n:
                while j + 1 < n and arr[j + 1] == arr[i]:
                    j += 1
                for x in range(i, j + 1):
                    d[x] = j + 1
                i = j + 1
            return d

        n, ans = len(A), []
        lft, rgh = check(A), [n-i-1 for i in check(A[::-1])[::-1]]

        for i in range(n):
            if (lft[i] == n or A[i] > A[lft[i]]) and (rgh[i] == -1 or A[i] > A[rgh[i]]):
                ans += [i]

        if not A or A == [A[0]]*n: return []
        return ans