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?
CodePudding user response：
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.
CodePudding user response：
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 Summarize();
};
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
lengthof the underlying array, - The usual sum
sumof the underlying array, - The weird sum
weird_sumof 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).