Scale Engineer

Sum of Variable Length Subarrays

Easy
#3045Time: O(n^2). The outer loop runs `n` times. The inner loop's number of iterations depends on `nums[i]`, but in the worst-case scenario (e.g., if `nums[i]` is large for all `i`), it can run up to `n` times. This results in a nested loop structure leading to a quadratic time complexity.Space: O(1). We only use a few variables to store the loop indices and the running sum, requiring constant extra space regardless of the input size.
Patterns
Prefix Sum
Data structures
Array

Prompt

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 <= 100
  • 1 <= nums[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through each index i of the array, determine the corresponding subarray by calculating its start and end points, and then iterate through this subarray to sum its elements. This sum is then added to a running total.

Algorithm

  • Initialize a variable totalSum to 0.
  • Loop through the input array nums with an outer loop from i = 0 to n-1.
  • Inside the outer loop, for each i, calculate the start index of the subarray: start = max(0, i - nums[i]).
  • Create an inner loop that iterates from j = start to i.
  • Inside the inner loop, add the value nums[j] to totalSum.
  • After both loops complete, totalSum will hold the final result.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. It follows the problem statement literally.

  1. We initialize a variable, totalSum, to store the final answer.
  2. We use a primary loop to iterate through each index i from 0 to n-1, where n is the length of the nums array. This loop corresponds to defining the subarray for each index.
  3. For each i, we calculate the starting index start of the subarray as max(0, i - nums[i]).
  4. We then use a nested loop to iterate from this start index up to i.
  5. In this inner loop, we access each element nums[j] of the current subarray and add it to our totalSum.
  6. After the outer loop finishes, totalSum contains the sum of all elements from all the defined subarrays.
class Solution {    public int sumOfVariableLengthSubarrays(int[] nums) {        int n = nums.length;        int totalSum = 0;        for (int i = 0; i < n; i++) {            int start = Math.max(0, i - nums[i]);            // Instead of a temporary sum, we can add directly to totalSum            for (int j = start; j <= i; j++) {                totalSum += nums[j];            }        }        return totalSum;    }}

Complexity

Time

O(n^2). The outer loop runs `n` times. The inner loop's number of iterations depends on `nums[i]`, but in the worst-case scenario (e.g., if `nums[i]` is large for all `i`), it can run up to `n` times. This results in a nested loop structure leading to a quadratic time complexity.

Space

O(1). We only use a few variables to store the loop indices and the running sum, requiring constant extra space regardless of the input size.

Trade-offs

Pros

  • Simple and easy to understand and implement.

  • Space-efficient as it uses constant extra space.

  • Sufficiently fast for the given constraints (n <= 100).

Cons

  • Inefficient for larger input sizes as it repeatedly calculates sums over overlapping subarray portions.

  • The time complexity is quadratic, which might be too slow if the constraints were larger.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem