---
Difficulty: Medium
Source: 160 Days of Problem Solving  (BONUS PROBLEMS 🎁)
Tags:
  - prefix -sum
  - Arrays
---

# 🚀 _1. Split array in three equal sum subarrays_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/array-bonus-problems/problem/split-array-in-three-equal-sum-subarrays)

## 💡 **Problem Description:**

Given an array `arr[]`, determine if `arr` can be split into three consecutive parts such that the sum of each part is equal. If possible, return any index pair `(i, j)` in an array such that:

```
sum(arr[0..i]) = sum(arr[i+1..j]) = sum(arr[j+1..n-1])
```

Otherwise, return an array `{-1, -1}`.

**Note:** Since multiple answers are possible, return any of them. The driver code will print `true` if it is correct, otherwise, it will print `false`.

## 🔍 **Example Walkthrough:**

**Input:**

```
arr[] = [1, 3, 4, 0, 4]
```

\*\*Output:

```
true
```

**Explanation:**
`[1, 2]` is valid pair as sum of subarray arr`[0..1]` is equal to sum of subarray arr`[2..3]` and also to sum of subarray arr`[4..4]`. The sum is 4, so driver code prints true.

**Input:**

```
arr[] = [2, 3, 4]
```

**Output:**

```
false
```

**Explanation:**
No three subarrays exist which have equal sum.

**Input:**

```
arr[] = [0, 1, 1]
```

**Output:**

```
false
```

### Constraints:

- $`3 ≤ arr.size() ≤ 10^6`$
- $`0 ≤ arr[i] ≤ 10^6`$

## 🎯 **My Approach:**

### Step-by-Step:

1. **Calculate the Total Sum:**  
   Compute the total sum of the array. If this sum is not divisible by `3`, return `{-1, -1}` because splitting is impossible.

2. **Determine the Target Sum:**  
   Divide the total sum by `3` to get the sum each subarray should equal.

3. **Find the Splitting Points:**  
   Traverse the array to find indices `i` and `j` where:

   - Sum of `arr[0..i]` equals the target sum (first split).
   - Sum of `arr[i+1..j]` also equals the target sum (second split).

4. **Validate:**  
   If both splits are found, return `[i, j]`; otherwise, return `{-1, -1}`.

## 🕒 **Time and Auxiliary Space Complexity**

- **Expected Time Complexity:** O(n), where `n` is the size of the array. The algorithm involves a single pass through the array to compute the total sum, followed by another pass to find the splitting points.
- **Expected Auxiliary Space Complexity:** O(1), as the solution uses only a constant amount of additional space.

## 📝 **Solution Code**

## Code (Cpp)

```cpp
class Solution {
public:
    vector<int> findSplit(vector<int>& arr) {
        int total_sum = accumulate(arr.begin(), arr.end(), 0);
        if (total_sum % 3 != 0) {
            return {-1, -1};
        }
        int target = total_sum / 3;
        int current_sum = 0;
        int first_split = -1, second_split = -1;
        for (int i = 0; i < arr.size(); i++) {
            current_sum += arr[i];
            if (current_sum == target) {
                first_split = i;
                break;
            }
        }
        if (first_split == -1) {
            return {-1, -1};
        }
        current_sum = 0;
        for (int j = first_split + 1; j < arr.size(); j++) {
            current_sum += arr[j];
            if (current_sum == target) {
                second_split = j;
                break;
            }
        }
        if (second_split != -1) {
            return {first_split, second_split};
        } else {
            return {-1, -1};
        }
    }
};
```

## Code (Java)

```java
class Solution {

    public List<Integer> findSplit(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }

        if (totalSum % 3 != 0) {
            return Arrays.asList(-1, -1);
        }

        int target = totalSum / 3;
        int currentSum = 0;
        int firstSplit = -1, secondSplit = -1;

        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            if (currentSum == target) {
                firstSplit = i;
                break;
            }
        }
        if (firstSplit == -1) {
            return Arrays.asList(-1, -1);
        }

        currentSum = 0;

        for (int i = firstSplit + 1; i < arr.length; i++) {
            currentSum += arr[i];
            if (currentSum == target) {
                secondSplit = i;
                break;
            }
        }
        if (secondSplit != -1) {
            return Arrays.asList(firstSplit, secondSplit);
        }
        return Arrays.asList(-1, -1);
    }
}
```

## Code (Python)

```python
class Solution:

    def findSplit(self, arr):
        total_sum = sum(arr)
        if total_sum % 3 != 0:
            return [-1, -1]

        target = total_sum // 3
        current_sum = 0
        first_split = -1
        second_split = -1

        for i in range(len(arr)):
            current_sum += arr[i]
            if current_sum == target:
                first_split = i
                break

        if first_split == -1:
            return [-1, -1]

        current_sum = 0

        for i in range(first_split + 1, len(arr)):
            current_sum += arr[i]
            if current_sum == target:
                second_split = i
                break

        if second_split != -1:
            return [first_split, second_split]
        return [-1, -1]

```

## 🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>