Date: 2026-06-06
Time: 18:28
This file solves LeetCode 1013. It determines whether an integer array can be split into three contiguous, non-empty subarrays that each sum to the same value. It's a single-class, single-method solution following the standard LeetCode Solution class convention used across this repository.
Solution.canThreePartsEqualSum(self, arr: List[int]) -> bool
The only method. Contract: given a list of integers, return True iff there exist indices i < j such that arr[0:i+1], arr[i+1:j+1], and arr[j+1:] all have the same sum.
Prefix-sum with early exit. Rather than materializing a prefix-sum array, the code maintains a running sum and checks whether it has hit target, then 2 * target. This is O(n) time, O(1) space — a greedy single-pass approach.
The key insight: if the total is S and divisible by 3, then target = S/3. The code scans left-to-right accumulating runningsum. When runningsum == target, that's the end of part 1. When runningsum == 2 * target, that's the end of part 2, and everything remaining is part 3. The check runningsum == target * (parts_found + 1) elegantly unifies both boundary checks into one expression.
Imports: Only typing.List — no external or project dependencies.
Imported by: partition-array-into-three-parts-with-equal-sum/test_solution.py (the "Imported By" list in the prompt is the full test suite across the repo, which all share a common test runner pattern, not actual imports of this specific module).
1. Compute total = sum(arr). If not divisible by 3, return False immediately.
2. Set target = total // 3. Initialize runningsum = 0, partsfound = 0.
3. Iterate indices 0 through len(arr) - 2 (inclusive). The upper bound ensures the third partition is non-empty.
4. Accumulate runningsum += arr[i]. When runningsum equals target * (partsfound + 1), increment partsfound.
5. If parts_found reaches 2, return True — the remaining elements form the third part.
6. If the loop completes without finding 2 partition boundaries, return False.
len(arr) - 2 (i.e., range(len(arr) - 1)), guaranteeing at least one element remains for the third partition after finding two boundaries.runningsum == target * (partsfound + 1) only fires in order — part 1's boundary at target, then part 2's boundary at 2 * target. This works because parts_found increments sequentially.None. The method assumes valid input per the LeetCode contract (non-empty array of integers). No exceptions are raised or caught.
When total == 0, target == 0. The cumulative check still works: it finds the first prefix summing to 0 (part 1), then the first prefix summing to 0 again (part 2). The remaining elements must also sum to 0 since the total is 0. The range(len(arr) - 1) bound still correctly ensures part 3 is non-empty.