Problem Statement in English

You’re given an array arr. Your task is to return the length of the longest subset of arr that has toggling comparison operators between them.

For example, given arr = [2,3,1], your answer would be $3$, since 2 < 3 > 1.

Approach

We can do this in one iteration over the array. We just need to keep track of what the result of the last comparison oepration was, and check if the current one is the same.

Realize that everytime we get the same number back to back, the current longest becomes $1$, and when we get the sam operator back to back, the current longest becomes $2$. Once you’ve wrapped your head around that, you’re good to go!

Solution in Python


class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return len(arr)

        best = 1
        c = best
        last = None

        for i in range(1, len(arr)):
            # calculate state
            if arr[i] == arr[i - 1]:
                state = None
            elif arr[i] < arr[i - 1]:
                state = -1
            else:
                state = 1

            # update count
            if state == None:
                c = 1
            elif state != last:
                c += 1
            else:
                c = 2

            # update last state
            last = state

            # update max
            best = max(best, c)

        return best

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a couple integer variables.

Mistakes I Made

I didn’t realize that when we have $2$ of the same operations back to back, the current longest becomes $2$, I initially set it to $1$.

And we are done.