Efficiently generate list of lightest intervals of a vector

Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal).

For example, if we have the array:

1 1 0 0 1 2 1 0 0 0 1


For any length n, the minimal weight of $i$ length interval is:

interval size:              1  2  3  4  5  6  7  8  9  10 11
interval weight:            0  0  0  1  2  4  4  4  5  6  7


A naive algorithm would compute the shortest interval for each $i$ by itself, which results in a $O(n^2)$ time algorithm (keeping a sliding window of size $i$).

If we attempt a greedy "triangle" algorithm (start from the smallest number, expand by 1 each time), it fails, no matter if we try it botom-up or top-down:

A triangle algorithm would fail at 1 1 1 4 0 1 4

1 1 1 4 0 1 4 -> 0
1:0 :         0
2:1 :       4 0 > 0 1
3:5 :       4 0 1 = 0 1 4     BUT: 1 1 1 would be cheaper
4:6 :     1 4 0 1 < 4 0 1 4
5:7 :   1 1 4 0 1 < 1 4 0 1 4
6:8 : 1 1 1 4 0 1 < 1 1 4 0 1 4
7:12: 1 1 1 4 0 1 4


A reverse triangle algorithm would fail at 0 3 0 0 1 1

6:5: 0 3 0 0 1 1
5:4: 0 3 0 0 1 < 3 0 0 1 1
4:3: 0 3 0 0 < 3 0 0 1     BUT: 0 0 1 1 would be cheaper!
3:3: 0 3 0 == 3 0 0        BUT: 0 0 1 would be cheaper!
2:3: 0 3 == 3 0            BUT: 0 0 would be cheaper!
1:0: 0 < 3


Is it possible to find the interval weights in time $o(n^2)$? Is it possible to approximate them with lower runtime?

• Could you define 'easiest path' and 'difficulty'? – Max Hutchinson Jan 22 '14 at 16:56
• I think OP is asking "given an array of $n$ numbers, find, for each $1\leq i \leq n$, the interval of length $i$ that has least total weight" – Sasho Nikolov Jan 22 '14 at 17:38
• I've edited the question for readability. I've removed the "approximation" part as the suggestion algorithm runs in $O(n^2)$ time, which is equivalent to the simple algorithm that computes the intervals one by one. My edit needs to be approved for it to show. – R B Jan 23 '14 at 11:09

You can build the whole table using the following $O(n^2)$ construction:

1: 1   1   0 z:0 w:1   2   1   0   0   0   1
2:   2   1   0   1   3   3   1   0   0   1
3:   y:2   1   1   3   4 v:3   1   0   1
4:     x:2   2   3   4 u:4 ...
5:        ...
...


At every step you are calculating the value $x$ at the top of a "reversed triangle", and the value is simply the sum of an adjacent element in the previous row ($y$ in the figure) and the opposite vertex at the base of the triangle ($z$ in the figure).

*         z
...   ...
y   *
x
x = y + z


or equivalently:

w         *
...   ...
*   v
u
u = v + w


For each row the difficulty is given by the lower element of that row.

• that is so strange, how did you find this? – guest Jan 23 '14 at 11:31
• It is very simple: every vertex of the reversed triangle is the sum of its base elements, so if you extend the base you just need to sum the new element to get the new total. – Marzio De Biasi Jan 23 '14 at 11:44
• that's so brilliant and intuitive, it feels like a million other unrelated problems just solved themselves automatically. – guest Jan 23 '14 at 11:48
• @user35945: I would like to consider it in the same way ... but for me it feels like "hello Mr.Sum, I'm a new element can I join the party?" :-S :-D :-D ... – Marzio De Biasi Jan 23 '14 at 11:55
• Marzio, I do not understand your notation. Is this different from just keeping one sliding window for each size? For $O(n^2)$ pretty much any algorithm works. – Sasho Nikolov Jan 23 '14 at 19:11

Assuming you really meant the minimal weight interval as Sasho suggested, answering each query in $O(n)$ time and $O(1)$ space is trivial:

Compute the sum of the first $i$ elements, then go through the vector with a sliding window of size $i$ (keep a $sum$ and $min$ variables), and compare its sum to $min$ for every index. Every time a new minimal window is discovered, save it's start index, so after a single path you have the lightest interval of size $i$.

• but that's the worst possible way to do it, isn't it? If you want the weight for every lenght path, can't you recycle? – guest Jan 23 '14 at 10:28
• Didn't understand you're looking for the answer for all i's.. – R B Jan 23 '14 at 10:34
• Anyways, is complexity is $O(n^2)$, same as your approximation suggestion. – R B Jan 23 '14 at 11:14
• The worst case solution has a size $O(n)$ output unless you extract it lazily. Example, all 1's vector window size 1. – Chad Brewbaker Jan 23 '14 at 19:46

Apply parallel prefix. $O(n)$

In parallel subtract the prefix that is $k-1$ before it. $O(n)$.

Reduce the array in parallel and get the min $O(n)$.

You could alternatively formulate this as a monoid that esentially @RB's solution but made to run in parallel. I did one for arbitrary length roman numerals last year for a Iowa Ruby Brigade kata.

There is a Branch and Bound solution that I think runs in $O(n \log n)$. It works assuming that all elements in the vector $X$ are non-negative.

Intervals. An interval $X[b..e]$ is represented as a tuple $(b,e,w)$, where $w$ is the weight $w=X[b] + X[b+1] + \cdots + X[e]$. The length is $y.length=e-b+1$, its left extension is $y.left = (b-1,e,s+X[b-1])$, and its right extension is $(b,e+1,s+X[e+1])$.

Data Structures. The algorithm uses two data structures. The second one is a set of elements represented as a balanced binary tree, in which insertion, deletion and access run in $O(\log n)$. I assume that the input list of numbers $X$ is an array, so any access to $X$ is in constant time.

Algorithm. The algorithm uses two data structures to control the B&B process

• $queue$ is a priority queue of intervals that sorts these first by weight (lighter first), length (longer first) and position (leftmost first). The queue is implemented using a heap array, in which add and remove operations run in logarithmic time.
• $alive$ is a set of pairs $(b,e)$, where each pair represents the beginning and end of an interval. Intuitively, an interval is alive if it is in the queue and there is no other interval in the queue that contains it. The set is implemented with a balanced tree, with insertions and deletions in $O(\log s)$.

Here is the algorithm in pseudocode.

queue := emptyQueue();
alive := emptySet();
for ( j <— 1..N ) {
queue.insert( (j,j,X[j])) ;
alive.insert( (j,j) ) ;
}
l = 1
while ( l <= N){
h@(b,e,s) = queue.first()
queue.removeFirst()
if( alive.contains(b,e) ){
alive.remove(b,e)
if ( h.length == l) {
C[l] = h
l ++
}
if (b > 1){
left = h.left
queue.insert(left)
alive.insert( b-1,e  )
alive.remove( b-1,e-1 )
alive.remove( b-1,b-1 )
}
if (e < N){
right = h.right
queue.insert(right)
alive.insert( b  ,e+1 )
alive.remove( b+1,e+1 )
alive.remove( e+1,e+1 )
}
}
}


The initialisation runs in $O(N\log N)$ time. The $\mathtt{while}$ loop performs an unknown number $f$ of iterations. Each one performs several operatios on the queue and set with running times in $O(\log s)$ and $O(\log q)$, where $q$ and $s$ are the maximum number of elements in the queue and set during the algorithm. This maximum number is below $f+N$. The key to control the loop is the $alive$ set of intervals, whose elements are pairwise not-contained, so there are at most $N$ elements in the set.