#2811

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Check if it is Possible to Split Array

Determine whether an array can be fully split into single-element subarrays using a state transition dynamic programming approach efficiently.

array dynamic programming greedy

Problem Statement

Given an integer array nums of length n and an integer m, determine if it is possible to repeatedly split the array into smaller arrays until all arrays have size one. Each step allows selecting an array of length at least two and splitting it into two arrays, but both resulting arrays must satisfy the good array condition defined by the problem.

An array is considered good if, after any split, both resulting arrays can eventually be split into single-element arrays following the same rules. You must decide whether nums can be fully decomposed into n arrays of size one while respecting these constraints.

Examples

Example 1

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

Output: true

Example 2

Input: nums = [2, 1, 3], m = 5

Output: false

The first move has to be either of the following: So as both moves are invalid (they do not divide the array into two good arrays), we are unable to split nums into n arrays of size 1.

Example 3

Input: nums = [2, 3, 3, 2, 3], m = 6

Output: true

Constraints

1 <= n == nums.length <= 100
1 <= nums[i] <= 100
1 <= m <= 200

Solution Approach

Dynamic Programming State Tracking

Use a DP array where dp[i] indicates whether the first i elements can be split into good arrays. For each i, check all j < i and see if nums[j:i] forms a valid good array. Update dp[i] based on previous states to reflect all possible splits.

Greedy Optimization for Valid Splits

When multiple split positions exist, choose the one that maximizes progress toward size-one arrays. This leverages the problem's property that if a subarray of length greater than one can be split, then it can always be split down to size one.

Validation and Early Termination

At each step, validate that both resulting subarrays are good according to the DP states. If no valid split exists for a subarray, terminate early to avoid unnecessary computation and return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating through all possible split positions for each subarray, potentially O(n^2) in the worst case. Space complexity is O(n) to store the DP states for subarray validation.

What Interviewers Usually Probe

You might ask how to represent subarray validity efficiently for state transitions.
Expect a discussion on when greedy choices simplify DP state decisions.
Interviewers may probe whether early termination improves performance on unsplittable arrays.

Common Pitfalls or Variants

Common pitfalls

Failing to check that both resulting arrays are good before updating DP states.
Assuming any split is valid without considering the problem's good array definition.
Overcomplicating with unnecessary recursion instead of leveraging DP and greedy observations.

Follow-up variants

Instead of splitting into size-one arrays, determine if array can be split into subarrays summing to exactly m.
Allow splits only at positions where the sum of elements is even and validate good array recursively.
Change the definition of a good array to require at least one element greater than a threshold in each subarray.

FAQ

What is the key pattern to solve Check if it is Possible to Split Array?

The main pattern is state transition dynamic programming combined with greedy selection of valid subarray splits.

Can this problem be solved using pure recursion?

Yes, but pure recursion may be inefficient; DP with greedy choices ensures faster evaluation and avoids repeated computations.

What is a common mistake when implementing DP for this problem?

Ignoring that both resulting arrays must be good when updating DP states often leads to incorrect results.

Does array order affect the solution?

Yes, the split positions depend on the original order since subarrays must preserve sequence to remain good.

Is early termination helpful in this problem?

Absolutely, detecting unsplittable arrays early prevents unnecessary computation and speeds up the solution.

terminal

Solution

Solution 1: Memoization Search

First, we preprocess to get the prefix sum array $s$, where $s[i]$ represents the sum of the first $i$ elements of the array $nums$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i == j:
                return True
            for k in range(i, j):
                a = k == i or s[k + 1] - s[i] >= m
                b = k == j - 1 or s[j + 1] - s[k + 1] >= m
                if a and b and dfs(i, k) and dfs(k + 1, j):
                    return True
            return False

        s = list(accumulate(nums, initial=0))
        return dfs(0, len(nums) - 1)

Solution 2: Quick Thinking

No matter how you operate, there will always be a `length == 2` subarray left in the end. Since there are no negative numbers in the elements, as the split operation proceeds, the length and sum of the subarray will gradually decrease. The sum of other `length > 2` subarrays must be larger than the sum of this subarray. Therefore, we only need to consider whether there is a `length == 2` subarray with a sum greater than or equal to `m`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i == j:
                return True
            for k in range(i, j):
                a = k == i or s[k + 1] - s[i] >= m
                b = k == j - 1 or s[j + 1] - s[k + 1] >= m
                if a and b and dfs(i, k) and dfs(k + 1, j):
                    return True
            return False

        s = list(accumulate(nums, initial=0))
        return dfs(0, len(nums) - 1)

Continue Practicing

#2900 longest unequal adjacent groups subsequence i #2708 maximum strength of a group #2673 make costs of paths equal in a binary tree