Scale Engineer

Check if it is Possible to Split Array

Med
#2515Time: O(n^3) - We have three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is `O(n^2)`. The inner loop iterates over all possible split points `k`, which takes `O(n)` time. Calculating sums takes `O(1)` with the prefix sum array.Space: O(n^2) - We use a 2D DP table of size n x n and a prefix sum array of size n+1.
Patterns
Dynamic ProgrammingGreedy
Data structures
Array

Prompt

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:

  • The length of the array is one, or
  • The sum of the elements of the array is greater than or equal to 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:

  • Split [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.
  • Split [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:

  • Split [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.
  • Split [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:

  • Split [2, 3, 3, 2, 3] to [2] and [3, 3, 2, 3].
  • Split [3, 3, 2, 3] to [3, 3, 2] and [3].
  • Split [3, 3, 2] to [3, 3] and [2].
  • Split [3, 3] to [3] and [3].

 

Constraints:

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= m <= 200

Approaches

2 approaches with complexity analysis and trade-offs.

A standard approach for problems involving optimal substructure and overlapping subproblems is dynamic programming. We can define a function canSplit(i, j) that returns true if the subarray nums[i...j] can be split into j-i+1 arrays of size one. The result for canSplit(i, j) depends on the results of smaller subarrays, leading to a DP formulation.

Algorithm

  • Create a 2D boolean array dp[n][n], where dp[i][j] will store true if the subarray nums[i...j] can be fully split, and false otherwise.
  • To handle subarray sum calculations efficiently, precompute a prefixSum array.
  • The base cases for the DP are subarrays of length 1. dp[i][i] is true for all i from 0 to n-1, as a single-element array is already considered split.
  • Iterate through all possible subarray lengths, from len = 2 to n.
  • For each length, iterate through all possible starting indices i.
  • For each subarray nums[i...j] (where j = i + len - 1), try every possible split point k from i to j-1.
  • A split at k divides nums[i...j] into nums[i...k] and nums[k+1...j].
  • This split is valid if both resulting subarrays are "good". A subarray is good if its length is 1 or its sum is greater than or equal to m.
  • If the split is valid, we then check if the subarrays themselves can be further split by looking up our DP table: dp[i][k] and dp[k+1][j].
  • If we find any k for which the split is valid and both subproblems are solvable, we set dp[i][j] = true and break the inner loop (since we've found one way to split nums[i...j])
  • The final answer is the value of dp[0][n-1].

Walkthrough

We can use a 2D DP table, dp[i][j], to store whether the subarray nums[i...j] is splittable. We can build this table bottom-up, starting from smaller subarrays and building up to the entire array.

  • State: dp[i][j] = true if nums[i...j] can be split, false otherwise.
  • Base Case: For any subarray of length 1, dp[i][i] = true.
  • Transition: To compute dp[i][j], we iterate through all possible split points k from i to j-1. A split at k is possible if:
    1. The split itself is valid: The left part nums[i...k] is "good" AND the right part nums[k+1...j] is "good". An array is good if its length is 1 or its sum is >= m.
    2. The resulting subarrays can be fully split: dp[i][k] is true AND dp[k+1][j] is true.

If we find any such k, then dp[i][j] becomes true. To avoid recomputing subarray sums repeatedly, we can use a prefix sum array.

class Solution {    public boolean canSplitArray(List<Integer> nums, int m) {        int n = nums.size();        if (n <= 2) {            return true;        }         long[] prefixSum = new long[n + 1];        for (int i = 0; i < n; i++) {            prefixSum[i + 1] = prefixSum[i] + nums.get(i);        }         boolean[][] dp = new boolean[n][n];         for (int i = 0; i < n; i++) {            dp[i][i] = true;        }         for (int len = 2; len <= n; len++) {            for (int i = 0; i <= n - len; i++) {                int j = i + len - 1;                for (int k = i; k < j; k++) {                    // Split into [i...k] and [k+1...j]                    long leftSum = prefixSum[k + 1] - prefixSum[i];                    boolean isLeftGood = (k - i + 1 == 1) || (leftSum >= m);                     long rightSum = prefixSum[j + 1] - prefixSum[k + 1];                    boolean isRightGood = (j - k == 1) || (rightSum >= m);                     if (isLeftGood && isRightGood) {                        if (dp[i][k] && dp[k+1][j]) {                            dp[i][j] = true;                            break;                        }                    }                }            }        }         return dp[0][n - 1];    }}

Complexity

Time

O(n^3) - We have three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is `O(n^2)`. The inner loop iterates over all possible split points `k`, which takes `O(n)` time. Calculating sums takes `O(1)` with the prefix sum array.

Space

O(n^2) - We use a 2D DP table of size n x n and a prefix sum array of size n+1.

Trade-offs

Pros

  • It is a systematic approach that correctly solves the problem for the given constraints.

  • The logic is a direct translation of the problem's recursive definition, making it easier to verify correctness.

Cons

  • The O(n^3) time complexity might be too slow if the constraints on n were larger.

  • Requires O(n^2) space, which can be significant for larger n.

Solutions

class Solution {private  Boolean[][] f;private  int[] s;private  int m;public  boolean canSplitArray(List<Integer> nums, int m) {    int n = nums.size();    f = new Boolean[n][n];    s = new int[n + 1];    for (int i = 1; i <= n; ++i) {      s[i] = s[i - 1] + nums.get(i - 1);    }    this.m = m;    return dfs(0, n - 1);  }private  boolean dfs(int i, int j) {    if (i == j) {      return true;    }    if (f[i][j] != null) {      return f[i][j];    }    for (int k = i; k < j; ++k) {      boolean a = k == i || s[k + 1] - s[i] >= m;      boolean b = k == j - 1 || s[j + 1] - s[k + 1] >= m;      if (a && b && dfs(i, k) && dfs(k + 1, j)) {        return f[i][j] = true;      }    }    return f[i][j] = false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem