Problem statement

https://binarysearch.com/problems/Valid-State-of-List/

Solution

We can use dp with states dp(i) where it is answer for array A[:i]. Then we need to check no more than 3 options.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        @lru_cache(None)
        def dp(i):
            if i == -1: return True
            if i > 1 and A[i] == A[i-1] + 1 == A[i-2] + 2 and dp(i-3): return True
            if i > 1 and A[i] == A[i-1] == A[i-2] and dp(i-3): return True
            if i > 0 and A[i] == A[i-1] and dp(i-2): return True
            return False
        return dp(len(A) - 1)