Split array in three equal sum subarrays

Given anarray, 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: Driver code will print true if arr can be split into three equal sum subarrays, otherwise, it is false.

Examples :

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. 

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⁶
0 ≤ arr[i] ≤ 10⁶

Approach 01:

#include <vector>
#include <numeric>
using namespace std;

class Solution {
public:
    vector<int> findSplit(vector<int>& arr) {
        int arraySize = arr.size();
        long long totalSum = accumulate(arr.begin(), arr.end(), 0ll);
        
        // Check if the array sum is divisible by 3
        if (totalSum % 3 != 0) 
            return {-1, -1};
        
        int splitPointStart = -1;
        long long firstSegmentSum = totalSum / 3;
        
        // Find the starting point of the split
        for (int i = 0; i < arraySize; ++i) {
            firstSegmentSum -= arr[i];
            if (firstSegmentSum <= 0) {
                splitPointStart = i;
                break;
            }
        }
        
        int splitPointEnd = -1;
        long long lastSegmentSum = totalSum / 3;
        
        // Find the ending point of the split
        for (int i = arraySize - 1; i >= 0; --i) {
            lastSegmentSum -= arr[i];
            if (lastSegmentSum <= 0) {
                splitPointEnd = i;
                break;
            }
        }

        // Check if the split is valid
        if (firstSegmentSum < 0 || lastSegmentSum < 0 || splitPointEnd - splitPointStart < 2)
            return {-1, -1};
        
        return {splitPointStart, splitPointEnd - 1};
    }
};

from typing import List
from itertools import accumulate

class Solution:
    def findSplit(self, arr):
        arraySize = len(arr)
        totalSum = sum(arr)
        
        # Check if the array sum is divisible by 3
        if totalSum % 3 != 0:
            return [-1, -1]
        
        splitPointStart = -1
        firstSegmentSum = totalSum // 3
        
        # Find the starting point of the split
        for i in range(arraySize):
            firstSegmentSum -= arr[i]
            if firstSegmentSum <= 0:
                splitPointStart = i
                break
        
        splitPointEnd = -1
        lastSegmentSum = totalSum // 3
        
        # Find the ending point of the split
        for i in range(arraySize - 1, -1, -1):
            lastSegmentSum -= arr[i]
            if lastSegmentSum <= 0:
                splitPointEnd = i
                break

        # Check if the split is valid
        if firstSegmentSum < 0 or lastSegmentSum < 0 or splitPointEnd - splitPointStart < 2:
            return [-1, -1]
        
        return [splitPointStart, splitPointEnd - 1]

Time Complexity

• Array Sum Calculation:

  The function calculates the total sum of the array using accumulate, which takes \( O(N) \) time, where \( N \) is the size of the arr array.

• Finding Split Points:

  The function has two separate loops to find the start and end points of the split. Each loop iterates through the array once, making this part of the function also \( O(N) \).

• Overall Time Complexity:

  The overall time complexity is \( O(N) \) because both the sum calculation and the split point searches are \( O(N) \) operations.

Space Complexity

• Auxiliary Variables:

  The function uses a constant amount of additional space for variables such as totalSum, firstSegmentSum, lastSegmentSum, splitPointStart, and splitPointEnd, all of which have \( O(1) \) space complexity.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as only a fixed amount of extra space is required regardless of the input size.