We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if it is Possible to Split Array

Number: 2916

Difficulty: Medium

Paid? No

Companies: MoneyLion

Problem Description

You are given an array nums of length n and an integer m. You can perform split operations on any array (either the original or one produced by a previous split) that has a length of at least two. In one step you choose an index to split the array into two contiguous parts. However, you are only allowed to make a split if both resulting subarrays are considered "good." An array is called good if:

  • Its length is one, or
  • The sum of its elements is greater than or equal to m.

Return true if it is possible to eventually split the original array into n arrays each of size one, following the rule. Otherwise, return false.

Key Insights

  • The split operation is only allowed if each of the two contiguous subarrays is "good." For subarrays of length >1, the sum must be at least m.
  • Arrays of length one are automatically good.
  • The problem can be solved recursively by checking every possible split point and ensuring that both the immediate subarrays satisfy the "good" condition and can themselves be further split (if their length exceeds one) into single-element arrays.
  • Dynamic programming (memoization) can be used to avoid re-computation since the input size is small (n ≤ 100).

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case because for every subarray (O(n^2)) we may try O(n) different split points. Space Complexity: O(n^2) due to the memoization table and prefix sum array.

Solution

We use a recursive strategy with memoization (top-down dynamic programming). First, we precompute a prefix sum array to get the sum of any contiguous subarray in O(1) time. The function dp(i, j) determines if the subarray nums[i..j] can be split (if needed) into units (arrays of length one) by repeatedly performing valid splits.

For a subarray from index i to j:

  • If i equals j, it is a single element and is trivially good.
  • Otherwise, try every possible split position k (from i to j-1) and check:
    • The left segment (nums[i..k]) is good if either its length is 1 or its sum is at least m.
    • The right segment (nums[k+1..j]) is good if either its length is 1 or its sum is at least m.
  • If both segments are immediately good and can be further split (if necessary) into single elements (i.e. dp(i, k) and dp(k+1, j) are both true), then the subarray nums[i..j] is splittable.
  • Use memoization to store and reuse results for each (i, j) subarray to avoid repeated computations. This approach ensures that each valid split meets the rules and, eventually, the entire array is broken down into single elements.

Code Solutions

# Python solution with detailed comments

class Solution:
    def canSplitArray(self, nums, m):
        n = len(nums)
        # Precompute prefix sums: prefix[i] is the sum of nums[0..i-1]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        
        # Helper to compute sum of subarray from index i to j (inclusive)
        def subarray_sum(i, j):
            return prefix[j+1] - prefix[i]
        
        # Memoization dictionary for dp results: key -> (i, j)
        memo = {}
        
        def dp(i, j):
            # Base case: single element is always splittable (and good)
            if i == j:
                return True
            if (i, j) in memo:
                return memo[(i, j)]
            
            # Try every possible split between indices i and j
            for k in range(i, j):
                left_length = k - i + 1
                right_length = j - k
                
                # Check if left segment is good:
                # If it is a single element, it is automatically good.
                # Otherwise, check if its sum is at least m.
                if left_length == 1 or subarray_sum(i, k) >= m:
                    left_good = True
                else:
                    left_good = False
                
                # Check if right segment is good:
                if right_length == 1 or subarray_sum(k+1, j) >= m:
                    right_good = True
                else:
                    right_good = False
                
                # If both segments are immediately good and they can be fully split
                # into single elements (if necessary), then this subarray is splittable.
                if left_good and right_good and dp(i, k) and dp(k+1, j):
                    memo[(i, j)] = True
                    return True
            memo[(i, j)] = False
            return False
        
        return dp(0, n-1)

# Example usage:
# sol = Solution()
# print(sol.canSplitArray([2, 2, 1], 4))  # Expected output: True
← Back to All Questions