Efficiently generate list of lightest intervals of a vector

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.