Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Greedy Check for Any Good Split

Intuition

If there exists any split of the array into two non-empty parts such that both parts are good (i.e., have sum ≥ m or length 1), then we can always recursively split further. So, we just need to check if there is any split point where both left and right subarrays are good.

Approach

  1. If the array length is 1, return true.
  2. For every split point i (1 ≤ i < n):
    • Compute the sum of the left part (nums[0:i]) and the right part (nums[i:]).
    • If either part has length 1 or sum ≥ m, mark it as good.
    • If both parts are good, return true.
  3. If no such split exists, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; ++i) {
            if (nums[i-1] + nums[i] >= m) return true;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func canSplitArray(nums []int, m int) bool {
    n := len(nums)
    if n <= 2 {
        return true
    }
    for i := 1; i < n; i++ {
        if nums[i-1]+nums[i] >= m {
            return true
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public boolean canSplitArray(int[] nums, int m) {
        int n = nums.length;
        if (n <= 2) return true;
        for (int i = 1; i < n; ++i) {
            if (nums[i-1] + nums[i] >= m) return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun canSplitArray(nums: IntArray, m: Int): Boolean {
        if (nums.size <= 2) return true
        for (i in 1 until nums.size) {
            if (nums[i-1] + nums[i] >= m) return true
        }
        return false
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def canSplitArray(self, nums: list[int], m: int) -> bool:
        n = len(nums)
        if n <= 2:
            return True
        for i in range(1, n):
            if nums[i-1] + nums[i] >= m:
                return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn can_split_array(nums: Vec<i32>, m: i32) -> bool {
        let n = nums.len();
        if n <= 2 { return true; }
        for i in 1..n {
            if nums[i-1] + nums[i] >= m {
                return true;
            }
        }
        false
    }
}

Complexity

  • ⏰ Time complexity: O(N), where N is the length of the array (since we can precompute prefix sums).
  • 🧺 Space complexity: O(1)