Check if it is Possible to Split Array - Practice Coding Problems

Check if it is Possible to Split Array - 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.

Input & Output

Example 1 — Basic Splittable Case

$ Input: nums = [2,1,2,6], m = 4

› Output: true

💡 Note: We can split [2,1,2,6] → [2,1,2] and [6]. Both are good: [2,1,2] has sum 5 ≥ 4, and [6] has length 1. Continue splitting [2,1,2] until all elements are separated.

Example 2 — Non-splittable Case

$ Input: nums = [2,1,1,1], m = 4

› Output: false

💡 Note: No two adjacent elements sum to 4 or more: 2+1=3, 1+1=2, 1+1=2. We cannot split any subarray of length > 2 while keeping both parts good.

Example 3 — Small Array

$ Input: nums = [1,1], m = 10

› Output: true

💡 Note: Arrays of length ≤ 2 can always be split into individual elements since single elements are always considered good.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 1000
1 ≤ m ≤ 200

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,2,6] with minimum sum threshold m=4

Strategy

Check if any adjacent pair sums ≥ m (enables splitting)

Result

Found 2+6=8 ≥ 4, so answer is true

Key Takeaway

🎯 Key Insight: We only need one adjacent pair summing ≥ m to enable complete splitting

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that we can split an array into individual elements if and only if we can find at least one pair of adjacent elements that sum to m or more, OR the array has length ≤ 2. The optimal greedy approach runs in O(n) time and O(1) space by simply checking adjacent pairs.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Observation	O(n)	O(1)	Check if any two adjacent elements sum to at least m, or array length ≤ 2
Dynamic Programming with Memoization	O(n³)	O(n²)	Cache results of subproblems to avoid redundant calculations
Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible ways to split the array recursively

Greedy Observation — Algorithm Steps

If array length ≤ 2, return true
Check if any two adjacent elements sum ≥ m
If yes, return true; otherwise false

Visualization

Tap to expand

Step-by-Step Walkthrough

Length Check

Arrays of length ≤ 2 always work

Adjacent Pairs

Check each adjacent pair sum

Decision

If any pair sum ≥ m, return true

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize, int m) {
    // Arrays of length <= 2 can always be split
    if (numsSize <= 2) {
        return true;
    }
    
    // Check if any two adjacent elements sum >= m
    for (int i = 0; i < numsSize - 1; i++) {
        if ((long long)nums[i] + nums[i + 1] >= m) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int m;
    scanf("%d", &m);
    
    bool result = solution(nums, numsSize, m);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to check adjacent pairs

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

247 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Observation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler