Check if there is a valid partition for the array

Array Dynamic Programming

52.2% acceptance

Feb 25, 2026

2066

208

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: The subarray consists of exactly 2, equal elements. For example, the subarray [2,2] is good. The subarray consists of exactly 3, equal elements. For example, the subarray [4,4,4] is good. 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_partition(nums: Vec<i32>) -> bool {
    let n = nums.len();
    let mut dp = vec![false; n + 1];
    dp[0] = true;
    for i in 2..=n {
      if dp[i-2] && nums[i-1] == nums[i-2] { dp[i] = true; }
      if i >= 3 && dp[i-3] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] { dp[i] = true; }
      if i >= 3 && dp[i-3] && nums[i-1] == nums[i-2] + 1 && nums[i-2] == nums[i-3] + 1 { dp[i] = true; }
    }
    dp[n]
  }
}