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

MediumView on LeetCode

Array Dynamic Programming

Time: O(n)

Space: O(n)

Intuition

Check if valid parentheses string can be formed. Wildcard * can be (, ), or empty. Track range [min_open, max_open].

Algorithm

1min_open=0, max_open=0. For each char: if (: both++. If ): both--. If *: min--, max++.
2If max_open < 0: return false. Clamp min_open = max(0, min_open).
3Return min_open == 0.

Common Pitfalls

•Track minimum and maximum possible open counts. Clamp min at 0 (cannot have negative opens).

2369.cs

// Approach: DP — dp[i] = true if valid partition exists for first i elements (check 2/3-element windows).
// Time: O(n) Space: O(n)

public class Solution
{
    public bool ValidPartition(int[] nums)
    {
        int n = nums.Length;
        // dp[i] := true if there's a valid partition for the first i numbers
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        dp[2] = n >= 2 && nums[0] == nums[1];

        for (int i = 3; i <= n; ++i)
        {
            dp[i] = (dp[i - 2] && nums[i - 2] == nums[i - 1]) ||
                    (dp[i - 3] &&
                     ((nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1]) ||
                      (nums[i - 3] + 1 == nums[i - 2] &&
                       nums[i - 2] + 1 == nums[i - 1])));
        }

        return dp[n];
    }
}

Was this solution helpful?