Calculate all possible sums in an array from its sub arrays

Question

I have an array of numbers, now I have to find sum of elements by generating all the possible subarrays of the given array and applying some conditions.

The condition is for each subarray get the minimum and also find the total of elements in it and multiply both (minimum * total). Finally, add all these multiplied values for all subarrays.

Here is the problem statement:

Find the sum of all possible sub-arrays using the below formula:

Sum(left, right) = (min of arr[i]) * (∑ arr[i]), where i ranges from left to right.

Example:

Array = [2,3,2,1]

The sub arrays are: [start_index, end_index]

 [0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4
 [0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10
 [0,2] subarray = [2,3,2], min is 2 and total of items = 7. min * total = 2*7=14
 [0,3] subarray = [2,3,2,1], min is 1 and total of items = 8. min * total = 1*8=8

 [1,1] subarray = [3], min is 3 and total of items = 3. min * total = 3*3 = 9
 [1,2] subarray = [3,2], min is 2 and total of items = 5. min * total = 2*5 = 10
 [1,3] subarray = [3,2,1], min is 1 and total of items = 6. min * total = 1*6 = 6

 [2,2] subarray = [2], min is 2 and total of items = 2. min * total = 2*2 = 4
 [2,3] subarray = [2,1], min is 1 and total of items = 3. min * total = 1*3 = 3

 [3,3] subarray = [1], min is 1 and total of items = 1. min * total = 1*1 = 1
 
 Total = 4 + 10 + 14 + 8 + 9 + 10+ 6 + 4 + 3 + 1 = 69

So the answer is 69 in this case.

Constraints:

Each array element is in range 1 to 10^9. Array size 1 to 10^5. Return response in modulo 10^9+7

This is the code I tried.

public static int process(List<Integer> list) {
    int n = list.size();
    int mod = 7 + 1000_000_000;
    long result = 0;
    for (int i = 0; i < n; i++) {
        long total = 0;
        int min = list.get(i);
        for (int j = i; j < n; j++) {
            int p = list.get(j);
            total = (total + p) % mod;
            min = Math.min(min, p);
            result = (result + (min * total) % mod) % mod;
        }
    }
    return (int) result;
}

I want to reduce the time complexity of this algorithm?

What can be a better approach to solve this task?

Update:

David Eisenstat has given a great answer, but Im finding it to difficult to understand and come with a Java program, can someone provide a java solution for the approach or provide a pseudo code so i can come up with a program.

can you display the index ranges using standard math notation: [ - inclusive, ( - exclusive — Alexander Ivanchenko, Jan 21 '22 at 21:47
@AlexanderIvanchenko, I added `Constraints` already, is that what you are asking? — learner, Jan 21 '22 at 22:00
that's the international notation of intervals [link](https://en.wikipedia.org/wiki/Interval_(mathematics)#Classification_of_intervals) — Alexander Ivanchenko, Jan 21 '22 at 22:03
@AlexanderIvanchenko, I have to find all possible sub-arrays which are continuous as mentioned in my post. so [0, n) I guess. — learner, Jan 21 '22 at 22:18
`[3,3], min is 3 and total of items = 3` part is my question. — Redu, Jan 24 '22 at 20:34
@Redu, `[3,3] subarray = [1]` here [3,3] represents [start_index, end_index] of input [2,3,2,1] so at index `3` the value is `1` so subarray [3,3] is [1] — learner, Jan 24 '22 at 21:39
I was referring to the 5th line though which starts with `[1,1]`. — Redu, Jan 24 '22 at 22:25
@Redu `[1,1]` means it holds only single element `3`, I have updated it — learner, Jan 24 '22 at 23:23
the number of "subarrays in an array" is n! / fact(n) ... (where n is the size/length of array :) ...further, lets see... — xerx593, Jan 24 '22 at 23:36
Could you edit your post and quote the actual instructions? I don’t think it’s feasible to brute-force generate all sub arrays given the constraints. — Richard Ambler, Jan 24 '22 at 23:40
..i just "played" the numbers, but i noticed: 69 = fact(4) - 1 * (1*2*3) / 2 — xerx593, Jan 24 '22 at 23:40
@RichardAmbler, I added details under `Here is the problem statement` , please check. — learner, Jan 25 '22 at 09:36
Could you provide a link to the page where this problem was originally asked? — Damien, Jan 25 '22 at 10:31
@Damien, I tried this some days back during an interview, so do not have a link to that question. — learner, Jan 25 '22 at 13:06

David Eisenstat · Answer 1 · 2022-01-26T13:48:56.217

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.

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).

Thank you for the great answer. I'm humbled to be beaten by a research engineer at Google :D After giving my answer, I was wondering about mathmatical approahces and how we could refactor and summarize the task to reduce TC. I would have never figured out such an answer as yours. Some of the parts of your approach are **entirely** new to me. I'm still trying to understand it lol. But I learned one thing (again). Write out simple examples. I was doing it in my head. I have experienced this time and again. But fail to do it most of the times. Thanks again. — user1984, Jan 26 '22 at 08:33
I tried reading your answer several times but I am not able to understand how to come up with a program based on your answer, can you please help me with a java code or python code for this. — learner, Feb 07 '22 at 16:08

score 1 · Answer 2 · answered Jan 25 '22 at 10:14

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.

score 1 · Answer 3 · answered Jan 30 '22 at 21:44

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

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
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]) 
        >

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.

As time complexity is still O(n^2) the program fails with time limit exceeded errors. — learner, Feb 07 '22 at 16:33

Calculate all possible sums in an array from its sub arrays

3 Answers3

Algorithm

Time Complexity Analysis

Explanation for solution