1. Split array in three equal sum subarrays.md

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

🚀 1. Split array in three equal sum subarrays 🧠

The problem can be found at the following link: Problem Link

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

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)

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)

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. Let’s make this learning journey more collaborative!

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

---

📍Visitor Count