LeetCode 2811: Check if it is Possible to Split Array Solution

Master LeetCode problem 2811 (Check if it is Possible to Split Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2811. Check if it is Possible to Split Array

Medium

Array Dynamic Programming Greedy

Problem Explanation

Explanation:

To solve this problem, we can use a recursive approach where we try to split the array at every possible index and check if both resulting subarrays are good arrays. If we can successfully split the array into n arrays of size 1, then we return true. Otherwise, we return false.

Algorithm:

Create a recursive function that takes the array, the current index to split, and the number of arrays to split into as parameters.
Base cases:
- If the number of arrays to split into is 0 and we have reached the end of the array, return true.
- If we have already used all the elements in the array or the number of arrays to split into is 0, return false.
For each index i from the current index to the end of the array:
- Split the array at index i into two subarrays.
- Check if both subarrays are good arrays.
- Recur with the updated parameters by reducing the number of arrays to split into by 1.
If none of the splits were successful, return false.

Time Complexity:

The time complexity of this approach is O(2^n) where n is the length of the input array nums.

Space Complexity:

The space complexity is O(n) for the recursive calls.

: :

Solution Code

class Solution {
    public boolean splitArray(int[] nums, int m) {
        return canSplit(nums, 0, m, nums.length);
    }
    
    private boolean canSplit(int[] nums, int startIndex, int m, int n) {
        if (n == 0 && startIndex == nums.length) {
            return true;
        }
        if (startIndex == nums.length || n == 0) {
            return false;
        }
        
        for (int i = startIndex; i < nums.length; i++) {
            int[] subarray1 = Arrays.copyOfRange(nums, startIndex, i + 1);
            int[] subarray2 = Arrays.copyOfRange(nums, i + 1, nums.length);
            if (isGoodArray(subarray1, m) && isGoodArray(subarray2, m)) {
                if (canSplit(nums, i + 1, m, n - 1)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean isGoodArray(int[] nums, int m) {
        if (nums.length == 1) {
            return true;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (sum >= m) {
                return true;
            }
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2811 (Check if it is Possible to Split Array)?

This page provides optimized solutions for LeetCode problem 2811 (Check if it is Possible to Split Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2811 (Check if it is Possible to Split Array)?

The time complexity for LeetCode 2811 (Check if it is Possible to Split Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2811 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2811 in Java, C++, or Python.

Back to LeetCode Solutions