Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Check if There is a Valid Partition For The Array solution and explanation

MediumArrayDynamic Programming7 min read52.5% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Check if There is a Valid Partition For The Array
21:27
Check if There is a Valid Partition For The Array - Leetcode 2369 - PythonNeetCodeIO · 21:27 · 11K viewsWatch on YouTube
9 more videos on this problem
  1. Check if There is a Valid Partition For The Array - Leetcode 2369 - PythonNeetCodeIO · 21:27 · 11K views
  2. Check if There is a Valid Partition For The Array | Recursion | Memoization | GOOGLE | Leetcode-2369codestorywithMIK · 25:39 · 5K views
  3. LEETCODE 2369. Check if There is a Valid Partition For The Array | WEEKLY CONTEST 305. MEDIUMCode with Alisha · 12:15 · 3K views
  4. 2369 Check if There is a Valid Partition For The Array | Leetcode Weekly Contest 305 | LeetCode 2369Bro Coders · 11:07 · 3K views
  5. Decode Dynamic Programming LeetCode 2369. Check if There is a Valid Partition For The Array PythonvanAmsen · 11:54 · 1K views
  6. Leetcode 2369 Check if There is a Valid Partition For The ArrayJeevan Kumar - Cracckify · 9:54 · 870 views
  7. 2369. Check if There is a Valid Partition For The Array (Leetcode Medium)Programming Live with Larry · 5:45 · 661 views
  8. Check if There is a Valid Partition For The Array | Dynamic Programming | LeetCode Solution 2369Gantavya Malviya · 12:47 · 432 views
  9. Leetcode 2369. Check if There is a Valid Partition For The ArrayElite Code · 28:59 · 263 views
  10. Dynamic Programming in Rust! LeetCode 2369. Check if There is a Valid Partition For The ArrayvanAmsen · 9:04 · 262 views

The problem

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

Approach overview

Problem Overview: You receive an integer array and must determine whether it can be partitioned into contiguous groups that follow strict rules: two equal numbers [x, x], three equal numbers [x, x, x], or three consecutive increasing numbers [x, x+1, x+2]. The entire array must be covered without overlap.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

The most reliable strategy uses dynamic programming. Define dp[i] as whether the first i elements can form a valid partition. Iterate through the array and check whether the current position can extend a valid partition using one of the allowed patterns. For each index, verify the last two elements for the [x, x] pattern or the last three elements for [x, x, x] and [x, x+1, x+2]. If a rule matches and the previous state dp[i-k] was valid, mark dp[i] as true. This builds the solution incrementally with a single pass through the array. Time complexity is O(n) because each index performs constant checks, while space complexity is O(n) for the DP table.

Approach 2: Greedy State Compression (O(n) time, O(1) space)

The DP solution only depends on the previous two or three states, so storing the entire table is unnecessary. You can compress the state and track only a few booleans representing dp[i-1], dp[i-2], and dp[i-3]. During iteration, compute the current validity using the same partition rules and shift the state variables forward. This behaves like a greedy rolling decision process while still respecting the dynamic programming transitions. The algorithm still scans the array once, so time complexity remains O(n), but the space complexity drops to O(1). This version is ideal when optimizing memory or writing concise interview code.

Recommended for interviews: Interviewers expect the dynamic programming reasoning because it clearly models the partition validity at each prefix of the array. After presenting the DP idea, compressing it to constant space demonstrates deeper understanding and optimization skills. Both approaches rely on recognizing valid local patterns and validating them against previously solved subproblems.

Approach 1: Dynamic Programming Approach

The dynamic programming approach uses a dp array where dp[i] is true if there is a valid partition for the subarray nums[0..i]. We initialize dp[0] as false because there cannot be a valid partition for a single element. Then, for each i, we check for all valid configurations of subarrays ending at i, i.e., [i-1,i], [i-2,i], and [i-2,i-1,i], updating the dp array accordingly.

def validPartition(nums):
    n = len(nums)
    if n < 2:
        return False

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

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

    return dp[n]
public class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        dp[1] = nums[0] == nums[1];

        for (int i = 2; i < n; ++i) {
            if (nums[i] == nums[i - 1] && dp[i - 1]) dp[i + 1] = true;
            if (nums[i] == nums[i - 1] && nums[i] == nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
            if (nums[i] - 1 == nums[i - 1] && nums[i - 1] - 1 == nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
        }
        return dp[n];
    }
}
#include <vector>
using namespace std;

bool validPartition(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    dp[1] = nums[0] == nums[1];

    for (int i = 2; i < n; ++i) {
        if (nums[i] == nums[i-1] && dp[i-1]) dp[i+1] = true;
        if (nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && dp[i-2]) dp[i+1] = true;
        if (nums[i] - 1 == nums[i-1] && nums[i-1] - 1 == nums[i-2] && dp[i-2]) dp[i+1] = true;
    }
    return dp[n];
}
function validPartition(nums) {
    const n = nums.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    dp[1] = nums[0] === nums[1];

    for (let i = 2; i < n; i++) {
        if (nums[i] === nums[i - 1] && dp[i - 1]) dp[i + 1] = true;
        if (nums[i] === nums[i - 1] && nums[i - 1] === nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
        if (nums[i] - 1 === nums[i - 1] && nums[i - 1] - 1 === nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
    }
    return dp[n];
}
public class Solution {
    public bool ValidPartition(int[] nums) {
        int n = nums.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        if (n > 1) dp[1] = nums[0] == nums[1];

        for (int i = 2; i < n; ++i) {
            if (nums[i] == nums[i - 1] && dp[i - 1]) dp[i + 1] = true;
            if (nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
            if (nums[i] - 1 == nums[i - 1] && nums[i - 1] - 1 == nums[i - 2] && dp[i - 2]) dp[i + 1] = true;
        }
        return dp[n];
    }
}

This code uses a dynamic programming approach to iterate through the list, checking and updating the validity of partitions.

Complexity

Time Complexity: O(n), where n is the length of the array since we iterate through the array once.
Space Complexity: O(n) for the dp array.

Try this approach in the editor

Approach 2: Greedy Approach

The greedy approach attempts to form valid subarrays by traversing the array and greedily picking the largest valid partition at each position. While processing the elements, if a valid subarray is found, the elements involved are ignored in subsequent iterations. Note, this provides a simple but possibly non-optimal solution for certain edge cases.

def validPartition(nums):
    n = len(nums)
    i = 0
    while i < n:
        if i < n - 1 and nums[i] == nums[i+1]:
            i += 2
        elif i < n - 2 and nums[i] == nums[i+1] == nums[i+2]:
            i += 3
        elif i < n - 2 and nums[i+1] - nums[i] == 1 and nums[i+2] - nums[i+1] == 1:
            i += 3
        else:
            return False
    return True
public class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            if (i < n - 1 && nums[i] == nums[i+1]) {
                i += 2;
            } else if (i < n - 2 && nums[i] == nums[i+1] && nums[i+1] == nums[i+2]) {
                i += 3;
            } else if (i < n - 2 && nums[i+1] - nums[i] == 1 && nums[i+2] - nums[i+1] == 1) {
                i += 3;
            } else {
                return false;
            }
        }
        return true;
    }
}
#include <vector>
using namespace std;

bool validPartition(vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        if (i < n - 1 && nums[i] == nums[i + 1]) {
            i += 2;
        } else if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {
            i += 3;
        } else if (i < n - 2 && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1) {
            i += 3;
        } else {
            return false;
        }
    }
    return true;
}
function validPartition(nums) {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        if (i < n - 1 && nums[i] === nums[i + 1]) {
            i += 2;
        } else if (i < n - 2 && nums[i] === nums[i + 1] && nums[i + 1] === nums[i + 2]) {
            i += 3;
        } else if (i < n - 2 && nums[i + 1] - nums[i] === 1 && nums[i + 2] - nums[i + 1] === 1) {
            i += 3;
        } else {
            return false;
        }
    }
    return true;
}
public class Solution {
    public bool ValidPartition(int[] nums) {
        int n = nums.Length;
        int i = 0;
        while (i < n) {
            if (i < n - 1 && nums[i] == nums[i + 1]) {
                i += 2;
            } else if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {
                i += 3;
            } else if (i < n - 2 && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1) {
                i += 3;
            } else {
                return false;
            }
        }
        return true;
    }
}

This solution greedily attempts to find and skip valid subarrays during a single pass through the array, which can be efficient but is less robust than dynamic programming.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

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

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);
}
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)
}
Try this approach in the editor

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

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];
}
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]
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n), where n is the length of the array since we iterate through the array once.
Space Complexity: O(n) for the dp array.

Greedy Approach

Time Complexity: O(n)
Space Complexity: O(1)

Memoization Search–
Dynamic Programming–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (DP Table)O(n)O(n)Best for explaining the logic clearly and deriving the recurrence during interviews
Greedy / State Compressed DPO(n)O(1)Use when optimizing memory since only the last few DP states are required

Frequently asked questions

Is Check if There is a Valid Partition For The Array easy or hard?

The problem is classified as Medium difficulty. The main challenge is recognizing that the array should be evaluated by prefix validity and that only a few partition patterns are allowed, which leads naturally to a dynamic programming solution.

Check if There is a Valid Partition For The Array Python/Java solution

Python and Java implementations typically create a DP array where dp[i] represents whether the first i elements can be partitioned correctly. Each iteration checks two‑element and three‑element patterns and updates the DP state accordingly. The same logic translates directly to C++, C#, and JavaScript.

How to solve Check if There is a Valid Partition For The Array in O(n)?

Iterate through the array while maintaining a DP state indicating whether the previous positions formed a valid partition. At each index, check if the last two numbers are equal or if the last three numbers are either equal or consecutive increasing. If any rule holds and the earlier state was valid, mark the current position valid.

What is the best approach for Check if There is a Valid Partition For The Array?

The dynamic programming approach is the most reliable solution. It tracks whether each prefix of the array can form a valid partition using the allowed patterns: two equal numbers, three equal numbers, or three consecutive numbers. The algorithm runs in O(n) time and checks constant conditions at each index.

Is Check if There is a Valid Partition For The Array asked at Google/Amazon/Meta?

Dynamic programming problems with array partitioning patterns commonly appear in interviews at companies like Amazon, Google, and Meta. Variations test whether candidates can model prefix states and design efficient DP transitions.

What data structure is used in Check if There is a Valid Partition For The Array?

The core structure is a dynamic programming array that stores whether a prefix of the input array forms a valid partition. The optimized version reduces this to a few boolean variables representing the last DP states.

What is the time complexity of Check if There is a Valid Partition For The Array?

The optimal solution runs in O(n) time because the array is scanned once while checking a few constant patterns at each step. The standard DP implementation uses O(n) space for the table, though this can be reduced to O(1) using state compression.

Comments

Next problem · similarCount the Number of Good PartitionsHard
Now write it yourselfClose this page and solve Check if There is a Valid Partition For The Array in the editor, without looking.
Practise Check if There is a Valid Partition For The Array