Problem

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:

  • 0 < i, i + 1 < j, j + 1 < k < n - 1
  • The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.

A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Example 2:

1
2

Input: nums = [1,2,1,2,1,2,1,2]
Output: false

Constraints:

  • n == nums.length
  • 1 <= n <= 2000
  • -10^6 <= nums[i] <= 10^6

Solution

Method 1 – Prefix Sum and Hash Set

Intuition

We want to find three split points (i, j, k) such that the sums of four subarrays are equal. By using prefix sums, we can efficiently compute subarray sums and use a hash set to track possible sums for the first two splits, then check for a matching sum in the third split.

Approach

  1. Compute the prefix sum array for nums.
  2. For each possible j (from 3 to n-4), try all possible i (from 1 to j-2) and store valid sums in a set.
  3. For each possible k (from j+2 to n-2), check if the sum for the third split matches any sum in the set.
  4. If a match is found, return true.
  5. If no match is found after all iterations, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n+1, 0);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        for (int j = 3; j < n-3; ++j) {
            unordered_set<int> s;
            for (int i = 1; i < j-1; ++i) {
                int sum1 = pre[i];
                int sum2 = pre[j] - pre[i+1];
                if (sum1 == sum2) s.insert(sum1);
            }
            for (int k = j+2; k < n-1; ++k) {
                int sum3 = pre[k] - pre[j+1];
                int sum4 = pre[n] - pre[k+1];
                if (sum3 == sum4 && s.count(sum3)) return true;
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func splitArray(nums []int) bool {
    n := len(nums)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + nums[i]
    }
    for j := 3; j < n-3; j++ {
        s := map[int]struct{}{}
        for i := 1; i < j-1; i++ {
            sum1 := pre[i]
            sum2 := pre[j] - pre[i+1]
            if sum1 == sum2 {
                s[sum1] = struct{}{}
            }
        }
        for k := j+2; k < n-1; k++ {
            sum3 := pre[k] - pre[j+1]
            sum4 := pre[n] - pre[k+1]
            if sum3 == sum4 {
                if _, ok := s[sum3]; ok {
                    return true
                }
            }
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean splitArray(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        for (int j = 3; j < n-3; ++j) {
            Set<Integer> s = new HashSet<>();
            for (int i = 1; i < j-1; ++i) {
                int sum1 = pre[i];
                int sum2 = pre[j] - pre[i+1];
                if (sum1 == sum2) s.add(sum1);
            }
            for (int k = j+2; k < n-1; ++k) {
                int sum3 = pre[k] - pre[j+1];
                int sum4 = pre[n] - pre[k+1];
                if (sum3 == sum4 && s.contains(sum3)) return true;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun splitArray(nums: IntArray): Boolean {
        val n = nums.size
        val pre = IntArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]
        for (j in 3 until n-3) {
            val s = mutableSetOf<Int>()
            for (i in 1 until j-1) {
                val sum1 = pre[i]
                val sum2 = pre[j] - pre[i+1]
                if (sum1 == sum2) s.add(sum1)
            }
            for (k in j+2 until n-1) {
                val sum3 = pre[k] - pre[j+1]
                val sum4 = pre[n] - pre[k+1]
                if (sum3 == sum4 && s.contains(sum3)) return true
            }
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def splitArray(nums: list[int]) -> bool:
    n = len(nums)
    pre = [0] * (n+1)
    for i in range(n):
        pre[i+1] = pre[i] + nums[i]
    for j in range(3, n-3):
        s = set()
        for i in range(1, j-1):
            sum1 = pre[i]
            sum2 = pre[j] - pre[i+1]
            if sum1 == sum2:
                s.add(sum1)
        for k in range(j+2, n-1):
            sum3 = pre[k] - pre[j+1]
            sum4 = pre[n] - pre[k+1]
            if sum3 == sum4 and sum3 in s:
                return True
    return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn split_array(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut pre = vec![0; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] + nums[i];
        }
        for j in 3..n-3 {
            let mut s = std::collections::HashSet::new();
            for i in 1..j-1 {
                let sum1 = pre[i];
                let sum2 = pre[j] - pre[i+1];
                if sum1 == sum2 {
                    s.insert(sum1);
                }
            }
            for k in j+2..n-1 {
                let sum3 = pre[k] - pre[j+1];
                let sum4 = pre[n] - pre[k+1];
                if sum3 == sum4 && s.contains(&sum3) {
                    return true;
                }
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    splitArray(nums: number[]): boolean {
        const n = nums.length;
        const pre = Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        for (let j = 3; j < n-3; ++j) {
            const s = new Set<number>();
            for (let i = 1; i < j-1; ++i) {
                const sum1 = pre[i];
                const sum2 = pre[j] - pre[i+1];
                if (sum1 === sum2) s.add(sum1);
            }
            for (let k = j+2; k < n-1; ++k) {
                const sum3 = pre[k] - pre[j+1];
                const sum4 = pre[n] - pre[k+1];
                if (sum3 === sum4 && s.has(sum3)) return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) – Two nested loops for i and k for each j.
  • 🧺 Space complexity: O(n) – Prefix sum array and hash set for sums.