| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Medium |
1543 |
Weekly Contest 357 Q2 |
|
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 to4 >= 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 tom. - 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 tom.
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 <= 1001 <= nums[i] <= 1001 <= m <= 200
First, we preprocess to get the prefix sum array
Next, we design a function true, otherwise return false.
The calculation process of the function
If true;
Otherwise, we enumerate the split point
- The subarray
$nums[i,..k]$ has only one element, or the sum of the elements of the subarray$nums[i,..k]$ is greater than or equal to$m$ ; - The subarray
$nums[k + 1,..j]$ has only one element, or the sum of the elements of the subarray$nums[k + 1,..j]$ is greater than or equal to$m$ ; - Both
$dfs(i, k)$ and$dfs(k + 1, j)$ aretrue.
To avoid repeated calculations, we use the method of memoization search, and use a two-dimensional array
The time complexity is
class Solution:
def canSplitArray(self, nums: List[int], m: int) -> bool:
@cache
def dfs(i: int, j: int) -> bool:
if i == j:
return True
for k in range(i, j):
a = k == i or s[k + 1] - s[i] >= m
b = k == j - 1 or s[j + 1] - s[k + 1] >= m
if a and b and dfs(i, k) and dfs(k + 1, j):
return True
return False
s = list(accumulate(nums, initial=0))
return dfs(0, len(nums) - 1)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;
}
}class Solution {
public:
bool canSplitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int f[n][n];
memset(f, -1, sizeof f);
function<bool(int, int)> dfs = [&](int i, int j) {
if (i == j) {
return true;
}
if (f[i][j] != -1) {
return f[i][j] == 1;
}
for (int k = i; k < j; ++k) {
bool a = k == i || s[k + 1] - s[i] >= m;
bool b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
if (a && b && dfs(i, k) && dfs(k + 1, j)) {
f[i][j] = 1;
return true;
}
}
f[i][j] = 0;
return false;
};
return dfs(0, n - 1);
}
};func canSplitArray(nums []int, m int) bool {
n := len(nums)
f := make([][]int, n)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
for i := range f {
f[i] = make([]int, n)
}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i == j {
return true
}
if f[i][j] != 0 {
return f[i][j] == 1
}
for k := i; k < j; k++ {
a := k == i || s[k+1]-s[i] >= m
b := k == j-1 || s[j+1]-s[k+1] >= m
if a && b && dfs(i, k) && dfs(k+1, j) {
f[i][j] = 1
return true
}
}
f[i][j] = -1
return false
}
return dfs(0, n-1)
}function canSplitArray(nums: number[], m: number): boolean {
const n = nums.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
const f: number[][] = Array(n)
.fill(0)
.map(() => Array(n).fill(-1));
const dfs = (i: number, j: number): boolean => {
if (i === j) {
return true;
}
if (f[i][j] !== -1) {
return f[i][j] === 1;
}
for (let k = i; k < j; ++k) {
const a = k === i || s[k + 1] - s[i] >= m;
const b = k === j - 1 || s[j + 1] - s[k + 1] >= m;
if (a && b && dfs(i, k) && dfs(k + 1, j)) {
f[i][j] = 1;
return true;
}
}
f[i][j] = 0;
return false;
};
return dfs(0, n - 1);
}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
}
}No matter how you operate, there will always be a length == 2 subarray left in the end. Since there are no negative numbers in the elements, as the split operation proceeds, the length and sum of the subarray will gradually decrease. The sum of other length > 2 subarrays must be larger than the sum of this subarray. Therefore, we only need to consider whether there is a length == 2 subarray with a sum greater than or equal to m.
📢 Note that when
nums.length <= 2, no operation is needed.
The time complexity is
function canSplitArray(nums: number[], m: number): boolean {
const n = nums.length;
if (n <= 2) {
return true;
}
for (let i = 1; i < n; i++) {
if (nums[i - 1] + nums[i] >= m) {
return true;
}
}
return false;
}