Problem

Given an array write an algorithm to find the sum of all the possible sub arrays.

Examples

Example 1:

1
2
3

Input: arr: [1, 2, 3]
Output: 20
Explanation: All subarrays are [[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]] and their sum is 1 + 3 + 6 + 2 + 5 + 3 = 20

Solution

Method 1 - By generating all sub arrays

As discussed in Print all sub arrays, find out all the sub arrays and then calculate the sum. Here is the approach:

  • Iterate through each starting point of subarrays.
  • For each starting point, iterate through each ending point of subarrays.
  • Calculate the sum of the subarray from the starting point to the ending point, and accumulate the sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class Solution {
    public long sumOfAllSubarrays(int[] nums) {
        int n = nums.length;
        long totalSum = 0;

        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                long subarraySum = 0;
                for (int k = start; k <= end; k++) {
                    subarraySum += nums[k];
                }
                totalSum += subarraySum;
            }
        }

        return totalSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def sum_of_all_subarrays(nums):
        n = len(nums)
        total_sum = 0

        for start in range(n):
            for end in range(start, n):
                subarray_sum = 0
                for k in range(start, end + 1):
                    subarray_sum += nums[k]
                total_sum += subarray_sum

        return total_sum

# Example usage
nums = [1, 2, 3]
result = sum_of_all_subarrays(nums)
print("Sum of all possible subarrays:", result)

Complexity

  • ⏰ Time complexity: O(n^3), because for each possible subarray, we spend time to sum its elements. There are n(n+1)/2 subarrays and summing an individual subarray can take O(n) time in the worst case.
  • 🧺 Space complexity: O(1),  as no additional space is required apart from a few variables.

Method 2 - Using prefix sum

  • Calculate the prefix sum array, where each element at index i contains the sum of the array from the start up to index i.
  • Iterate through each starting point of subarrays.
  • For each subarray starting point, using the prefix sum array calculate the sum for each ending point.
  • Accumulate the subarray sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public long sumOfAllSubarrays(int[] nums) {
        int n = nums.length;
        long[] prefixSum = new long[n];
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        long totalSum = 0;

        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                if (start == 0) {
                    totalSum += prefixSum[end];
                } else {
                    totalSum += prefixSum[end] - prefixSum[start - 1];
                }
            }
        }

        return totalSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    # Method 2: Using Prefix Sum
    def sum_of_all_subarrays(self, nums):
        n = len(nums)
        prefix_sum = [0] * n
        prefix_sum[0] = nums[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]

        total_sum = 0

        for start in range(n):
            for end in range(start, n):
                if start == 0:
                    total_sum += prefix_sum[end]
                else:
                    total_sum += prefix_sum[end] - prefix_sum[start - 1]

        return total_sum

Complexity

  • ⏰ Time complexity: O(n^2) for iterating through the subarrays plus O(n) for computing the prefix sum, thus O(n^2).
  • 🧺 Space complexity: O(n) due to the prefix sum array.

Method 3 - Counting number of occurrences of numbers in subarray

Consider the array [1, 2, 3, 4]. The subarrays are:

1
2
3
4

[1], [1 2], [1 2 3], [1 2 3 4],
[2], [2 3], [2 3 4],
[3], [3 4],
[4]

For each element, the number of occurrences can be observed as follows:

  • 1 appears 4 times
  • 2 appears 6 times
  • 3 appears 6 times
  • 4 appears 4 times

By examining the subarrays starting with each element, we observe:

  • For 1, subarrays are [1], [1 2], [1 2 3], [1 2 3 4]
  • For 2, subarrays are [2], [2 3], [2 3 4]
  • For 3, subarrays are [3], [3 4]
  • For 4, subarrays are [4]

Thus, the number of times each element appears at the first position will be equal to n (in this case, n = 4). The next element, 2, will appear n - 1 times, and so on. Hence, the ith element appears (n-i) times.

Occurrences at the first positions:

  • 1 appears 4 times.
  • 2 appears 3 times.
  • 3 appears 2 times.
  • 4 appears 1 time.

Subtracting these from the initial count gives us:

  • 1: 0 remaining
  • 2: 3 remaining
  • 3: 4 remaining
  • 4: 3 remaining

The formula (n-i) * i helps us determine this pattern.

So, the total number of occurrences for the ith element is (n-i) * i + (n-i) which simplifies to (n-i) * (i + 1).

For the array [1, 2, 3, 4], the total sum is:

  • 1 * (4-0) * (0+1) + 2 * (4-1) * (1+1) + 3 * (4-2) * (2+1) + 4 * (4-3) * (3+1)
  • This equals 1 * 4 + 2 * 6 + 3 * 6 + 4 * 4 = 50.

For the array [1, 2, 3], the total sum is:

  • 1 * (3-0) * (0+1) + 2 * (3-1) * (1+1) + 3 * (3-2) * (2+1)
  • This equals 1 * 3 + 2 * 4 + 3 * 3 = 3 + 8 + 9 = 20.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class Solution {
    public long sumOfAllSubarrays(int[] nums) {
        int n = nums.length;
        long totalSum = 0;

        for (int i = 0; i < n; i++) {
            totalSum += nums[i] * (n - i) * (i + 1);
        }
        return totalSum;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def sum_of_all_subarrays(self, nums):
        n = len(nums)
        total_sum = 0

        for i in range(n):
            total_sum += nums[i] * (n - i) * (i + 1)

        return total_sum

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)