LeetCode 2811 - Check if it is Possible to Split Array

LeetCode Problem 2811

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem asks whether it is possible to split an input array nums into exactly n arrays of size one using a series of valid splits. Each split must take an existing array of length at least two and divide it into two good arrays. An array is considered good if it is either of length one, or if the sum of its elements is greater than or equal to the given integer m. The input consists of an array of integers nums and a threshold integer m. The output is a boolean indicating whether the array can eventually be split into n arrays of size one under these rules.

Key points are that each split is restrictive: both resulting arrays must be good, which means splits are only allowed if they meet the sum threshold or result in single-element arrays. This prevents arbitrary splits and is the core constraint of the problem. The constraints are relatively small (n <= 100 and nums[i] <= 100), which suggests an approach that checks pairs or adjacent sums may be efficient enough. Edge cases include very small arrays (n = 1), arrays where no pair of elements sum to m or more, and arrays where m is larger than any possible sum.

The problem essentially tests whether there exists a valid sequence of splits from the full array down to all single-element arrays, given that only "good" subarrays are allowed.

Approaches

Brute Force

A brute-force approach would recursively attempt all possible splits of the array into two subarrays and check if both subarrays are good. If both are good, we would continue recursively until all subarrays are of size one. While this approach is correct, it is too slow due to the exponential number of split combinations (O(2^n)), especially as n approaches 100. Checking the sum of every subarray repeatedly adds further overhead.

Key Insight for Optimal Solution

The main insight is that for arrays of length greater than 2, it is sufficient to check whether any single split at an adjacent pair of elements yields at least one valid way to proceed. Since every single-element array is automatically good, only the sum of adjacent pairs affects whether splits are possible. Specifically, if at least one adjacent pair of elements has a sum greater than or equal to m, a valid sequence of splits exists. Additionally, arrays of length 1 or 2 are trivial cases.

This observation reduces the problem from considering all possible splits to simply checking the sum of adjacent elements and the length of the array, which leads to an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively try all splits, slow for n=100
Optimal	O(n)	O(1)	Check adjacent sums and handle n <= 2 as special cases

Algorithm Walkthrough

1. First, handle trivial cases where the array length n is less than or equal to 2. Any array of size 1 or 2 can always be split according to the rules, since single-element arrays are automatically good and two-element arrays can be split if either element is good.
2. For arrays of length greater than 2, iterate through the array and check each pair of consecutive elements nums[i] + nums[i+1].
3. If any adjacent pair sums to a value greater than or equal to m, return True, because this indicates that a valid sequence of splits exists starting at this pair.
4. If no such pair exists, return False, as there is no way to split the array while ensuring all resulting arrays are good.

This approach works because a valid split sequence requires that at least one intermediate split preserves the "good array" property, and adjacent pairs are the minimal unit that can form a valid split for arrays of length greater than 2.

Python Solution

from typing import List

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        n = len(nums)
        if n <= 2:
            return True
        for i in range(n - 1):
            if nums[i] + nums[i + 1] >= m:
                return True
        return False

The implementation first checks if the array is trivially splittable due to its small size. It then iterates through adjacent pairs, returning True if any pair meets the sum requirement, otherwise returning False. This aligns directly with the algorithm walkthrough.

Go Solution

func canSplitArray(nums []int, m int) bool {
    n := len(nums)
    if n <= 2 {
        return true
    }
    for i := 0; i < n-1; i++ {
        if nums[i]+nums[i+1] >= m {
            return true
        }
    }
    return false
}

The Go implementation mirrors the Python version. It handles array lengths of 1 or 2 as trivial cases, then iterates through adjacent pairs to find a sum that satisfies the m condition. Slice indexing in Go is used carefully to avoid out-of-range errors.

Worked Examples

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

Step	Array	Check
Initial	[2,2,1]	n > 2
i=0	2+2=4	>= m → return True

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

Step	Array	Check
Initial	[2,1,3]	n > 2
i=0	2+1=3	< m
i=1	1+3=4	< m → return False

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

Step	Array	Check
Initial	[2,3,3,2,3]	n > 2
i=0	2+3=5	< m
i=1	3+3=6	>= m → return True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We only iterate through the array once checking adjacent pairs
Space	O(1)	Only a few variables used; no extra data structures

The time complexity is linear because we examine each adjacent pair once. The space complexity is constant because no additional storage is required.

Test Cases

# Provided examples
assert Solution().canSplitArray([2, 2, 1], 4) == True  # splits possible
assert Solution().canSplitArray([2, 1, 3], 5) == False  # no valid splits
assert Solution().canSplitArray([2, 3, 3, 2, 3], 6) == True  # valid splits

# Boundary cases
assert Solution().canSplitArray([1], 1) == True  # single element
assert Solution().canSplitArray([1, 2], 10) == True  # two elements, automatically True
assert Solution().canSplitArray([1, 1, 1, 1], 3) == False  # no adjacent pair sums >= m
assert Solution().canSplitArray([1, 2, 2, 1], 3) == True  # adjacent pair sums to m

Test	Why
[2,2,1], 4	Basic valid split
[2,1,3], 5	Basic invalid split
[2,3,3,2,3], 6	Multiple steps valid
[1],1	Trivial single element
[1,2],10	Trivial two-element array
[1,1,1,1],3	No pair meets m, should fail
[1,2,2,1],3	Edge case with valid adjacent pair

Edge Cases

First, arrays of length 1 or 2 are trivial because single-element arrays are always good. No sum checks are needed. This could trip up implementations that expect at least 3 elements.

Second, arrays where no adjacent pair meets the threshold m represent a failure case. The algorithm correctly returns False without attempting unnecessary splits.

Third, arrays where multiple valid adjacent pairs exist demonstrate that only one pair needs to satisfy the condition. This ensures that the algorithm is efficient and avoids overcomplicating the split logic.