Sum of Consecutive Subarrays - Video Solutions

Problem Overview: Given an array, compute the total sum of every possible consecutive subarray. Each contiguous segment contributes its own sum, and the final answer is the accumulation of all those values.

Approach 1: Brute Force Enumeration (Time: O(n^3), Space: O(1))

The most direct method enumerates every possible subarray and computes its sum independently. Use two loops to choose the start and end index, then a third loop to add elements between them. This approach clearly demonstrates how subarrays are formed but quickly becomes impractical because every subarray requires a full traversal to compute its sum. With n elements, there are O(n^2) subarrays and each may take O(n) work, leading to O(n^3) time complexity and constant O(1) space.

Approach 2: Prefix Sum Optimization (Time: O(n^2), Space: O(n))

Precompute a prefix sum array where prefix[i] stores the sum of elements from index 0 to i-1. The sum of any subarray [l, r] can then be calculated in constant time using prefix[r+1] - prefix[l]. Iterate over all possible start and end indices and accumulate their sums using this lookup. The prefix array removes the inner summation loop, reducing the runtime to O(n^2) while using O(n) additional memory. This approach is common in array problems where repeated range-sum queries appear.

Approach 3: Recurrence / Dynamic Contribution (Time: O(n), Space: O(1))

The optimal solution observes how often each element contributes to subarray sums. For an index i, the element nums[i] appears in exactly (i + 1) * (n - i) different subarrays. Instead of generating subarrays explicitly, accumulate the contribution directly. Another equivalent view uses a recurrence: maintain the sum of all subarrays ending at the current index. If endSum represents the total sum of subarrays ending at i-1, then for index i the new value becomes endSum = endSum + nums[i] * (i + 1). Add endSum to the global result each step. This dynamic formulation runs in O(n) time and constant O(1) space, making it ideal for large inputs and aligning with patterns from dynamic programming and cumulative array contributions.

Recommended for interviews: Start with the brute force idea to show you understand how consecutive subarrays are generated. Then transition to the recurrence-based contribution method. Interviewers expect the O(n) dynamic accumulation because it demonstrates pattern recognition with prefix-style reasoning and efficient iteration over the array.