A New Perspective on Subarray Sum: Beyond Brute Force and Prefix Arrays

As a developer passionate about problem solving, I often find joy in discovering elegant alternatives to well-known algorithms. Recently, I derived a fresh approach to calculating the sum of all subarrays of an array—one that goes beyond brute force and even traditional prefix sum techniques.
This blog walks you through the intuition, implementation, and mathematical reasoning behind my two-pass prefix-based solution.

💡 Problem Statement
Given an array arr[] of length n, compute the sum of all possible subarrays.
Example:
Input: arr = [1, 2, 3]
Output: 20
Explanation:
Subarrays: [1], [2], [3], [1,2], [2,3], [1,2,3]
Sum = 1 + 2 + 3 + (1+2) + (2+3) + (1+2+3) = 20

🚫 Traditional Approaches
Most solutions fall into one of these categories:

• Brute Force (O(n²)): Iterate over all subarrays and sum them individually.
• Prefix Sum Array: Precompute prefix sums and use them to calculate subarray sums.
• Contribution Technique: Use mathematical formulas to compute how many times each element appears in subarrays. While effective, these methods either lack elegance or require additional space or combinatorial reasoning.

✅ My Two-Pass Prefix-Based Solution
Here’s the code:
`

`
public int subarraySum(int[] arr) {
int prefix = 0, prefixsum = 0, ans = 0;

// First pass: compute total of all prefix sums
for (int i = 0; i < arr.length; i++) {
    prefix += arr[i];
    prefixsum += prefix;
}

int totalpresum = prefixsum;
prefixsum = 0;
prefix = 0;

// Second pass: subtract scaled prefix to isolate contributions
for (int i = 0; i < arr.length; i++) {
    ans += (totalpresum - prefixsum - (prefix * (arr.length - i)));
    prefix += arr[i];
    prefixsum += prefix;
}

return ans;

}
`
`



🧠 Intuition Behind the Formula
Let’s break it down:
🔹 First Pass
We calculate the sum of all prefix sums. This gives us a cumulative view of how elements build up across subarrays.
🔹 Second Pass
We subtract overlapping contributions using:
ans += totalpresum - prefixsum - (prefix * (n - i))

• totalpresum: Total of all prefix sums.
• prefixsum: Sum of prefixes up to index i.
• prefix * (n - i): Adjusts for how many subarrays the current prefix affects. This isolates the net contribution of each element across all subarrays.

📊 Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) No extra arrays, no nested loops—just pure arithmetic.

🧪 Example Walkthrough
Let’s walk through arr = [1, 2, 3].
First Pass:

• Subarrays and their sums:
• [1] → 1
• [2] → 2
• [3] → 3
• [1, 2] → 3
• [2, 3] → 5
• [1, 2, 3] → 6 🔢 Total prefix Sum = 1 + 2 + 3 + 3 + 5 + 6 = 20 Second Pass: We adjust each prefix’s contribution using the formula, and the final answer becomes 20. ans += totalpresum - prefixsum - (prefix * (n - i)) 🌟 Why This Matters This approach isn’t just efficient—it’s original. I couldn’t find this exact method documented on any major platform. It’s a great example of how deep thinking and experimentation can lead to new insights in algorithm design.

✍️ Final Thoughts
If you found this technique interesting, I’d love to hear your thoughts or see how you might extend it to related problems (like sum of all submatrices in 2D arrays).
You can connect with me on LinkedIn(Satyam Pruthi) or leave a comment below. Let’s keep learning and building together!