Approach Summary
Precompute total sum. For each split point i, left avg = prefixSum[i] / (i+1), right avg = (total - prefixSum[i]) / (n-i-1). Track minimum diff.
How to Recognize This Pattern
- Compare left and right averages at each split
- Prefix sum enables O(1) average computation per index
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Prefix Sum