Skip to content

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

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  bool validPartition(vector<int>& nums) {
    const int n = nums.size();
    // dp[i] := true if there's a valid partition for the first i numbers
    vector<bool> dp(n + 1);
    dp[0] = true;
    dp[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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean validPartition(int[] nums) {
    final int n = nums.length;
    // dp[i] := true if there's a valid partition for the first i numbers
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    dp[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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def validPartition(self, nums: list[int]) -> bool:
    n = len(nums)
    # dp[i] := True if there's a valid partition for the first i numbers
    dp = [False] * (n + 1)
    dp[0] = True
    dp[2] = nums[0] == nums[1]

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

    return dp[n]