Problem Description

You are given an array nums of length n and an integer m. Your goal is to determine if you can split this array into n separate arrays, where each final array contains exactly one element.

The splitting process follows specific rules:

A good array is defined as:

• An array with length equal to 1, OR
• An array whose sum of elements is greater than or equal to m

The splitting process works as follows:

• Start with the original array nums
• In each step, select any existing array that has at least 2 elements
• Split the selected array into exactly 2 new arrays
• Both resulting arrays must be "good" for the split to be valid
• Continue this process until you either:
  • Successfully split everything into n single-element arrays (return true)
  • Cannot make any more valid splits (return false)

For example, if nums = [2, 3, 3, 2, 3] and m = 6:

• You could split [2, 3, 3, 2, 3] into [2, 3, 3] (sum = 8 ≥ 6, good) and [2, 3] (sum = 5 < 6, but length > 1, need to check if splittable)
• Continue splitting until all arrays have length 1

The key challenge is finding the right sequence of splits where at each step, both resulting subarrays are either single elements or have a sum ≥ m.

Intuition

The key insight is that we need to think about this problem recursively. When we split an array into two parts, both parts must be "good" - meaning they either have length 1 or sum ≥ m. After the split, we need to continue splitting each part independently until everything becomes single elements.

This naturally leads to a recursive approach: for any subarray [i, j], we try all possible split points k and check if:

1. The left part [i, k] is good (either single element or sum ≥ m)
2. The right part [k+1, j] is good (either single element or sum ≥ m)
3. Both parts can be further split successfully into single elements

The beauty of this approach is that we can use dynamic programming with memoization. If we've already computed whether a subarray [i, j] can be successfully split, we don't need to compute it again.

To efficiently calculate sums of subarrays, we use a prefix sum array s. This allows us to compute the sum of any subarray [i, j] in O(1) time using s[j+1] - s[i].

The recursive function dfs(i, j) answers: "Can the subarray from index i to j be split into single elements following the rules?"

Base case: If i == j, we already have a single element, so return true.

Recursive case: Try every possible split point k between i and j-1. For each split:

• Check if left part is good: k == i (single element) or s[k+1] - s[i] >= m
• Check if right part is good: k == j-1 (single element) or s[j+1] - s[k+1] >= m
• Recursively check if both parts can be further split: dfs(i, k) and dfs(k+1, j)

The answer is dfs(0, n-1) - whether the entire array can be split into single elements.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The implementation uses memoization search (top-down dynamic programming) with a prefix sum array for efficient range sum queries.

Step 1: Build Prefix Sum Array

We first create a prefix sum array s using accumulate(nums, initial=0):

• s[i] represents the sum of the first i elements
• This allows us to calculate the sum of subarray [i, j] as s[j+1] - s[i] in O(1) time

Step 2: Define Recursive Function with Memoization

The function dfs(i, j) determines if the subarray nums[i..j] can be split into single elements:

@cache  # Memoization decorator to avoid recomputation
def dfs(i: int, j: int) -> bool:

Step 3: Handle Base Case

If i == j, we have a single element, which doesn't need splitting:

if i == j:
    return True

Step 4: Try All Possible Split Points

For each potential split point k in range [i, j), we split the array into:

• Left part: nums[i..k]
• Right part: nums[k+1..j]

Step 5: Check if Both Parts are Good

For each split point k:

• Variable a checks if left part is good:

  • k == i: single element (always good)
  • OR s[k + 1] - s[i] >= m: sum of left part ≥ m

• Variable b checks if right part is good:

  • k == j - 1: single element (always good)
  • OR s[j + 1] - s[k + 1] >= m: sum of right part ≥ m

Step 6: Recursive Validation

If both parts are good (a and b are true), recursively check:

• dfs(i, k): Can left part be split into single elements?
• dfs(k + 1, j): Can right part be split into single elements?

If all conditions are met for any split point, return True.

Step 7: Return Result

The final answer is dfs(0, len(nums) - 1), checking if the entire array can be split.

The @cache decorator ensures each subproblem dfs(i, j) is computed only once, giving us O(n³) time complexity (n² possible subarrays × n split points each) and O(n²) space complexity for memoization.

Example Walkthrough

Let's walk through a small example with nums = [2, 1, 5, 2] and m = 4.

Initial Setup:

• Build prefix sum array: s = [0, 2, 3, 8, 10]
• This allows us to calculate any subarray sum quickly
• For example: sum of nums[1..2] = s[3] - s[1] = 8 - 2 = 6

Goal: Call dfs(0, 3) to check if we can split the entire array into 4 single elements.

Step 1: dfs(0, 3) - Split array [2, 1, 5, 2]

Try split point k = 0:

• Left part: [2] (single element, good ✓)
• Right part: [1, 5, 2] with sum = 8 ≥ 4 (good ✓)
• Recursively check: dfs(0, 0) AND dfs(1, 3)

Step 2: dfs(0, 0) - Array [2]

• Base case: i == j, return True ✓

Step 3: dfs(1, 3) - Split array [1, 5, 2]

Try split point k = 1:

• Left part: [1] (single element, good ✓)
• Right part: [5, 2] with sum = 7 ≥ 4 (good ✓)
• Recursively check: dfs(1, 1) AND dfs(2, 3)

Step 4: dfs(1, 1) - Array [1]

• Base case: return True ✓

Step 5: dfs(2, 3) - Split array [5, 2]

Try split point k = 2:

• Left part: [5] (single element, good ✓)
• Right part: [2] (single element, good ✓)
• Recursively check: dfs(2, 2) AND dfs(3, 3)

Step 6: dfs(2, 2) and dfs(3, 3)

• Both are base cases, return True ✓

Result: All recursive calls return True, so the entire array can be successfully split!

The splitting sequence would be:

1. [2, 1, 5, 2] → [2] and [1, 5, 2]
2. [1, 5, 2] → [1] and [5, 2]
3. [5, 2] → [5] and [2]

Each split creates two "good" arrays (either single elements or sum ≥ 4), and we successfully reach 4 single-element arrays.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n³)

The analysis breaks down as follows:

• The recursive function dfs(i, j) uses memoization with @cache, so each unique state (i, j) is computed only once
• There are O(n²) possible states since i can range from 0 to n-1 and j can range from i to n-1
• For each state (i, j), the function iterates through all possible split points k from i to j-1, which takes O(j - i) = O(n) time in the worst case
• The operations inside the loop (checking conditions a and b using prefix sums) take O(1) time
• Therefore, the total time complexity is O(n²) × O(n) = O(n³)

Space Complexity: O(n²)

The space usage comes from:

• The memoization cache stores results for all possible (i, j) pairs, which requires O(n²) space
• The prefix sum array s requires O(n) space
• The recursion stack depth can be at most O(n) in the worst case
• Since O(n²) dominates, the overall space complexity is O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Index Handling

One of the most common mistakes in this problem is confusion between inclusive and exclusive indices when working with the prefix sum array and recursive calls.

Pitfall Example:

# Incorrect: Mixing up index boundaries
right_part_valid = (split_point == right or  # Wrong comparison!
                   prefix_sum[right] - prefix_sum[split_point + 1] >= m)  # Wrong index!

Why it happens: The prefix sum array has length n+1 while the original array has length n. It's easy to confuse:

• prefix_sum[i] represents sum of first i elements (0 to i-1)
• nums[i] represents the element at index i

Solution: Always remember:

• For sum of subarray from index i to j (inclusive): use prefix_sum[j + 1] - prefix_sum[i]
• When checking if right part is a single element after splitting at split_point, compare with right - 1, not right

2. Forgetting to Check Both Split Conditions

Pitfall Example:

# Incorrect: Only checking if parts can be recursively split
for split_point in range(left, right):
    if can_split_range(left, split_point) and can_split_range(split_point + 1, right):
        return True  # Forgot to check if parts are "good"!

Why it happens: The problem has two layers of validation:

1. Each split must produce two "good" arrays (single element OR sum ≥ m)
2. Each resulting array must be recursively splittable

Solution: Always validate both conditions:

if (left_part_valid and right_part_valid and  # Check if parts are good
    can_split_range(left, split_point) and     # Check recursive splitting
    can_split_range(split_point + 1, right)):

3. Incorrect Base Case for Arrays of Length 2

Pitfall Example:

# Incorrect: Special-casing length 2 arrays
if right - left == 1:  # Array of length 2
    return nums[left] >= m or nums[right] >= m  # Wrong logic!

Why it happens: It's tempting to add special cases for small arrays, but this can introduce bugs. An array of length 2 can only be split into two single elements, and single elements are always "good" regardless of their value.

Solution: Keep the base case simple - only check for single elements:

if left == right:
    return True
# Let the general case handle arrays of length 2+

4. Not Using Memoization or Using It Incorrectly

Pitfall Example:

# Incorrect: Forgetting memoization leads to exponential time complexity
def can_split_range(left: int, right: int) -> bool:  # No @cache decorator!
    # ... recursive calls without memoization

Why it happens: Without memoization, the same subproblems are computed multiple times, leading to exponential time complexity that will cause timeout for larger inputs.

Solution: Always use memoization for overlapping subproblems:

• Use @cache decorator from functools
• Or manually implement with a dictionary/2D array
• Ensure the function parameters are hashable (integers, not lists)

5. Edge Case: Arrays with Length ≤ 2

Pitfall Example:

# Forgetting that arrays of length 1 or 2 have special behavior
nums = [5]  # Length 1 - always returns True
nums = [3, 2]  # Length 2 - always returns True (splits into two single elements)

Why it happens: The problem statement might not explicitly clarify these cases, leading to overthinking.

Solution: Remember the fundamental rule:

• Single elements are always "good"
• Any array of length ≤ 2 can always be split into single elements
• The algorithm handles these naturally without special cases