Question

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

中文文档

Description

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

Solutions

Solution 1: Memoization Search

We design a function $dfs(i)$, which represents whether there is a valid partition starting from index $i$. So the answer is $dfs(0)$.

The execution process of the function $dfs(i)$ is as follows:

• If $i \ge n$, return $true$.
• If the elements at index $i$ and $i+1$ are equal, we can choose to make $i$ and $i+1$ a subarray, and recursively call $dfs(i+2)$.
• If the elements at index $i$, $i+1$ and $i+2$ are equal, we can choose to make $i$, $i+1$ and $i+2$ a subarray, and recursively call $dfs(i+3)$.
• If the elements at index $i$, $i+1$ and $i+2$ increase by $1$ in turn, we can choose to make $i$, $i+1$ and $i+2$ a subarray, and recursively call $dfs(i+3)$.
• If none of the above conditions are met, return $false$, otherwise return $true$.

That is:

$$ dfs(i) = \text{OR} \begin{cases} true,&i \ge n\ dfs(i+2),&i+1 < n\ \text{and}\ \textit{nums}[i] = \textit{nums}[i+1]\ dfs(i+3),&i+2 < n\ \text{and}\ \textit{nums}[i] = \textit{nums}[i+1] = \textit{nums}[i+2]\ dfs(i+3),&i+2 < n\ \text{and}\ \textit{nums}[i+1] - \textit{nums}[i] = 1\ \text{and}\ \textit{nums}[i+2] - \textit{nums}[i+1] = 1 \end{cases} $$

To avoid repeated calculations, we use the method of memoization search.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array.

class Solution:
  def validPartition(self, nums: List[int]) -> bool:
    @cache
    def dfs(i: int) -> bool:
      if i >= n:
        return True
      a = i + 1 < n and nums[i] == nums[i + 1]
      b = i + 2 < n and nums[i] == nums[i + 1] == nums[i + 2]
      c = (
        i + 2 < n
        and nums[i + 1] - nums[i] == 1
        and nums[i + 2] - nums[i + 1] == 1
      )
      return (a and dfs(i + 2)) or ((b or c) and dfs(i + 3))

    n = len(nums)
    return dfs(0)

class Solution {
  private int n;
  private int[] nums;
  private Boolean[] f;

  public boolean validPartition(int[] nums) {
    n = nums.length;
    this.nums = nums;
    f = new Boolean[n];
    return dfs(0);
  }

  private boolean dfs(int i) {
    if (i >= n) {
      return true;
    }
    if (f[i] != null) {
      return f[i];
    }
    boolean a = i + 1 < n && nums[i] == nums[i + 1];
    boolean b = i + 2 < n && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2];
    boolean c = i + 2 < n && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1;
    return f[i] = ((a && dfs(i + 2)) || ((b || c) && dfs(i + 3)));
  }
}

class Solution {
public:
  bool validPartition(vector<int>& nums) {
    n = nums.size();
    this->nums = nums;
    f.assign(n, -1);
    return dfs(0);
  }

private:
  int n;
  vector<int> f;
  vector<int> nums;

  bool dfs(int i) {
    if (i >= n) {
      return true;
    }
    if (f[i] != -1) {
      return f[i] == 1;
    }
    bool a = i + 1 < n && nums[i] == nums[i + 1];
    bool b = i + 2 < n && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2];
    bool c = i + 2 < n && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1;
    f[i] = ((a && dfs(i + 2)) || ((b || c) && dfs(i + 3))) ? 1 : 0;
    return f[i] == 1;
  }
};

func validPartition(nums []int) bool {
  n := len(nums)
  f := make([]int, n)
  for i := range f {
    f[i] = -1
  }
  var dfs func(int) bool
  dfs = func(i int) bool {
    if i == n {
      return true
    }
    if f[i] != -1 {
      return f[i] == 1
    }
    a := i+1 < n && nums[i] == nums[i+1]
    b := i+2 < n && nums[i] == nums[i+1] && nums[i+1] == nums[i+2]
    c := i+2 < n && nums[i+1]-nums[i] == 1 && nums[i+2]-nums[i+1] == 1
    f[i] = 0
    if a && dfs(i+2) || b && dfs(i+3) || c && dfs(i+3) {
      f[i] = 1
    }
    return f[i] == 1
  }
  return dfs(0)
}

function validPartition(nums: number[]): boolean {
  const n = nums.length;
  const f: number[] = Array(n).fill(-1);
  const dfs = (i: number): boolean => {
    if (i >= n) {
      return true;
    }
    if (f[i] !== -1) {
      return f[i] === 1;
    }
    const a = i + 1 < n && nums[i] == nums[i + 1];
    const b = i + 2 < n && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2];
    const c = i + 2 < n && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1;
    f[i] = (a && dfs(i + 2)) || ((b || c) && dfs(i + 3)) ? 1 : 0;
    return f[i] == 1;
  };
  return dfs(0);
}

Solution 2: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

Let $f[i]$ represent whether there is a valid partition for the first $i$ elements of the array. Initially, $f[0] = true$, and the answer is $f[n]$.

The state transition equation is as follows:

$$ f[i] = \text{OR} \begin{cases} true,&i = 0\ f[i-2],&i-2 \ge 0\ \text{and}\ \textit{nums}[i-1] = \textit{nums}[i-2]\ f[i-3],&i-3 \ge 0\ \text{and}\ \textit{nums}[i-1] = \textit{nums}[i-2] = \textit{nums}[i-3]\ f[i-3],&i-3 \ge 0\ \text{and}\ \textit{nums}[i-1] - \textit{nums}[i-2] = 1\ \text{and}\ \textit{nums}[i-2] - \textit{nums}[i-3] = 1 \end{cases} $$

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array.

class Solution:
  def validPartition(self, nums: List[int]) -> bool:
    n = len(nums)
    f = [True] + [False] * n
    for i, x in enumerate(nums, 1):
      a = i - 2 >= 0 and nums[i - 2] == x
      b = i - 3 >= 0 and nums[i - 3] == nums[i - 2] == x
      c = i - 3 >= 0 and x - nums[i - 2] == 1 and nums[i - 2] - nums[i - 3] == 1
      f[i] = (a and f[i - 2]) or ((b or c) and f[i - 3])
    return f[n]

class Solution {
  public boolean validPartition(int[] nums) {
    int n = nums.length;
    boolean[] f = new boolean[n + 1];
    f[0] = true;
    for (int i = 1; i <= n; ++i) {
      boolean a = i - 2 >= 0 && nums[i - 1] == nums[i - 2];
      boolean b = i - 3 >= 0 && nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3];
      boolean c
        = i - 3 >= 0 && nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1;
      f[i] = (a && f[i - 2]) || ((b || c) && f[i - 3]);
    }
    return f[n];
  }
}

class Solution {
public:
  bool validPartition(vector<int>& nums) {
    int n = nums.size();
    vector<bool> f(n + 1);
    f[0] = true;
    for (int i = 1; i <= n; ++i) {
      bool a = i - 2 >= 0 && nums[i - 1] == nums[i - 2];
      bool b = i - 3 >= 0 && nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3];
      bool c = i - 3 >= 0 && nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1;
      f[i] = (a && f[i - 2]) || ((b || c) && f[i - 3]);
    }
    return f[n];
  }
};

func validPartition(nums []int) bool {
  n := len(nums)
  f := make([]bool, n+1)
  f[0] = true
  for i := 1; i <= n; i++ {
    x := nums[i-1]
    a := i-2 >= 0 && nums[i-2] == x
    b := i-3 >= 0 && nums[i-3] == nums[i-2] && nums[i-2] == x
    c := i-3 >= 0 && x-nums[i-2] == 1 && nums[i-2]-nums[i-3] == 1
    f[i] = (a && f[i-2]) || ((b || c) && f[i-3])
  }
  return f[n]
}

function validPartition(nums: number[]): boolean {
  const n = nums.length;
  const f: boolean[] = Array(n + 1).fill(false);
  f[0] = true;
  for (let i = 1; i <= n; ++i) {
    const a = i - 2 >= 0 && nums[i - 1] === nums[i - 2];
    const b = i - 3 >= 0 && nums[i - 1] === nums[i - 2] && nums[i - 2] === nums[i - 3];
    const c = i - 3 >= 0 && nums[i - 1] - nums[i - 2] === 1 && nums[i - 2] - nums[i - 3] === 1;
    f[i] = (a && f[i - 2]) || ((b || c) && f[i - 3]);
  }
  return f[n];
}