Classic Dynamic Programming IV

Another medium problem requiring a DP solution (more and more I'm seeing Medium-LC problems needing an DP solution). It follows a similar pattern of the previous ones, except that it doesn't look for min/max, but you can see the structure being the same: suppose you know the solution on whether you can do a valid partition for positions 0, 1, 2, ..., N-1. In order to know whether there is a valid partition for N, just run the three checks using the info stored for the previous partitions. Code is down below, cheers, ACC.

Check if There is a Valid Partition For The Array - LeetCode

2369. Check if There is a Valid Partition For The Array

Medium

You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:

1. The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
2. The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
3. The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.

Return true if the array has at least one valid partition. Otherwise, return false.

 

Example 1:

Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.

Example 2:

Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.

 

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

public bool ValidPartition(int[] nums)
{
    bool[] dp = new bool[nums.Length];

    dp[0] = false;
    for (int i = 0; i < nums.Length; i++)
    {
        dp[i] = false;

        //First case:
        if (i - 1 >= 0 && nums[i - 1] == nums[i])
        {
            if (i - 2 >= 0) dp[i] = dp[i - 2];
            else dp[i] = true;
        }

        //Second case:
        if (!dp[i] &&
            i - 2 >= 0 &&
            nums[i - 2] == nums[i - 1] &&
            i - 1 >= 0 &&
            nums[i - 1] == nums[i])
        {
            if (i - 3 >= 0) dp[i] = dp[i - 3];
            else dp[i] = true;
        }

        //Third case:
        if (!dp[i] &&
            i - 2 >= 0 &&
            nums[i - 2] == nums[i - 1] - 1 &&
            i - 1 >= 0 &&
            nums[i - 1] == nums[i] - 1)
        {
            if (i - 3 >= 0) dp[i] = dp[i - 3];
            else dp[i] = true;
        }
    }

    return dp[dp.Length - 1];
}