Ways To Split Array Into Three Subarrays - Leetcode Solution

The problem statement asks us to split an integer array into three non-empty contiguous subarrays such that the sum of the elements in each subarray is equal. If such a split is possible, then we need to return a list of three integers: [i, j, k]. Here, [i, j, k] refer to the start indices of the three subarrays respectively.

Solution:

The approach to solving this problem involves the use of pre-processing the array to calculate prefix sums. Using prefix sums, we can easily find the sum of any subarray in O(1) time. Here is how we can solve this problem:

1. Calculate the prefix sum of the array: This can be done in O(n) time and space complexity. We can assign an additional array to store the prefix sums of the original array.

2. Calculate the suffix sum of the array: Similar to the previous step, we can assign an additional array to store the suffix sums of the original array.

3. Iterate through the array: Now, we will iterate through the array from the second index to the second last index. We will check if the prefix sum of the subarray [0, i] is equal to suffix sum of subarray [i+1, n-1]. If yes, we will move on to the next step. If not, we will continue the iteration.

4. Subarray calculations: Once we've found i, we will now iterate from i+1 to n-2. We will calculate the prefix sum of the subarray [i+1, j] and check if it is equal to suffix sum of the subarray [j+1, n-1]. If yes, we will store i and j as the indices of the first two subarrays and (j+1) and (n-1) as the indices of the third subarray and return this triplet.

5. Return [-1, -1, -1] if not possible: If we can't find any such triplet, we will return [-1, -1, -1].

Time Complexity: O(n) Space Complexity: O(n)

Here is the implementation of the above approach:

def threeEqualParts(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix_sum = [0]*n
    suffix_sum = [0]*n
    prefix_sum[0] = nums[0]
    suffix_sum[n-1] = nums[n-1]
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i-1] + nums[i]
        suffix_sum[n-i-1] = suffix_sum[n-i] + nums[n-i-1]
    for i in range(1, n-1):
        if prefix_sum[i-1] == suffix_sum[i]:
            for j in range(i+1, n-1):
                if prefix_sum[j-1] - prefix_sum[i] == suffix_sum[n-j-1]:
                    return [i, j]
    return [-1, -1]

The above code will solve the problem and return the answer as a list of integers.

1