Calculate all possible sums in an array from its sub arrays

As user1984 observes, we can't achieve o(n²) by doing constant work for each sub-array. Here's how we get to O(n).

The sub-array minimum is the hardest factor to deal with, so we factor it out. Assume that the elements are pairwise distinct to avoid double counting in the math below (the code won't change). Letting A range over sub-arrays and x over elements,

sum_{A} [(sum_{y in A} y) (min A)] = sum_{x} [x sum_{A such that min(A) = x} (sum_{y in A} y)]. 

Focusing on sum_{A | min(A) = x} (sum_{y in A} y) first, the picture is that we have a sub-array like

a b x c d e 

where the element to the left of a (if it exists) is less than x, the element to the right of e (if it exists) is less than x, and all of the elements shown are greater than x. We want to sum over all sub-sub-arrays containing x.

a b x b x x a b x c b x c x c a b x c d b x c d x c d a b x c d e b x c d e x c d e 

We still don't have time to sum over these sub-sub-arrays, but fortunately there's a pattern. Here are the number of times each element appears in a sub-sub-array.

a: 4 = 1 * 4 appearances b: 8 = 2 * 4 appearances x: 12 = 3 * 4 appearances c: 9 = 3 * 3 appearances d: 6 = 3 * 2 appearances e: 3 = 3 * 1 appearances 

This insight reduces the processing time for one sub-array to O(n), but there are still n sub-arrays, so we need two more ideas.

Now is the right time to figure out what the sub-arrays look like. The first sub-array is the whole array. We split this array at the minimum element and recursively investigate the left sub-array and the right separately.

This recursive structure is captured by the labeled binary tree where

• The in-order traversal is the array elements in order;
• Every node has a label less than its children. (I'm still assuming distinct elements. In practice what we can do is to declare the array index to be a tiebreaker.)

This is called a treap, and it can be constructed in linear time by an algorithm with a family resemblance to precedence parsing. For the array [3,1,4,5,9,2,6], for example, see below.

 1 / \ 3 2 / \ 4 6 \ 5 \ 9 

The final piece is being able to aggregate the sum patterns above. Specifically, we want to implement an API that might look like this in C++:

class ArraySummary { public: // Constructs an object with underlying array [x]. ArraySummary(int x); // Returns an object representing the concatenation of the underlying arrays. ArraySummary Concatenate(ArraySummary that); // Returns the sum over i of (i+1)*array[i]. int WeirdSum(); }; 

The point of this interface is that we don't actually need to store the whole array to implement WeirdSum(). If we store

• The length length of the underlying array,
• The usual sum sum of the underlying array,
• The weird sum weird_sum of the underlying array;

then we can implement the constructor as

length = 1; sum = x; weird_sum = x; 

and Concatenate() as

length = length1 + length2; sum = sum1 + sum2; weird_sum = weird_sum1 + weird_sum2 + length1 * sum2; 

We need two of these, one in each direction. Then it's just a depth-first traversal (actually if you implement precedence parsing, it's just bottom-up).

Your current solution has time complexity O(n^2), assuming that list.get is O(1). There are exactly 1 + 2 + ... + n-1 + n operations which can be expressed as n * (n + 1)/2, hence O(n^2).

Interestingly, n * (n + 1)/2 is the number of sub arrays that you can get from an array of length n, as defined in your question and evident from your code.

This implies that you are doing one operation per sub array and this is the requird minimum operations for this task, since you need to look at least once at each sub array.

My conclusion is that it isn't possible to reduce the time complexity of this task, unless there is some mathematical formula that helps to do so.

This doesn't necessary mean that there aren't ways to optimize the code, but that would need testing and may be language specific. Regardless, it wouldn't change the time complexity in terms of n where n is the length of the input array.

Appreciate any input on my logic. I'm learning myself.

The answer provided by David Eisenstat is very efficient with complexity of O(n).

I would like to share another approach, that although it has time complexity of O(n^2), it may be more simple and may be easier for some (me included) to fully understand.

Algorithm

1. initiate two dimensional array of size matrix[n][n], each cell will hold pair of Integers <sum, min>. we will denote for each Matrix[i, j] the first element of the pair as Matrix[i, j].sum and the second as Matrix[i, j].min
2. Initiate the diagonal of the matrix as follows:

for i in [0, n-1]: Matrix[i][i] = <arr[i], arr[i]> 

for i in [0, n-1]: for j in[i, n-1]: Matrix[i, j] = < Matrix[i - 1, j].sum + arr[i, j], Min(Matrix[i - 1, j].min, arr[i, j]) > 

4. Calculate the result:

result = 0 for i in [0, n-1]: for j in[i, n-1]: result += Matrix[i, j].sum * Matrix[i, j].min 

Time Complexity Analysis

• Step 1: initiating two dimensional array ofsize [n,n] will take in theory O(n^2) as it may require to initiate all indices to 0, but if we skip the initialization of each cell and just allocate the memory this could take O(1)

• Step 2 : Here we iterate from 0 to n-1 doing constant work each iteration and therefore the time complexity is O(n)

• Step 3: Here we iterate over half of the matrix cells(all that are right of the diagonal), doing constant work each iteration, and therefore the time complexity is O((n - 1) + (n - 2) + .... + (1) + (0)) = O(n^2)

• Step 4: Similar analysis to step 3, O(n^2)

In total we get O(n^2)

Explanation for solution

This is simple example of Dynamic programming approach.

Let's define sub[i, j] as the subarray between index i and j while 0 =< i, j <= n-1

Then:

• Matrix[i, j].sum = sum x in sub[i, j]
• Matrix[i, j].min = min x in sub[i, j]

Why?

for sub[i,i] it's obvious that:

• sum x in sub[i, i] = arr[i]
• min x in sub[i, i] = arr[i]

Just like we calculate in step 2.

Convince yourself that:

• sum sub[i,j] = sum sub[i-1,j] + arr[i, j]
• min sub[i,j] = Min(min sub[i-1,j], arr[i, j])

This explains step 3.

In Step 4 we just sums up everything to get the required result.

It can be with the O(n) solution.

Intuition

First of all, we want to achieve all subarrays like this. a1 a2 a3 min b1 b2 b3 where min is minimum. We will use a monotonic increasing stack to achieve it. In every iteration, if the stack's top value is greater than the next element, we will pop the stack and calculate the sum until the condition is not met.

Secondly, we want to figure out how to calculate the total sum if we have an a1 a2 a3 min b1 b2 b3 subarray. Here, we will use a prefix of prefix sum.

Prefix Sum

At first, we need the prefix sum. Assume that p indicates prefix sum, we want to achieve p1 p2 p3 p4 p5 p6 p7. Our prefix sum will be like this;

p1: a1

p2: a1 + a2

p3: a1 + a2 + a3

.

p6 : a1 + a2 + a3 + min + b1 + b2

p7: a1 + a2 + a3 + min + b1 + b2 + b3

Within prefix sum now we can calculate the sum of between two indexes. The sum of (start, end] is pend - pstart. If start: 1 and end: 3 that means p3 - p1 = (a1 + a2 + a3) - (a1) = a2 + a3.

Prefix of Prefix Sum

How can we calculate all possible subarray sums that include our min value?

We separate this calculation to the left side and right side.

The left side included min will be a1 a2 a3 min.

The right side included min will be min b1 b2 b3.

For example, some of the possible sums can be:

a1 + a2 + a3 + min

a1 + a2 + a3 + min + b1

a3 + min + b1 + b2 + b3

min + b1 + b2 + b3

We need to find all the [bj, ai] sums. Where i means all the left side indexes and j means all the right side indexes. Now We need to use the prefix of prefix sum. It will give us all possible sums between two indexes. Let's say P. It will be sum(Pj) - sum(Pi).

Now, how do we calculate our sum(Pj) - sum(Pi)?

So Pj is P7 - P4. It is the right side possible sum. Same way Pi is P4 - P1. It is the left side possible sum.

How many combinations for sum(Pj) are there?

leftSize * (P7 - P4). Same way for sum(Pi) it will be rightSize * (P4 - P1).

Final equation to calculate subarray [a1 a2 a3 min b1 b2 b3] is: min * ((leftSize * (P7 - P4)) - (rightSize * (P4 - P1))).

Algorithm

public static int process(List<Integer> list) { int n = list.size(); int mod = (int) 1e9 + 7; int[] preSum = new int[n + 2]; Deque<Integer> stack = new ArrayDeque<>(); int pre = 0; int result = 0; for (int i = 0; i <= n; i++) { int num = i < n ? list.get(i) : 0; // current prefix sum pre = (pre + num) % mod; // prefix of prefix sum array preSum[i + 1] = (preSum[i] + pre) % mod; while (!stack.isEmpty() && list.get(stack.peek()) > num) { int mid = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int lSize = mid - left; int rSize = i - mid; long lSum = left < 0 ? preSum[mid] : preSum[mid] - preSum[left]; long rSum = preSum[i] - preSum[mid]; result = (int) (result + (list.get(mid) * ((rSum * lSize - lSum * rSize) % mod)) % mod) % mod; } stack.push(i); } return (result + mod) % mod; } 

Time complexity: O(n) Space complexity: O(n)

References

Thanks to @lee215 for one pass solution.

Thanks to @forAc for the explanation of the final equation.

https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/JavaC%2B%2BPython-One-Pass-Solution

Since I could not completely understand David's answer I have used what I understood from it and then wrote a complete function to calculate the result with his ideas. I'm not convinced what he says at the end is fully correct as I had to use formulas that were sort of similar but not exactly, and I can't see how they are equivalent.

I will put in the code then explain

class Node: def __init__(self, value = None, index=0): self.index = index self.parent = 0 self.left = 0 self.right = 0 self.value = value tree = [] tree.append(Node(0)) for i in range(1,len(int_array)+1): k = i - 1 tree.append(Node(int_array[i-1],i-1)) while(tree[k].value > tree[i].value): k = tree[k].parent tree[i].left = tree[k].right tree[k].right = i tree[i].parent = k tree[tree[i].left].parent = i 

So first I used the treap like David suggested and essentially copied the implementation of that from OI Wiki. Now for the function itself.

total_weird_sum = 0 def weird_sum(node, total_weird_sum): if(node.left == 0 and node.right == 0): total_weird_sum += node.value**2 return 1, node.value, node.value, total_weird_sum if(node.left==0): left_length, left_value_sum, left_value_sequence_sum = 0, 0, 0 else: left_length, left_value_sum, left_value_sequence_sum, total_weird_sum = weird_sum(tree[node.left], total_weird_sum) if(node.right==0): right_length, right_value_sum, right_value_sequence_sum = 0,0, 0 else: right_length, right_value_sum, right_value_sequence_sum, total_weird_sum = weird_sum(tree[node.right], total_weird_sum) total_weird_sum += node.value*right_value_sequence_sum*(left_length+1) + node.value*left_value_sequence_sum*(right_length+1) + (right_length+1)*(left_length+1)*node.value**2 if(node.parent==0): return total_weird_sum value_sum = left_value_sum + right_value_sum + node.value length = right_length+left_length+1 if(node.index > tree[node.parent].index): value_sequence_sum = (length+1)*(left_value_sum) - left_value_sequence_sum + right_value_sequence_sum + (right_length+1)*node.value else: value_sequence_sum = (length+1)*(right_value_sum) - right_value_sequence_sum + left_value_sequence_sum + (left_length+1)*node.value return length, value_sum, value_sequence_sum, total_weird_sum 

It is a recursive function, again as David suggested. Let me use as the example the treap structure from David's example.

 1 / \ 3 2 / \ 4 6 \ 5 \ 9 

First, let's calculate the end children contribution. Since they are just single element sub-arrays a number a will contribute a**2 to the answer. The code in the lines

if(node.left == 0 and node.right == 0): total_weird_sum += node.value**2 return 1, node.value, node.value, total_weird_sum 

adds this to the weird sum and then also returns the length of that set, 1, the value a twice (explained in a minute). So 9 contributes 9**2.

Now for the next subarray which is [5,9], the subarrays are [5] and [5,9]. To explain what David put further with his example of

a b x c d e 

if x is the smallest then the number of occurrences of x is the number of elements left of x, plus 1 (left length + 1) multiplied by the same on the right, or (left length + 1)(right length + 1). For the other numbers it is the number of steps from the edges to the number multiplied by the other length + 1. So b is 2*4 occurrences. We combine the sum of the left and right elements weighed by their contribution with the value sequence sum. The right value sequence sum is 3*c + 2*d + e

Thus in the code

 if(node.left==0): left_length, left_value_sum, left_value_sequence_sum = 0, 0, 0 else: left_length, left_value_sum, left_value_sequence_sum, total_weird_sum = weird_sum(tree[node.left], total_weird_sum) if(node.right==0): right_length, right_value_sum, right_value_sequence_sum = 0,0, 0 else: right_length, right_value_sum, right_value_sequence_sum, total_weird_sum = weird_sum(tree[node.right], total_weird_sum) total_weird_sum += node.value*right_value_sequence_sum*(left_length+1) + node.value*left_value_sequence_sum*(right_length+1) + (right_length+1)*(left_length+1)*node.value**2 

The children that are empty contribute nothing, while the return of the function is value sequence sum and the ordinary value sum from the node and all its children. The right value sequence sum at node 4 is 2*5 + 9, for example, while the ordinary sum is 5+9. This is multiplied by the left length + 1 (1) and by the node value 4. The same happens for the other child but in this case it contributes nothing. Also, (left_length + 1)(right_length +1)*node.value contributes the one element subarray of the node to weird sum.

Now for the trickier part. As we move from a child to its parent, we want to combine the all the nodes descended from the child into one effective sequence. The correct way for the example above to node 2 is

 1 / \ 3 2 / \ 9 6 / 5 / 4 

as in our original array is 9 closest to 5. You can imagine rotating the right branch about 4 counterclockwise towards 2. The right value sequence sum has to be adjusted now to account for the change in order. The original ones were 2*5+9 and now it must be 3*9 + 2*5 + 4. To do this, if the parent node is on the right, we take the right value sum (5+9) and multiply it by the number of nodes including the parent + 1 (2+1+1) then remove the current right value sequence sum and add the left value sequence sum as well as the (left length +1)*node value. In our example that is

(3+1)*(5+9) - (2*5+9) + 0 + (0+1)*4 = 3*9 + 2*5 + 4

and if the parent is on the left we switch left and right as appropriate.

 value_sum = left_value_sum + right_value_sum + node.value length = right_length+left_length+1 if(node.index > tree[node.parent].index): value_sequence_sum = (length+1)*(left_value_sum) - left_value_sequence_sum + right_value_sequence_sum + (right_length+1)*node.value else: value_sequence_sum = (length+1)*(right_value_sum) - right_value_sequence_sum + left_value_sequence_sum + (left_length+1)*node.value return length, value_sum, value_sequence_sum, total_weird_sum 

This part of the code does this and returns the new value sequence sum, the new value sum (4+5+9 in our case), and the length (3 in our case).