Check if There is a Valid Partition For The Array LeetCode solution in Python

1
# Runtime: 920 ms (Top 32.4%) | Memory: 30.14 MB (Top 95.0%)
2

3

4
class Solution:
5
    def validPartition(self, nums: List[int]) -> bool:
6
        n = len(nums)
7

8
        dp = [False] * 3
9
        dp[0] = True  # An empty partition is always valid
10

11
        for i in range(2, n + 1):
12
            ans = False
13

14
            if nums[i - 1] == nums[i - 2]:
15
                ans = ans or dp[(i - 2) % 3]
16
            if i >= 3 and nums[i - 1] == nums[i - 2] == nums[i - 3]:
17
                ans = ans or dp[(i - 3) % 3]
18
            if i >= 3 and nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2:
19
                ans = ans or dp[(i - 3) % 3]
20

21
            dp[i % 3] = ans
22

23
        return dp[n % 3]