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 <= 200Problem Overview: You are given an integer array and a minimum sum constraint m. The task is to determine whether the array can be repeatedly split into subarrays such that every resulting subarray of length greater than one has a sum at least m. The process continues until only single elements remain or no further valid splits exist.
Approach 1: Divide and Conquer (O(n^2) time, O(n) space)
This method recursively checks whether the array can be split at different indices while maintaining the sum constraint. For every possible partition point i, compute the sum of the left and right segments and verify that both satisfy the required condition. If both sides are valid, recursively attempt to split them further. Memoization helps avoid recomputing states for the same subarray range. This approach mirrors a classic recursive partition strategy commonly seen in dynamic programming problems where overlapping subproblems appear. It works well for explaining the problem structure but becomes expensive for large arrays because each split may trigger multiple recursive checks.
Approach 2: Heap Data Structure Approach (O(n log n) time, O(n) space)
A heap-based strategy tracks candidate segments that can still be split while maintaining the minimum sum requirement. You begin by treating the whole array as one segment and push it into a priority queue ordered by segment size or sum. At each step, remove a segment, attempt to divide it into two valid parts, and push the resulting segments back into the heap if they still meet the constraint. This technique simulates the splitting process while always working on the most promising segment first. The heap ensures efficient selection and reinsertion operations. While not the most optimal approach, it demonstrates how array segmentation problems can be modeled using priority queues.
Approach 3: Greedy Adjacent Pair Insight (O(n) time, O(1) space)
The key observation drastically simplifies the problem. If the array length is less than or equal to two, a valid split always exists. For larger arrays, check whether there exists at least one adjacent pair nums[i] + nums[i+1] >= m. If such a pair exists, the array can always be split step by step while preserving the sum constraint. That pair effectively acts as a safe pivot that keeps every intermediate segment valid during further splits. This greedy observation eliminates recursion and extra structures, making it the optimal strategy. Problems that reduce to local adjacency checks often fall under greedy algorithms.
Recommended for interviews: Start with the recursive divide-and-conquer explanation to demonstrate how you reason about valid partitions. Then move to the greedy observation. Interviewers typically expect the O(n) greedy solution because it shows you recognized the structural property of adjacent pairs rather than brute-forcing all partitions.
This approach uses the divide and conquer paradigm. The problem is broken down into smaller subproblems which are easier to solve, and their results are combined to give a solution to the original problem. For instance, in quicksort, a pivot is chosen and elements are partitioned around the pivot, solving each partition recursively.
The C implementation of quicksort selects a pivot and partitions the array around the pivot such that all elements smaller are on one side and larger on the other. It uses recursion to sort the partitions.
Time Complexity: O(n log n) on average, O(n^2) in the worst case. Space Complexity: O(log n) due to recursion stack.
This approach leverages the properties of heaps, such as the max heap or min heap, to solve problems efficiently. For instance, heapsort entails building a heap from the array and repeatedly extracting the maximum or minimum element while maintaining the heap invariant.
This C implementation of heap sort builds a max heap from the input array and then repeatedly extracts the maximum element, ensuring the array remains sorted.
Time Complexity: O(n log n) for all cases. Space Complexity: O(1) as it is an in-place sort.
| Approach | Complexity |
|---|---|
| Divide and Conquer Approach | Time Complexity: O(n log n) on average, O(n^2) in the worst case. Space Complexity: O(log n) due to recursion stack. |
| Heap Data Structure Approach | Time Complexity: O(n log n) for all cases. Space Complexity: O(1) as it is an in-place sort. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer with Memoization | O(n^2) | O(n) | When explaining recursive partition logic or exploring all valid split points |
| Heap Data Structure Simulation | O(n log n) | O(n) | When modeling the process of repeatedly splitting segments using a priority queue |
| Greedy Adjacent Pair Check | O(n) | O(1) | Best solution for interviews and production; relies on the adjacent pair sum insight |
BS 19. Painter's Partition and Split Array - Largest Sum • take U forward • 150,599 views views
Watch 9 more video solutions →Practice Check if it is Possible to Split Array with our built-in code editor and test cases.
Practice on FleetCode