Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

LeetCode 2369 - Check if There is a Valid Partition

Problem Understanding

The problem gives us an integer array nums, and we must determine whether it is possible to split the array into contiguous groups such that every group satisfies one of three valid patterns.

A valid group can be:

Exactly two equal numbers, such as [5,5]
Exactly three equal numbers, such as [7,7,7]
Exactly three consecutive increasing numbers, such as [3,4,5]

The partition must cover the entire array with no gaps and no overlaps. Every element must belong to exactly one valid subarray.

The important detail is that the subarrays must be contiguous. We cannot rearrange elements or skip elements. We can only split the original array into consecutive chunks.

The output should be:

true if at least one valid partition exists
false otherwise

The constraints are large:

2 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

Because the array length can reach one hundred thousand, exponential or quadratic solutions are not practical. We need an algorithm close to linear time.

Several edge cases are important:

Arrays of length 2 only work if both elements are equal.
Arrays of length 3 may satisfy either the "all equal" condition or the "consecutive increasing" condition.
A locally valid group may lead to a globally invalid partition. For example, greedily taking the first valid segment does not always work.
Some arrays contain multiple valid partition paths, so the algorithm must explore possibilities efficiently.
Arrays with leftover elements that cannot form a valid group must correctly return false.

Approaches

Brute Force Approach

A straightforward approach is to try every possible partition recursively.

Starting from index 0, we can attempt:

Taking the next two elements if they are equal
Taking the next three elements if they are equal
Taking the next three elements if they form consecutive increasing values

For every valid choice, we recursively continue from the next index.

This brute-force solution is correct because it explores every possible valid partition. If any recursive path successfully reaches the end of the array, then a valid partition exists.

However, this approach is extremely slow because many subproblems repeat. For example, multiple recursive paths may repeatedly ask whether the suffix starting at index i can be partitioned. In the worst case, the recursion tree grows exponentially.

With n = 10^5, exponential complexity is impossible to run within time limits.

Optimal Dynamic Programming Approach

The key observation is that the validity of a partition only depends on earlier positions.

Suppose we define:

dp[i] = true if the first i elements can form a valid partition

Then, to compute dp[i], we only need to check whether the last valid group ending at position i - 1 satisfies one of the allowed patterns.

There are only three possibilities:

The last two elements are equal, and dp[i - 2] is true
The last three elements are equal, and dp[i - 3] is true
The last three elements are consecutive increasing, and dp[i - 3] is true

Since each position only checks a constant number of previous states, the algorithm runs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all partition combinations
Optimal Dynamic Programming	O(n)	O(n)	Uses previous computed states to avoid repeated work

Algorithm Walkthrough

Create a boolean DP array dp of size n + 1.

The meaning of dp[i] is whether the first i elements of nums can be partitioned validly. 2. Initialize dp[0] = true.

This represents the empty prefix. It is important because valid groups can build on top of this base case. 3. Iterate through the array from left to right.

For each position i, we determine whether a valid partition can end at index i - 1. 4. Check the two-equal-elements condition.

If:

i >= 2
nums[i - 1] == nums[i - 2]
dp[i - 2] is true

then we can form a valid partition ending at i - 1, so set dp[i] = true. 5. Check the three-equal-elements condition.

If:

i >= 3
nums[i - 1] == nums[i - 2] == nums[i - 3]
dp[i - 3] is true

then set dp[i] = true. 6. Check the consecutive-increasing condition.

If:

i >= 3
nums[i - 3] + 1 == nums[i - 2]
nums[i - 2] + 1 == nums[i - 1]
dp[i - 3] is true

then set dp[i] = true. 7. Continue until all positions are processed. 8. Return dp[n].

This tells us whether the entire array can be partitioned validly.

Why it works

The algorithm works because every valid partition must end with one of the three allowed group types. The DP state dp[i] stores whether the prefix ending before index i is solvable. By checking all valid final group configurations, we guarantee that every possible valid partition is considered exactly once. Since each state depends only on smaller already-computed states, the solution is both correct and efficient.

Python Solution

from typing import List

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)

        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(2, n + 1):
            # Case 1: two equal elements
            if nums[i - 1] == nums[i - 2] and dp[i - 2]:
                dp[i] = True

            # Cases involving three elements
            if i >= 3:
                # Case 2: three equal elements
                if (
                    nums[i - 1] == nums[i - 2] ==
                    nums[i - 3] and dp[i - 3]
                ):
                    dp[i] = True

                # Case 3: three consecutive increasing elements
                if (
                    nums[i - 3] + 1 == nums[i - 2] and
                    nums[i - 2] + 1 == nums[i - 1] and
                    dp[i - 3]
                ):
                    dp[i] = True

        return dp[n]

The implementation directly follows the DP formulation.

The variable n stores the array length. The dp array has size n + 1 because dp[i] represents the validity of the first i elements.

The base case dp[0] = True is essential because it allows the first valid group to form from the beginning of the array.

The loop starts from i = 2 because the smallest valid group size is two.

Inside the loop, the code checks the three allowed partition types:

Two equal elements
Three equal elements
Three consecutive increasing elements

Whenever one of these conditions is satisfied and the earlier prefix is already valid, the current prefix also becomes valid.

Finally, the algorithm returns dp[n], which indicates whether the entire array can be partitioned.

Go Solution

func validPartition(nums []int) bool {
	n := len(nums)

	dp := make([]bool, n+1)
	dp[0] = true

	for i := 2; i <= n; i++ {
		// Case 1: two equal elements
		if nums[i-1] == nums[i-2] && dp[i-2] {
			dp[i] = true
		}

		if i >= 3 {
			// Case 2: three equal elements
			if nums[i-1] == nums[i-2] &&
				nums[i-2] == nums[i-3] &&
				dp[i-3] {
				dp[i] = true
			}

			// Case 3: three consecutive increasing elements
			if nums[i-3]+1 == nums[i-2] &&
				nums[i-2]+1 == nums[i-1] &&
				dp[i-3] {
				dp[i] = true
			}
		}
	}

	return dp[n]
}

The Go implementation mirrors the Python solution closely.

The DP array is created using make([]bool, n+1). Go initializes boolean slices to false automatically, so only dp[0] must be explicitly set to true.

Go slices are zero indexed exactly like Python lists, so the same indexing logic applies.

There are no integer overflow concerns because the values only differ by 1, and the constraints remain well within Go's integer range.

Worked Examples

Example 1

Input: nums = [4,4,4,5,6]

We build the DP table step by step.

Initial state:

i	dp
0	true

DP array:

[true, false, false, false, false, false]

Iteration: i = 2

Check last two elements:

nums[1] == nums[0]
4 == 4
dp[0] == true

So:

dp[2] = true

State:

[true, false, true, false, false, false]

Iteration: i = 3

Check three equal:

4 == 4 == 4
dp[0] == true

So:

dp[3] = true

State:

[true, false, true, true, false, false]

Iteration: i = 4

Check valid endings:

[4,5] is not valid
[4,4,5] is not valid
[4,5,6] cannot end here yet

So:

dp[4] = false

State:

[true, false, true, true, false, false]

Iteration: i = 5

Check consecutive increasing:

4,5,6 are consecutive
dp[2] == true

Therefore:

dp[5] = true

Final state:

[true, false, true, true, false, true]

Return:

true

The valid partition is:

[4,4] + [4,5,6]

Example 2

Input: nums = [1,1,1,2]

Initial state:

[true, false, false, false, false]

Iteration: i = 2

Two equal elements:

1 == 1
dp[0] == true

So:

dp[2] = true

State:

[true, false, true, false, false]

Iteration: i = 3

Three equal elements:

1 == 1 == 1
dp[0] == true

So:

dp[3] = true

State:

[true, false, true, true, false]

Iteration: i = 4

Check endings:

[1,2] is invalid
[1,1,2] is invalid
[1,1,2] is not consecutive increasing

So:

dp[4] = false

Final state:

[true, false, true, true, false]

Return:

false

No valid full partition exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index checks only a constant number of conditions
Space	O(n)	The DP array stores one boolean value per prefix

The algorithm processes the array once from left to right. At every position, only a few comparisons are performed, so the total running time grows linearly with the input size.

The space usage is linear because the DP table stores n + 1 boolean states.

Test Cases

sol = Solution()

assert sol.validPartition([4,4,4,5,6]) is True
# Example case with mixed valid groups

assert sol.validPartition([1,1,1,2]) is False
# Example case with leftover invalid element

assert sol.validPartition([1,1]) is True
# Smallest valid two-element partition

assert sol.validPartition([1,2]) is False
# Two unequal elements cannot form a valid group

assert sol.validPartition([3,3,3]) is True
# Three equal elements

assert sol.validPartition([3,4,5]) is True
# Three consecutive increasing elements

assert sol.validPartition([1,1,2,2]) is True
# Multiple two-element groups

assert sol.validPartition([1,1,1,2,2,2]) is True
# Multiple three-equal groups

assert sol.validPartition([1,2,3,4,5,6]) is True
# Multiple consecutive increasing groups

assert sol.validPartition([1,1,1,1]) is True
# Can split into two equal pairs

assert sol.validPartition([1,1,1,1,1]) is False
# One element left over after valid groups

assert sol.validPartition([1,2,3,5,6,7]) is True
# Two consecutive increasing groups

assert sol.validPartition([1,2,4]) is False
# Three elements but not consecutive

assert sol.validPartition([5,5,5,5,5,5]) is True
# Repeated equal triples

assert sol.validPartition([1,1,2,3,4]) is True
# Pair followed by consecutive triple

assert sol.validPartition([7,7,8,8,9]) is False
# Final leftover element prevents partition

Test Summary

Test	Why
`[4,4,4,5,6]`	Standard mixed valid partition
`[1,1,1,2]`	No valid complete partition
`[1,1]`	Minimum valid size
`[1,2]`	Invalid two-element case
`[3,3,3]`	Three equal elements
`[3,4,5]`	Consecutive increasing triple
`[1,1,2,2]`	Multiple valid pairs
`[1,1,1,2,2,2]`	Multiple equal triples
`[1,2,3,4,5,6]`	Multiple consecutive triples
`[1,1,1,1]`	Two pair partitions
`[1,1,1,1,1]`	Leftover element edge case
`[1,2,3,5,6,7]`	Separate consecutive groups
`[1,2,4]`	Invalid non-consecutive triple
`[5,5,5,5,5,5]`	Repeated triple groups
`[1,1,2,3,4]`	Mixed pair and triple
`[7,7,8,8,9]`	Incomplete final segment

Edge Cases

One important edge case is the minimum input size of two elements. Since the only valid partition for length two is a pair of equal numbers, arrays like [5,5] must return true, while [5,6] must return false. The implementation handles this naturally because the loop begins at i = 2 and checks the two-equal-elements condition immediately.

Another important edge case is arrays with valid prefixes but invalid leftovers. For example, [1,1,1,1,1] initially appears promising because several valid groups exist. However, every possible partition leaves one unmatched element. The DP formulation correctly handles this because a state only becomes true if the entire earlier prefix was valid.

A third important edge case involves overlapping partition possibilities. Consider [4,4,4,4]. The first three elements form a valid triple, but using that partition leaves one invalid leftover element. The correct solution is splitting into two pairs: [4,4] and [4,4]. A greedy algorithm might fail here, but dynamic programming succeeds because it evaluates all valid ways to reach each prefix.

Another subtle edge case is consecutive sequences that almost work, such as [1,2,4]. Although the numbers are increasing, they are not consecutive because the difference between 2 and 4 is not 1. The implementation explicitly checks both adjacent differences, ensuring such cases are rejected correctly.

LeetCode 2369 - Check if There is a Valid Partition For The Array

Solution

LeetCode 2369 - Check if There is a Valid Partition

Problem Understanding

Approaches

Brute Force Approach

Optimal Dynamic Programming Approach

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Iteration: i = 2

Iteration: i = 3

Iteration: i = 4

Iteration: i = 5

Example 2

Iteration: i = 2

Iteration: i = 3

Iteration: i = 4

Complexity Analysis

Test Cases

Test Summary

Edge Cases