Skip to content

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

SourceWeekly Contest 305 Q3DifficultyMediumRating1779

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

Thinking

A partition uses two equals, three equals, or three consecutive increases. \(n \le 10^5\) makes naive recursion overlap. Validity from index \(i\) depends only on the suffix.

Memoize \(dfs(i)\): try a legal block of length \(2\) or \(3\) and jump to its end. Past \(n\) is success.

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) = \textit{OR} \begin{cases} true,&i \ge n\\ dfs(i+2),&i+1 < n\ \textit{and}\ \textit{nums}[i] = \textit{nums}[i+1]\\ dfs(i+3),&i+2 < n\ \textit{and}\ \textit{nums}[i] = \textit{nums}[i+1] = \textit{nums}[i+2]\\ dfs(i+3),&i+2 < n\ \textit{and}\ \textit{nums}[i+1] - \textit{nums}[i] = 1\ \textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

Thinking

Solution 1 fills a suffix table from the end. The same three blocks can be written on prefixes: \(f[i]\) means the first \(i\) elements form a valid partition, taken from \(f[i-2]\) or \(f[i-3]\).

Fill left to right. The answer is \(f[n]\). Time stays \(O(n)\).

Solution 1 already decides each suffix from the end. Here we decide each prefix instead, using the same three blocks.

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] = \textit{OR} \begin{cases} true,&i = 0\\ f[i-2],&i-2 \ge 0\ \textit{and}\ \textit{nums}[i-1] = \textit{nums}[i-2]\\ f[i-3],&i-3 \ge 0\ \textit{and}\ \textit{nums}[i-1] = \textit{nums}[i-2] = \textit{nums}[i-3]\\ f[i-3],&i-3 \ge 0\ \textit{and}\ \textit{nums}[i-1] - \textit{nums}[i-2] = 1\ \textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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];
}

Solution 3: Dynamic Programming

Thinking

A partition is two equals, three equals, or three consecutive increases. \(n \le 10^5\), so trying blocks overlaps, and the pair is always tried first.

On an array of equal values that attempt is a chain of length \(n/2\), which overflows the stack.

Later indexes are known if we walk backward. Let \(f[i]\) mean the suffix from \(i\) has a valid partition, with \(f[n]\) true, and fill \(i\) from \(n-1\) down to \(0\). A legal block still jumps to \(i+2\) or \(i+3\).

Let \(f[i]\) mean there is a valid partition of the suffix starting at index \(i\). The answer is \(f[0]\), and \(f[n] = true\).

Fill \(i\) from \(n - 1\) down to \(0\). Two equal neighbors can continue from \(f[i + 2]\). Three equal values, or three values that increase by \(1\), can continue from \(f[i + 3]\). Take the or of those cases; if none applies, \(f[i]\) is false:

\[ f[i] = \textit{OR} \begin{cases} f[i+2],&i+1 < n\ \textit{and}\ \textit{nums}[i] = \textit{nums}[i+1]\\ f[i+3],&i+2 < n\ \textit{and}\ \textit{nums}[i] = \textit{nums}[i+1] = \textit{nums}[i+2]\\ f[i+3],&i+2 < n\ \textit{and}\ \textit{nums}[i+1] - \textit{nums}[i] = 1\ \textit{and}\ \textit{nums}[i+2] - \textit{nums}[i+1] = 1 \end{cases} \]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        f = [False] * n + [True]
        for i in range(n - 1, -1, -1):
            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
            )
            f[i] = (a and f[i + 2]) or ((b or c) and f[i + 3])
        return f[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n + 1];
        f[n] = true;
        for (int i = n - 1; i >= 0; --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;
            f[i] = (a && f[i + 2]) || ((b || c) && f[i + 3]);
        }
        return f[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        f[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            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 && f[i + 2]) || ((b || c) && f[i + 3]);
        }
        return f[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func validPartition(nums []int) bool {
    n := len(nums)
    f := make([]bool, n+1)
    f[n] = true
    for i := n - 1; i >= 0; i-- {
        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] = (a && f[i+2]) || ((b || c) && f[i+3])
    }
    return f[0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function validPartition(nums: number[]): boolean {
    const n = nums.length;
    const f: boolean[] = Array(n + 1).fill(false);
    f[n] = true;
    for (let i = n - 1; i >= 0; --i) {
        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 && f[i + 2]) || ((b || c) && f[i + 3]);
    }
    return f[0];
}

Comments