2811. Check if it is Possible to Split Array


Problem Description

The problem presents us with an array called nums with length n, and an integer m. We need to determine if it's possible to divide the array into n non-empty arrays by carrying out a certain process.

The division process allows us to split any existing array into two subarrays, as long as each of the resulting subarrays meets at least one of these two conditions:

  1. The subarray length is one, meaning it cannot be split further.
  2. The sum of the elements in the subarray is equal to or greater than m.

The overall goal is to determine if we can continue splitting the arrays in this manner until we have exactly n non-empty arrays. We must return true if such a split is possible, or false otherwise. A subarray is defined as a contiguous sequence of elements within the array, meaning the elements of the subarray are next to each other and have not been reordered.

Intuition

To solve this problem, we'll employ the approach of depth-first search (DFS) to explore all possible ways of splitting the array until each resulting subarray meets the specified conditions. The recursive nature of DFS is suitable for this task because we need to try all possible splits and then, for each split, try all possible subsequent splits, and so on.

We begin by precomputing the prefix sums of the array, which helps us efficiently calculate the sum of any subarray in constant time. This optimization is crucial to ensure that we're not recalculating the sum of elements over and over for each potential subarray division.

Now, we define a recursive function dfs(i, j) which checks whether we can split the subarray nums[i:j+1] successfully according to the rules provided.

This recursive function works as follows:

  1. If the current subarray length is 1 (i.e., i == j), this means we cannot split it further and the condition is trivially satisfied. We return true.
  2. Otherwise, we iterate over all possible split points k from i to j - 1 to divide the array into two parts: nums[i:k] and nums[k+1:j].
  3. For each split point k, we check if the sum of elements in both subarrays is greater than or equal to m.
  4. If both resulting subarrays satisfy one of the conditions (either they cannot be split further or their sum is greater than or equal to m), we recursively call dfs on them.
  5. If the recursive calls return true for both subarrays, it means we can successfully split the array with the current split point k. We then return true.
  6. If no split point allows for a successful division, we return false.

The resulting decision tree created by the recursive dfs function will explore all possible ways to split the array and eventually tell us if it's possible or not to split the original array into n non-empty arrays satisfying the given conditions.

We cache the results of function calls to ensure we do not repeat the same computation multiple times for the same subarray, which significantly reduces the complexity and makes the solution feasible within a reasonable time frame.

The final call to dfs(0, len(nums) - 1) kicks off the process by attempting to split the entire original array.

Learn more about Greedy and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The solution takes a dynamic programming approach using a depth-first search (DFS) pattern along with memoization to avoid redundant computations. The primary data structure used is the s, which is a list of prefix sums of the given nums array. This structure allows us to quickly obtain the sum of any subarray in constant time. By using the accumulate method from the itertools module, we generate this list such that s[i] represents the sum of elements from the start of the array up to but not including element i of nums.

Let's walk through the key parts of the implementation:

  1. Prefix Sum Computation:

    1s = list(accumulate(nums, initial=0))

    The prefix sums array s is initialized with an additional 0 at the start for simplifying edge cases. This means that the sum of the subarray nums[i:j+1] can be calculated as s[j + 1] - s[i].

  2. Depth-First Search Function (DFS): The recursive dfs function is the core of the solution, defined as:

    1@cache
    2def dfs(i: int, j: int) -> bool:

    This function is decorated with @cache from the functools library, which automatically stores the results of recursive calls, thus implementing memoization.

  3. Base Case:

    1if i == j:
    2    return True

    If the subarray has length 1 (i == j), we cannot split it further, and this satisfies the condition.

  4. Recursive Case: The loop iterates through all possible split points between i and j exclusively.

    1for k in range(i, j):

    The loop checks each potential way to split nums[i:j+1] into nums[i:k] and nums[k+1:j].

  5. Condition Checking:

    1a = k == i or s[k + 1] - s[i] >= m
    2b = k == j - 1 or s[j + 1] - s[k + 1] >= m

    Here, a checks if the left subarray (nums[i:k]) either can't be split further (k == i) or its sum meets the condition (>= m). Similarly, b checks the right subarray (nums[k+1:j]).

  6. Recursive Calls and Conjunction:

    1if a and b and dfs(i, k) and dfs(k + 1, j):
    2    return True

    If both subarrays meet their respective conditions (a and b), recursive calls are made to check if the subarrays can be split further following the rules. If both calls return true, the current split is a valid split and the function returns true.

  7. Return False:

    1return False

    If no valid split is found, the function returns false.

  8. Initial Call: The initial call is made to attempt to split the whole array:

    1return dfs(0, len(nums) - 1)

    This call begins the recursion, and if it returns true, then the array can be split according to the given conditions.

In summary, the implementation explores all possible divisions of the array into required subarrays using a depth-first search while memorizing intermediate results to reduce the computational overhead. The final return value indicates whether the original array can be split into n non-empty arrays that meet the specified constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider an array nums = [3, 2, 2, 1] with m = 4.

  1. Prefix Sum Computation: Compute the prefix sums:

    1s = [0, 3, 5, 7, 8] // [initial 0, sum up to before index 1, 2, 3, 4 of nums]
  2. Initial Call: We begin with the function call dfs(0, 3) to split the whole array, nums[0:4].

  3. Explore Splits: For split point k = 0, we have:

    • Left subarray: nums[0:0], which is empty and invalid.
    • Move to the next split point.

    For split point k = 1, we have:

    • Left sum: s[1] - s[0] = 3 - 0 = 3, which is less than m, so cannot be used.
    • Move to the next split point.

    For split point k = 2, we have:

    • Left subarray: nums[0:2] ([3, 2])
    • Right subarray: nums[2:4] ([2, 1])
    • Left sum: s[2] - s[0] = 5, which is greater than m.
    • Right sum: s[4] - s[2] = 3, which is less than m.

    But since the right subarray length is not 1, we need to check its possible splits recursively.

    For the left subarray:

    • Call dfs(0, 1) which checks whether nums[0:2] can be split.

      For split point k = 0, we have:

      • Left and right subarray sums are 3 and 2 respectively.
      • Both subarrays cannot be split further (single element arrays).
      • The condition is satisfied (base case). Return true.

    For the right subarray:

    • Call dfs(2, 3) which checks whether nums[2:4] can be split.

      For split point k = 2, we have:

      • Left and right subarray sums are both 2 and 1 respectively.
      • Both cannot be split further (single element arrays).
      • The condition is satisfied (base case), return true.

    Since both left and right splits from the main split k = 2 returned true, our initial dfs(0,3) will also return true.

  4. Final Output: The final call to dfs(0, 3) returns true, indicating that it's possible to split the array nums = [3, 2, 2, 1] into subarrays that meet the condition or have a length of 1. The subarrays after valid splits are nums[0:2] = [3, 2] and nums[2:4] = [2, 1].

This example illustrates the recursive and divide-and-conquer nature of the depth-first search approach used to solve the problem, leveraging memoization to avoid redundant computations and improve efficiency.

Solution Implementation

1from typing import List
2from functools import lru_cache
3from itertools import accumulate
4
5class Solution:
6    def canSplitArray(self, nums: List[int], required_minimum: int) -> bool:
7        @lru_cache(None)  # Use memoization to cache results of the recursive calls for optimization
8        def dfs(start: int, end: int) -> bool:
9            # Base case: if the segment contains only one element, it can always be split
10            if start == end:
11                return True
12            # Try to split the array at different positions
13            for split_point in range(start, end):
14                # Check if the sum of the left segment is at least 'required_minimum'
15                left_valid = split_point == start or prefix_sums[split_point + 1] - prefix_sums[start] >= required_minimum
16                # Check if the sum of the right segment is at least 'required_minimum'
17                right_valid = split_point == end - 1 or prefix_sums[end + 1] - prefix_sums[split_point + 1] >= required_minimum
18                # If both segments are valid and can be further split, return True
19                if left_valid and right_valid and dfs(start, split_point) and dfs(split_point + 1, end):
20                    return True
21            # If no valid split was found, return False
22            return False
23
24        # Calculate the prefix sums of 'nums' to easily query the sum of any subarray
25        prefix_sums = list(accumulate(nums, initial=0))
26        # Start the depth-first search from the first to the last element
27        return dfs(0, len(nums) - 1)
28
1import java.util.List;
2
3class Solution {
4    private Boolean[][] memoization; // 2D array to store the results of subproblems
5    private int[] prefixSum; // 1D array to store the prefix sums of numbers
6    private int threshold; // The value each split must be greater than or equal to
7
8    // Method to determine if the nums array can be split according to the rules
9    public boolean canSplitArray(List<Integer> nums, int threshold) {
10        int n = nums.size();
11        memoization = new Boolean[n][n]; // Initialize the memoization array
12        prefixSum = new int[n + 1]; // Initialize the prefix sum array with one extra slot
13      
14        // Calculate prefix sums
15        for (int i = 1; i <= n; ++i) {
16            prefixSum[i] = prefixSum[i - 1] + nums.get(i - 1);
17        }
18      
19        this.threshold = threshold; // Set the global threshold value
20        // Perform a depth-first search starting with the full range
21        return dfs(0, n - 1);
22    }
23
24    // Helper method to perform a depth-first search on the array
25    private boolean dfs(int start, int end) {
26        // Base case: when only one element is left, it can be split
27        if (start == end) {
28            return true;
29        }
30        // If the subproblem has been solved before, return the stored result
31        if (memoization[start][end] != null) {
32            return memoization[start][end];
33        }
34        // Try splitting the array at each possible index
35        for (int k = start; k < end; ++k) {
36            // Determine whether the left side meets the threshold requirement
37            boolean leftMeetsThreshold = k == start || prefixSum[k + 1] - prefixSum[start] >= threshold;
38            // Determine whether the right side meets the threshold requirement
39            boolean rightMeetsThreshold = k == end - 1 || prefixSum[end + 1] - prefixSum[k + 1] >= threshold;
40          
41            // If both sides meet the threshold, and both recursive calls return true
42            if (leftMeetsThreshold && rightMeetsThreshold && dfs(start, k) && dfs(k + 1, end)) {
43                // Then this split is possible, store and return true
44                return memoization[start][end] = true;
45            }
46        }
47        // If no split meets the criteria, store and return false
48        return memoization[start][end] = false;
49    }
50}
51
1#include <vector>
2#include <cstring>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    bool canSplitArray(vector<int>& nums, int m) {
10        int n = nums.size();
11        // Create a prefix sum array 'prefixSums' with one extra space for easier calculations
12        vector<int> prefixSums(n + 1, 0);
13        for (int i = 1; i <= n; ++i) {
14            prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
15        }
16      
17        // Create a memoization table to store results of subproblems
18        int memo[n][n];
19        memset(memo, -1, sizeof memo);
20
21        // Define the recursive function with memoization to determine if we can split the array
22        function<bool(int, int)> canSplit = [&](int start, int end) {
23            // Base case: A single element can always form a valid subarray
24            if (start == end) {
25                return true;
26            }
27            // If we already computed this subproblem, return the stored result
28            if (memo[start][end] != -1) {
29                return memo[start][end] == 1;
30            }
31            // Explore splitting points between 'start' and 'end'
32            for (int split = start; split < end; ++split) {
33                // Condition to check if the left subarray is valid
34                bool leftValid = split == start || prefixSums[split + 1] - prefixSums[start] >= m;
35                // Condition to check if the right subarray is valid
36                bool rightValid = split == end - 1 || prefixSums[end + 1] - prefixSums[split + 1] >= m;
37                // If both subarrays are valid, and recursive calls for both subarrays return true
38                if (leftValid && rightValid && canSplit(start, split) && canSplit(split + 1, end)) {
39                    memo[start][end] = 1;
40                    return true;
41                }
42            }
43            // Mark this subproblem as impossible to split and return false
44            memo[start][end] = 0;
45            return false;
46        };
47
48        // Call the helper function starting from the whole array (0, n-1)
49        return canSplit(0, n - 1);
50    }
51};
52
1function canSplitArray(nums: number[], targetSum: number): boolean {
2    const numCount = nums.length;
3  
4    // Prefix sums array with an extra slot for simplifying calculations.
5    const prefixSums: number[] = new Array(numCount + 1).fill(0);
6    for (let i = 1; i <= numCount; ++i) {
7        prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
8    }
9  
10    // Cache for memoization to avoid recalculating subproblems.
11    const memo: number[][] = Array(numCount)
12        .fill(0)
13        .map(() => Array(numCount).fill(-1));
14
15    // Recursive function to determine if the array can be split.
16    const canSplit = (start: number, end: number): boolean => {
17        // Base case when the subarray has only one element.
18        if (start === end) {
19            return true;
20        }
21      
22        // Check the memo table to avoid re-calculation.
23        if (memo[start][end] !== -1) {
24            return memo[start][end] === 1;
25        }
26      
27        // Try splitting the array at different points.
28        for (let splitPoint = start; splitPoint < end; ++splitPoint) {
29            // Determine if left part meets the target sum condition.
30            const leftCondition = splitPoint === start || prefixSums[splitPoint + 1] - prefixSums[start] >= targetSum;
31            // Determine if right part meets the target sum condition.
32            const rightCondition = splitPoint === end - 1 || prefixSums[end + 1] - prefixSums[splitPoint + 1] >= targetSum;
33          
34            // Only when both conditions are met and the subarrays can be split further, we continue.
35            if (leftCondition && rightCondition && canSplit(start, splitPoint) && canSplit(splitPoint + 1, end)) {
36                memo[start][end] = 1;
37                return true;
38            }
39        }
40      
41        // If split is not possible, update memo and return false.
42        memo[start][end] = 0;
43        return false;
44    };
45
46    // Call the recursive function on the full array.
47    return canSplit(0, numCount - 1);
48}
49
Not Sure What to Study? Take the 2-min Quiz:

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily governed by the depth-first search implemented in the dfs function. We are exploring all possible ways to split the array nums into subarrays with the constraint that each subarray sum should be no less than m.

Every element in the array could be a potential splitting point, and at each splitting point, we are making two recursive calls to the dfs function (one for the left side of the split and one for the right side). In the worst-case scenario, this recursive process forms a full binary tree because we consider splitting at each point and each of those splits can lead to two more splits, and so on.

However, the use of the @cache decorator (which utilizes memoization) significantly cuts down on redundant calculations by storing previously computed results of the dfs function. This means we won't compute the same state ((i, j) pair) more than once.

If n is the length of nums, in the worst case without memoization, the dfs function could be called in order of O(2^n) times (since each function call can lead to two more). With memoization, each unique pair (i, j) will be calculated only once, leading to O(n^2) possible states.

The for loop within the dfs function iterates from i to j, so in the worst case, it could iterate n times for each recursive call. Therefore, considering memoization and the nested loop, the time complexity would be O(n^3).

Space Complexity

The space complexity of the code comes from the use of recursive calls in the dfs function (which uses the call stack) and memoization (which uses additional space to store the results).

  1. Call Stack: In the worst case, the call stack could go as deep as n levels since we might recursively be calling the dfs from the first element to the last. Therefore, the call stack could contribute O(n) space complexity.

  2. Memoization Cache: Since we are caching each unique (i, j) pair, and there could be O(n^2) such pairs, the space complexity due to memoization is O(n^2).

The space complexity for the array s, which holds the prefix sums, is O(n).

When combined, the dominating factor is the memoization space, leading to an overall space complexity of O(n^2).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫