Solution Explanation: Partition Array Into Three Parts With Equal Sum

This problem asks whether an array can be partitioned into three non-empty subarrays with equal sums. The solution leverages a greedy approach combined with efficient summation.

Algorithm:

1. Sum Check: First, calculate the total sum of the array. If the sum is not divisible by 3, it's impossible to partition the array into three equal-sum parts, so return false.

2. Target Sum: Divide the total sum by 3 to get the target sum (s) for each of the three partitions.

3. Greedy Traversal: Iterate through the array, keeping track of a running sum (t).

   • If the running sum (t) equals the target sum (s), increment a counter (cnt) representing the number of partitions found and reset the running sum (t) to 0.

4. Partition Check: After iterating, check if the cnt is greater than or equal to 3. If it is, it means we found at least three partitions with the target sum, indicating a successful partition; otherwise, return false.

Time Complexity Analysis:

The algorithm involves a single pass through the array, making its time complexity O(n), where n is the length of the input array.

Space Complexity Analysis:

The algorithm uses only a few variables to store the sum, target sum, counter, and running sum. The space used is constant regardless of the input size, making the space complexity O(1).

Code Implementation (Python):

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total_sum = sum(arr)
        if total_sum % 3 != 0:
            return False  # Not divisible by 3, impossible to partition
 
        target_sum = total_sum // 3
        count = 0
        current_sum = 0
        for num in arr:
            current_sum += num
            if current_sum == target_sum:
                count += 1
                current_sum = 0
 
        return count >= 3

Code Implementation (Java):

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = Arrays.stream(arr).sum();
        if (totalSum % 3 != 0) {
            return false;
        }
 
        int targetSum = totalSum / 3;
        int count = 0;
        int currentSum = 0;
        for (int num : arr) {
            currentSum += num;
            if (currentSum == targetSum) {
                count++;
                currentSum = 0;
            }
        }
 
        return count >= 3;
    }
}

Code Implementation (C++):

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int totalSum = accumulate(arr.begin(), arr.end(), 0);
        if (totalSum % 3 != 0) {
            return false;
        }
 
        int targetSum = totalSum / 3;
        int count = 0;
        int currentSum = 0;
        for (int num : arr) {
            currentSum += num;
            if (currentSum == targetSum) {
                count++;
                currentSum = 0;
            }
        }
 
        return count >= 3;
    }
};

The code in other languages (Go, TypeScript, Rust) follows a similar structure, adapting the syntax and data structures according to the language's conventions. The core logic remains consistent across all implementations.