You are given an array nums of length n and an integer m. You need to determine if it is possible to split the array into n arrays of size 1 by performing a series of steps.
An array is called good if:
m.In each step, you can select an existing array (which may be the result of previous steps) with a length of at least two and split it into two arrays, if both resulting arrays are good.
Return true if you can split the given array into n arrays, otherwise return false.
Example 1:
Input: nums = [2, 2, 1], m = 4
Output: true
Explanation:
[2, 2, 1] to [2, 2] and [1]. The array [1] has a length of one, and the array [2, 2] has the sum of its elements equal to 4 >= m, so both are good arrays.[2, 2] to [2] and [2]. both arrays have the length of one, so both are good arrays.Example 2:
Input: nums = [2, 1, 3], m = 5
Output: false
Explanation:
The first move has to be either of the following:
[2, 1, 3] to [2, 1] and [3]. The array [2, 1] has neither length of one nor sum of elements greater than or equal to m.[2, 1, 3] to [2] and [1, 3]. The array [1, 3] has neither length of one nor sum of elements greater than or equal to m.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
Explanation:
[2, 3, 3, 2, 3] to [2] and [3, 3, 2, 3].[3, 3, 2, 3] to [3, 3, 2] and [3].[3, 3, 2] to [3, 3] and [2].[3, 3] to [3] and [3].Constraints:
1 <= n == nums.length <= 1001 <= nums[i] <= 1001 <= m <= 200The key challenge in #2811 Check if it is Possible to Split Array is determining whether an array can be repeatedly divided into valid subarrays while maintaining the required sum constraint. A straightforward way to reason about this is through Dynamic Programming, where we check whether subarrays can be split while satisfying the minimum sum condition. In this approach, we track valid partitions and combine smaller subproblems to determine if the full array can be split.
However, a deeper observation reveals that the process can often be simplified using a Greedy insight. Instead of exploring all partitions, we look for local conditions in the array that guarantee a valid split is always possible. If such a condition exists, further splits can be performed recursively until only small segments remain.
The dynamic programming approach typically runs in O(n^2) time due to checking multiple subarray ranges, while the optimized greedy observation reduces the solution to O(n) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n^2) | O(n^2) |
| Greedy Optimization | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
It can be proven that if you can split more than one element as a subarray, then you can split exactly one element.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving greedy insights and dynamic programming patterns are common in FAANG-style interviews. While the exact question may vary, the ability to identify simplifying observations and reduce DP complexity is a frequently tested skill.
The optimal approach uses a greedy observation about adjacent elements. Instead of exploring all possible partitions, you check whether a local condition exists that guarantees the array can be split recursively. This reduces the complexity from quadratic to linear time.
Yes, dynamic programming can model the problem by checking whether each subarray can be split into valid parts that satisfy the sum constraint. However, this approach typically requires O(n^2) time and space, making it less efficient than the greedy optimization.
The problem mainly relies on array traversal and prefix or local sum observations rather than complex data structures. Most efficient solutions work directly on the input array with simple variables for tracking conditions.