2811. Check if it is Possible to Split Array Solution

Q: Is Check if it is Possible to Split Array easy or hard?

The problem is labeled Medium because the correct greedy observation is not immediately obvious. Many candidates initially try recursion or dynamic programming to test all splits. Recognizing the adjacent pair property reduces the problem to a simple linear scan.

Q: Check if it is Possible to Split Array Python/Java solution

In Python or Java, the solution typically iterates through the array and checks adjacent pairs against the threshold m. The implementation is short because it only requires a loop and conditional checks, resulting in O(n) time complexity and constant extra space.

Q: How to solve Check if it is Possible to Split Array in O(n)?

Scan the array once and check whether any adjacent pair satisfies nums[i] + nums[i+1] >= m. If the array length is at most two, return true immediately. If a valid adjacent pair exists, repeated splits will always maintain a valid segment. This greedy rule guarantees correctness in linear time.

The 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.

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 to 4 >= 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 to m.
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 to m.

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 <= 100
1 <= nums[i] <= 100
1 <= m <= 200

Approach overview

Problem Overview: You are given an integer array and a minimum sum constraint m. The task is to determine whether the array can be repeatedly split into subarrays such that every resulting subarray of length greater than one has a sum at least m. The process continues until only single elements remain or no further valid splits exist.

Approach 1: Divide and Conquer (O(n^2) time, O(n) space)

This method recursively checks whether the array can be split at different indices while maintaining the sum constraint. For every possible partition point i, compute the sum of the left and right segments and verify that both satisfy the required condition. If both sides are valid, recursively attempt to split them further. Memoization helps avoid recomputing states for the same subarray range. This approach mirrors a classic recursive partition strategy commonly seen in dynamic programming problems where overlapping subproblems appear. It works well for explaining the problem structure but becomes expensive for large arrays because each split may trigger multiple recursive checks.

Approach 2: Heap Data Structure Approach (O(n log n) time, O(n) space)

A heap-based strategy tracks candidate segments that can still be split while maintaining the minimum sum requirement. You begin by treating the whole array as one segment and push it into a priority queue ordered by segment size or sum. At each step, remove a segment, attempt to divide it into two valid parts, and push the resulting segments back into the heap if they still meet the constraint. This technique simulates the splitting process while always working on the most promising segment first. The heap ensures efficient selection and reinsertion operations. While not the most optimal approach, it demonstrates how array segmentation problems can be modeled using priority queues.

Approach 3: Greedy Adjacent Pair Insight (O(n) time, O(1) space)

The key observation drastically simplifies the problem. If the array length is less than or equal to two, a valid split always exists. For larger arrays, check whether there exists at least one adjacent pair nums[i] + nums[i+1] >= m. If such a pair exists, the array can always be split step by step while preserving the sum constraint. That pair effectively acts as a safe pivot that keeps every intermediate segment valid during further splits. This greedy observation eliminates recursion and extra structures, making it the optimal strategy. Problems that reduce to local adjacency checks often fall under greedy algorithms.

Recommended for interviews: Start with the recursive divide-and-conquer explanation to demonstrate how you reason about valid partitions. Then move to the greedy observation. Interviewers typically expect the O(n) greedy solution because it shows you recognized the structural property of adjacent pairs rather than brute-forcing all partitions.

Approach 1: Divide and Conquer Approach

This approach uses the divide and conquer paradigm. The problem is broken down into smaller subproblems which are easier to solve, and their results are combined to give a solution to the original problem. For instance, in quicksort, a pivot is chosen and elements are partitioned around the pivot, solving each partition recursively.

Python

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
quicksort(arr, 0, len(arr) - 1)
print(arr)

Java

import java.util.Arrays;

public class QuickSort {
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

C++

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high);
int partition(std::vector<int>& arr, int low, int high);
void swap(int& a, int& b);

int main() {
    std::vector<int> arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    quickSort(arr, 0, arr.size() - 1);
    for (const auto& elem : arr) {
        std::cout << elem << " ";
    }
    return 0;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; 
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++; 
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void swap(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}

JavaScript

function quickSort(arr, low, high) {
    if (low < high) {
        let pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = (low - 1);
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

let arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(arr, 0, arr.length - 1);
console.log(arr.join(' '));

#include <stdio.h>

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void swap(int* a, int* b);

int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++; 
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

using System;

class QuickSort {
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp1 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp1;
        return i + 1;
    }

    public static void Main() {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(arr, 0, arr.Length - 1);
        Console.WriteLine(string.Join(" ", arr));
    }
}

Python's quicksort takes advantage of tuple unpacking for swap operations, resulting in a more concise and readable implementation.

Complexity

Time Complexity: O(n log n) on average, O(n^2) in the worst case. Space Complexity: O(log n) due to recursion stack.

Try this approach in the editor

Approach 2: Heap Data Structure Approach

This approach leverages the properties of heaps, such as the max heap or min heap, to solve problems efficiently. For instance, heapsort entails building a heap from the array and repeatedly extracting the maximum or minimum element while maintaining the heap invariant.

Python

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)


arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
heapSort(arr)
print("Sorted array is:", arr)

Java

import java.util.Arrays;

public class HeapSort {
    public void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    public void heapSort(int arr[]) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i=n-1; i>=0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public static void main(String args[]) {
        int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        HeapSort ob = new HeapSort();
        ob.heapSort(arr);
        System.out.println("Sorted array is: ");
        System.out.println(Arrays.toString(arr));
    }
}

C++

#include <iostream>
#include <vector>

void heapify(std::vector<int>& arr, int n, int i);
void heapSort(std::vector<int>& arr);

int main() {
    std::vector<int> arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    heapSort(arr);
    for (int i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);

        heapify(arr, i, 0);
    }
}

JavaScript

function heapify(arr, n, i) {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function heapSort(arr) {
    let n = arr.length;

    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
}

let arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
heapSort(arr);
console.log("Sorted array is:", arr);

#include <stdio.h>

void heapify(int arr[], int n, int i);
void heapSort(int arr[], int n);

int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array is \n");
    for (int i=0; i<n; ++i)
        printf("%d ",arr[i]);
    return 0;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=n-1; i>0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);
    }
}

using System;

class HeapSort {
    public void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public void heapSort(int[] arr) {
        int n = arr.Length;

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    static void Main(string[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        HeapSort hs = new HeapSort();
        hs.heapSort(arr);
        Console.WriteLine("Sorted array is:");
        foreach (int value in arr)
            Console.Write(value + " ");
    }
}

The Python heap sort implementation uses a simple tuple swap to manage elements and preserve the heap structure. It’s elegant, leveraging Python’s flexible data handling.

Complexity

Time Complexity: O(n log n) for all cases. Space Complexity: O(1) as it is an in-place sort.

Try this approach in the editor

Approach 3: Memoization Search

First, we preprocess to get the prefix sum array s, where s[i] represents the sum of the first i elements of the array nums.

Next, we design a function dfs(i, j), which represents whether there is a way to split the index range [i, j] of the array nums that meets the conditions. If it exists, return true, otherwise return false.

The calculation process of the function dfs(i, j) is as follows:

If i = j, then there is only one element, no need to split, return true;

Otherwise, we enumerate the split point k, where k \in [i, j], if the following conditions are met, then it can be split into two subarrays nums[i,.. k] and nums[k + 1,.. j]:

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) are true.

To avoid repeated calculations, we use the method of memoization search, and use a two-dimensional array f to record all the return values of dfs(i, j), where f[i][j] represents the return value of dfs(i, j).

The time complexity is O(n^3), and the space complexity is O(n^2), where n is the length of the array nums.

TypeScript

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);
}

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)
}

Rust

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
    }
}

Try this approach in the editor

Approach 4: Quick Thinking

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 O(n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

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;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Divide and Conquer Approach	Time Complexity: O(n log n) on average, O(n^2) in the worst case. Space Complexity: O(log n) due to recursion stack.
Heap Data Structure Approach	Time Complexity: O(n log n) for all cases. Space Complexity: O(1) as it is an in-place sort.
Memoization Search	–
Quick Thinking	–

Complexity analysis

Approach	Time	Space	When to Use
Divide and Conquer with Memoization	O(n^2)	O(n)	When explaining recursive partition logic or exploring all valid split points
Heap Data Structure Simulation	O(n log n)	O(n)	When modeling the process of repeatedly splitting segments using a priority queue
Greedy Adjacent Pair Check	O(n)	O(1)	Best solution for interviews and production; relies on the adjacent pair sum insight

Frequently asked questions

Is Check if it is Possible to Split Array easy or hard?

The problem is labeled Medium because the correct greedy observation is not immediately obvious. Many candidates initially try recursion or dynamic programming to test all splits. Recognizing the adjacent pair property reduces the problem to a simple linear scan.

Check if it is Possible to Split Array Python/Java solution

In Python or Java, the solution typically iterates through the array and checks adjacent pairs against the threshold m. The implementation is short because it only requires a loop and conditional checks, resulting in O(n) time complexity and constant extra space.

How to solve Check if it is Possible to Split Array in O(n)?

Scan the array once and check whether any adjacent pair satisfies nums[i] + nums[i+1] >= m. If the array length is at most two, return true immediately. If a valid adjacent pair exists, repeated splits will always maintain a valid segment. This greedy rule guarantees correctness in linear time.

What is the best approach for Check if it is Possible to Split Array?

The optimal approach is a greedy observation. If the array length is less than or equal to two, the answer is always true. Otherwise, check if any adjacent pair has a sum greater than or equal to m. If such a pair exists, the array can always be split while preserving the required sum constraint. This runs in O(n) time and O(1) space.

Is Check if it is Possible to Split Array asked at Google/Amazon/Meta?

Problems involving array partitioning, greedy observations, and dynamic programming patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that test recognition of structural array properties are particularly common in coding interviews.

What data structure is used in Check if it is Possible to Split Array?

The optimal solution does not require complex data structures and only uses simple array traversal. Some conceptual solutions model the splitting process using recursion, dynamic programming tables, or heaps to manage candidate segments.

What is the time complexity of Check if it is Possible to Split Array?

The optimal greedy solution runs in O(n) time because it scans the array once to check adjacent pair sums. The space complexity is O(1) since no extra data structures are required. Alternative approaches such as divide and conquer or heap simulation may take O(n^2) or O(n log n) time.

Check if it is Possible to Split Array solution and explanation

The problem

Approach overview

Approach 1: Divide and Conquer Approach

Approach 2: Heap Data Structure Approach

Approach 3: Memoization Search

Approach 4: Quick Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check if it is Possible to Split Array solution and explanation

The problem

Approach overview

Approach 1: Divide and Conquer Approach

Approach 2: Heap Data Structure Approach

Approach 3: Memoization Search

Approach 4: Quick Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems