Sum of Variable Length Subarrays solution and explanation
Google
6 more videos on this problem
Leetcode | 3427 Sum of Variable Length Subarrays | Java | Simple Approach | WeeklyCakot Coding · 10:00 · 806 views
3427. Sum of Variable Length Subarrays (Leetcode Easy)Programming Live with Larry · 3:17 · 516 views
leetcode 3427 | Sum of Variable Length Subarrays | Prefix SumCoding Idiots · 13:54 · 217 views
3427. Sum of Variable Length Subarraysbab lobko (Short and straight to the point) · 3:38 · 146 views
LeetCode 3427 Sum of Variable Length Subarrays [easy] [quicksolve]LeetCoders United · 6:43 · 110 views
leetcode 3427. Sum of Variable Length SubarraysPixelBurst_coder · 2:27 · 93 views
Leetcode easy problem 3427. Sum of Variable Length Subarrays | devops python practiceADevOpsEngineer · 1:55 · 23 views
The problem
You are given an integer array nums of size n. For each index i where 0 <= i < n, define a subarray nums[start ... i] where start = max(0, i - nums[i]).
Return the total sum of all elements from the subarray defined for each index in the array.
Example 1:
Input: nums = [2,3,1]
Output: 11
Explanation:
| i | Subarray | Sum |
|---|---|---|
| 0 | nums[0] = [2] |
2 |
| 1 | nums[0 ... 1] = [2, 3] |
5 |
| 2 | nums[1 ... 2] = [3, 1] |
4 |
| Total Sum | 11 |
The total sum is 11. Hence, 11 is the output.
Example 2:
Input: nums = [3,1,1,2]
Output: 13
Explanation:
| i | Subarray | Sum |
|---|---|---|
| 0 | nums[0] = [3] |
3 |
| 1 | nums[0 ... 1] = [3, 1] |
4 |
| 2 | nums[1 ... 2] = [1, 1] |
2 |
| 3 | nums[1 ... 3] = [1, 1, 2] |
4 |
| Total Sum | 13 |
The total sum is 13. Hence, 13 is the output.
Constraints:
1 <= n == nums.length <= 1001 <= nums[i] <= 1000
Approach overview
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.
Solution
class Solution:
def subarraySum(self, nums: List[int]) -> int:
s = list(accumulate(nums, initial=0))
return sum(s[i + 1] - s[max(0, i - x)] for i, x in enumerate(nums))class Solution {
public int subarraySum(int[] nums) {
int n = nums.length;
int[] s = new int[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += s[i + 1] - s[Math.max(0, i - nums[i])];
}
return ans;
}
}class Solution {
public:
int subarraySum(vector<int>& nums) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += s[i + 1] - s[max(0, i - nums[i])];
}
return ans;
}
};function subarraySum(nums: number[]): number {
const n = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += s[i + 1] - s[Math.max(0, i - nums[i])];
}
return ans;
}func subarraySum(nums []int) (ans int) {
s := make([]int, len(nums)+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
for i, x := range nums {
ans += s[i+1] - s[max(0, i-x)]
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Subarray Iteration (Brute Force) | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum Optimization | O(n) | O(n) | General case and expected interview solution for efficient range sum queries |
Frequently asked questions
Is Sum of Variable Length Subarrays easy or hard?
Sum of Variable Length Subarrays is categorized as an Easy problem. The main idea is recognizing that each index defines a range ending at i. Using a prefix sum array turns repeated summations into constant-time queries, making the implementation straightforward.
Sum of Variable Length Subarrays Python/Java solution
Most implementations follow the same structure across languages: build a prefix sum array, iterate through the indices, compute start = max(0, i - nums[i]), and accumulate prefix[i + 1] - prefix[start]. The logic is identical in Python, Java, C++, Go, and TypeScript with only syntax differences.
How to solve Sum of Variable Length Subarrays in O(n)?
Construct a prefix sum array where prefix[i] stores the sum of elements before index i. For each index i, compute start = max(0, i - nums[i]). The subarray sum from start to i equals prefix[i + 1] - prefix[start]. Add this to the total while scanning the array once, achieving O(n) time complexity.
What is the best approach for Sum of Variable Length Subarrays?
The prefix sum approach is the most efficient method. Precompute cumulative sums so any subarray sum can be calculated in O(1) time. Then iterate through the array, determine the start index max(0, i - nums[i]), and compute the range sum using prefix values. This results in O(n) time and O(n) space.
Is Sum of Variable Length Subarrays asked at Google/Amazon/Meta?
Problems based on prefix sums and dynamic range calculations appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the underlying pattern of converting repeated subarray sums into prefix-sum queries is a common interview technique.
What data structure is used in Sum of Variable Length Subarrays?
The main structure used is a prefix sum array. It stores cumulative sums so that any range sum can be retrieved in constant time. This technique is widely used for array range queries and optimization of repeated summation tasks.
What is the time complexity of Sum of Variable Length Subarrays?
The optimal solution runs in O(n) time using a prefix sum array. Building the prefix array takes O(n), and each index performs a constant-time range sum query. A naive brute-force solution that recomputes sums for each subarray takes O(n²) time.