Sum of Variable Length Subarrays - Solution & Explanation

Problem Overview: You receive an integer array nums. For every index i, form a subarray that ends at i but whose starting index depends on the value nums[i]. Specifically, the subarray starts at max(0, i - nums[i]) and ends at i. The task is to compute the total sum of all these subarrays.

Approach 1: Direct Subarray Iteration (Brute Force) (Time: O(n²), Space: O(1))

The straightforward approach is to simulate exactly what the problem describes. For each index i, compute the starting index start = max(0, i - nums[i]). Then iterate from start to i and accumulate the values. Repeat this process for every index in the array and add each subarray's sum to the global result. This solution uses only basic iteration over the array and requires no additional data structures.

The downside is repeated work. Elements in the middle of the array may be summed multiple times across overlapping ranges. In the worst case, when many ranges are large, each iteration scans almost the entire prefix of the array, producing O(n²) time complexity. Space remains O(1) because only a few counters are used.

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

The key observation is that every required range sum can be answered instantly if prefix sums are available. Build a prefix array where prefix[i] stores the sum of the first i elements. With this structure, the sum of any range [l, r] becomes prefix[r + 1] - prefix[l]. This eliminates repeated summation and converts each subarray computation into constant time.

Iterate through the array once. For each index i, compute start = max(0, i - nums[i]). Use the prefix sum array to obtain the subarray sum instantly and add it to the result. Building the prefix array takes O(n), and processing all indices also takes O(n), giving a total time complexity of O(n). The extra prefix array requires O(n) space.

This approach works because range-sum queries become constant-time lookups after preprocessing. The pattern appears frequently in problems involving cumulative ranges or repeated interval queries on an array.

Recommended for interviews: Start by describing the brute-force iteration to show you understand the exact subarray definition. Then move to the prefix-sum optimization. Interviewers typically expect the O(n) prefix sum solution because it removes redundant work and demonstrates familiarity with range-sum techniques.