[Python solution] 2369. Check the effective partitioning method of the array

Question overview

Leetcode question 2369 asks us to check an array of integersnumsWhether it can be divided into one or more consecutive subarrays that meet certain conditions. Valid partition conditions include:

• A subarray consists of two equal elements, such as [2, 2]。
• A subarray consists of three equal elements, such as [3, 3, 3]。
• The subarray consists of three consecutively increasing elements, and the difference between adjacent elements is 1, such as [4, 5, 6]。

Returns if there is at least one valid partition of the arraytrue; Otherwise returnfalse。

Example analysis

• Example 1:nums = [4, 4, 4, 5, 6]can be divided into [4, 4] and [4, 5, 6], so returntrue。
• Example 2:nums = [1, 1, 1, 2]None of the partitioning conditions are met, so returnfalse。

Problem-solving ideas

adoptdynamic programmingstrategy, we define a Boolean arraydp, among whichdp[i]Represents the front of the arrayiWhether the elements can be divided effectively. Iterate over the array, for each positioni, try the following three division methods:

1. The subarray consists of the last two elements that are equal.
2. The subarray consists of the last three equal elements.
3. The subarray consists of the last three consecutively increasing elements.

Algorithm process

1. Initialize dp[0] to true, indicating that the empty array can be effectively divided.
2. For each i (starting at 2), check whether the array can be partitioned into i in one of the three ways above.
3. Ultimately, dp[n] (where n is the length of the array) gives the answer to whether the entire array can be efficiently divided.
4. If either way is possible, thendp[i]set totrue。

Specifically
Initialization:

1. Initialize dp[0] to true, indicating that the empty array can be effectively divided.
2. State transition: For each element nums[i] in the array (starting from the second element), consider the following situations:
   • If nums[i] is equal to nums[i-1], check whether dp[i-2] is true. If so, it means that [nums[i-1], nums[i]] can form a valid partition, and set dp[i] to true.
   • If nums[i], nums[i-1] and nums[i-2] are equal, dp[i-3] is also checked. If dp[i-3] is true, it means [nums[i-2], nums[i-1], nums[i]] can form an effective division, set dp[i] to true.
   • If nums[i], nums[i-1] and nums[i-2] form a continuous increasing sequence (i.e. nums[i]-1 == nums[i-1] and nums[i-1]-1 == nums[i-2]), check dp[i-3]. If true, set dp[i] to true.
3. Result judgment:
   • Finally, the value of dp[n] is checked (where n is the length of the array nums). If dp[n] is true, it means that the entire array can be effectively divided; otherwise, it cannot.

Dynamic programming implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * (n + 1)
        dp[0] = True  # 空数组视为有效划分

        for i in range(2, n + 1):
            if nums[i - 1] == nums[i - 2]:
                dp[i] = dp[i] or dp[i - 2]
            if i > 2 and nums[i - 1] == nums[i - 2] == nums[i - 3]:
                dp[i] = dp[i] or dp[i - 3]
            if i > 2 and nums[i - 1] - 1 == nums[i - 2] and nums[i - 2] - 1 == nums[i - 3]:
                dp[i] = dp[i] or dp[i - 3]

        return dp[n]

Algorithm complexity analysis

• time complexity:O(N), where N is an arraynumslength, the entire array needs to be traversed to fill the dynamic programming array.
• space complexity:O(N), used to store dynamic programming arraysdp, record the division of each position.

Through dynamic programming, we provide an efficient and intuitive solution that ensures optimal performance of the algorithm for similar array partitioning problems.