Check if it is Possible to Split Array

Check if it is Possible to Split Array

What is this problem about?

The "Check if it is Possible to Split Array interview question" is a logical reduction challenge. You are given an array of integers and a threshold m. Your goal is to split the array into single-element subarrays through a series of steps. In each step, you can split a subarray of length at least 2 into two non-empty parts. A split is valid if the length of the resulting part is 1 OR its sum is greater than or equal to m.

Why is this asked in interviews?

Companies like Moneylion ask the "Check if it is Possible to Split Array coding problem" to evaluate a candidate's ability to simplify a problem using a Greedy observation. While it looks like it might require complex "Dynamic Programming," there is a mathematical shortcut that reduces the problem to a simple neighbor check. It tests whether you can find the "pivot" required to sustain the splitting process.

Algorithmic pattern used

This problem follows the Greedy neighbor check pattern. The core insight is: if you can find at least one pair of adjacent elements whose sum is $\geq m$, you can always "peel off" the other elements one by one until only that pair is left, and then split the pair (since parts of length 1 are always allowed).

1. Base Case: If the array length is $\leq 2$, it is always possible.
2. Iterative Step: Iterate through the array and check if any two adjacent elements arr[i] + arr[i+1] sum to m or more.
3. Result: If such a pair exists, return true.

Example explanation

Array: [2, 2, 1], $m = 4$.

1. Length is 3 ($> 2$).
2. Check adjacent sums:
   • 2 + 2 = 4 ($\geq m$).
3. Since we have a pair that sums to 4, we can split [2, 2, 1] into [2, 2] and [1]. [1] is valid (length 1). [2, 2] is valid (sum 4). Result: True. Array: [2, 1, 3], $m = 5$.

• 2+1=3, 1+3=4. No pair $\geq 5$. Result: False.

Common mistakes candidates make

• Complex DP: Attempting a $O(N^3)$ range-based DP which is much more complex than the greedy neighbor check.
• Ignoring Length 1 rule: Forgetting that a split is valid if the resulting part has length 1, even if its sum is small.
• Off-by-one: Mistakes in checking indices during the adjacent sum loop.

Interview preparation tip

Always look for the most "constrained" state in a problem. In this case, the last split before everything becomes length 1 must involve a subarray of length 2 that satisfies the sum condition. If such a "seed" exists, the whole array can be reduced.