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

<pre><code>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:        ...
...
</code></pre>

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

<pre><code>*         z
 ...   ...
   y   *
     x
x = y + z
</code></pre>

<p>or equivalently:</p>

<pre><code>w         *
 ...   ...
   *   v
     u
u = v + w
</code></pre>

<p>For each row the difficulty is given by the lower element of that row.</p>

CC BY-SA 3.0
2014-01-23T11:31:23.803Z
that is so strange, how did you find this?
guest
CC BY-SA 3.0
2014-01-23T11:44:47.133Z
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
CC BY-SA 3.0
2014-01-23T11:48:04.260Z
that's so brilliant and intuitive, it feels like a million other unrelated problems just solved themselves automatically.
guest
CC BY-SA 3.0
2014-01-23T11:55:36.177Z
@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
CC BY-SA 3.0
2014-01-23T19:11:01.463Z
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
CC BY-SA 3.0
2014-01-24T07:42:25.907Z
@SashoNikolov: It is essentially the same, but in a "bare" sliding window algorithm, when you process the window of size $i$ you execute the sums of the first $i-1$ elements, in my construction above I simply reuse the previous sums (avoiding in this way the initial sum and the subtraction operations when sliding the window) at the cost of an extra $O(n)$ space.
Marzio De Biasi
CC BY-SA 3.0
2014-01-23T11:11:59.627Z
2014-01-23T11:19:09.920Z
2014-01-23T11:19:09.920Z
Marzio De Biasi
<p>There is a <a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow">Branch and Bound</a> solution that I <em>think</em> runs in $O(n \log n)$. 
It works assuming that all elements in the vector $X$ are non-negative. </p>

<p><strong>Intervals.</strong> 
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])$.</p>

<p><strong>Data Structures.</strong>
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.   </p>

<p><strong>Algorithm.</strong>
The algorithm uses two data structures to control the B&amp;B process </p>

<ul>
<li>$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. </li>
<li>$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)$.</li>
</ul>

<p>Here is the algorithm in pseudocode. </p>

<pre><code>queue := emptyQueue(); 
alive := emptySet(); 
for ( j &lt;— 1..N ) {
    queue.insert( (j,j,X[j])) ; 
    alive.insert( (j,j) ) ; 
}
l = 1
while ( l &lt;= 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 &gt; 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 &lt; N){
            right = h.right
            queue.insert(right)
            alive.insert( b  ,e+1 ) 
            alive.remove( b+1,e+1 )
            alive.remove( e+1,e+1 )
        }  
    }
}
</code></pre>

<p>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.  </p>

CC BY-SA 3.0
2014-01-24T07:46:28.320Z
2014-01-26T12:51:49.413Z
2014-01-26T12:51:49.413Z
Diego Alonso
<p>Assuming you really meant the minimal weight interval as Sasho suggested, answering each query in $O(n)$ time and $O(1)$ space is trivial:</p>

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

CC BY-SA 3.0
2014-01-23T10:28:52.237Z
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
CC BY-SA 3.0
2014-01-23T10:34:42.933Z
Didn't understand you're looking for the answer for all i's..
R B
CC BY-SA 3.0
2014-01-23T11:14:47.557Z
Anyways, is complexity is $O(n^2)$, same as your   approximation suggestion.
R B
CC BY-SA 3.0
2014-01-23T19:46:34.547Z
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
CC BY-SA 3.0
2014-01-23T09:29:03.957Z
2014-01-23T09:54:00.453Z
2014-01-23T09:54:00.453Z
R B
<p>Apply <a href="http://en.wikipedia.org/wiki/Prefix_sum" rel="nofollow">parallel prefix</a>. $O(n)$</p>

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

<p><a href="http://www.mcs.anl.gov/research/projects/mpi/www/www3/MPI_Reduce.html" rel="nofollow">Reduce</a> the array in parallel and get the min $O(n)$.</p>

<p>You could alternatively formulate this as a monoid that esentially @RB's solution but made to run in parallel. I did one for <a href="https://gist.github.com/chadbrewbaker/4542999" rel="nofollow">arbitrary length roman numerals</a> last year for a Iowa Ruby Brigade kata.</p>

CC BY-SA 3.0
2014-01-23T19:40:44.083Z
2014-01-23T19:40:44.083Z
Chad Brewbaker
<p>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).</p>

<p>For example, if we have the array:</p>

<pre><code>1 1 0 0 1 2 1 0 0 0 1
</code></pre>

<p>For any length n, the minimal weight of $i$ length interval is:</p>

<pre><code>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
</code></pre>

<p>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$).</p>

<p>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:</p>

<p>A triangle algorithm would fail at 1 1 1 4 0 1 4</p>

<pre><code>1 1 1 4 0 1 4 -&gt; 0
1:0 :         0
2:1 :       4 0 &gt; 0 1
3:5 :       4 0 1 = 0 1 4     BUT: 1 1 1 would be cheaper
4:6 :     1 4 0 1 &lt; 4 0 1 4
5:7 :   1 1 4 0 1 &lt; 1 4 0 1 4
6:8 : 1 1 1 4 0 1 &lt; 1 1 4 0 1 4
7:12: 1 1 1 4 0 1 4
</code></pre>

<p>A reverse triangle algorithm would fail at 0 3 0 0 1 1</p>

<pre><code>6:5: 0 3 0 0 1 1
5:4: 0 3 0 0 1 &lt; 3 0 0 1 1
4:3: 0 3 0 0 &lt; 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 &lt; 3
</code></pre>

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

CC BY-SA 3.0
2014-01-22T16:56:26.033Z
Could you define 'easiest path' and 'difficulty'?
Max Hutchinson
CC BY-SA 3.0
2014-01-22T17:38:43.870Z
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
CC BY-SA 3.0
2014-01-23T11:09:24.050Z
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
<ds.algorithms><dynamic-programming>
Efficiently generate list of lightest intervals of a vector
guest
# Efficiently generate list of lightest intervals of a vector

(Asked by: username_0 on 2014-01-22)

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?

**Tags:** ds.algorithms, dynamic-programming
> **Comments:**
> **username_1**: Could you define 'easiest path' and 'difficulty'?  
> **username_2**: 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"  
> **username_3**: 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.  

---

## 4 answers

### Answer by username_4 on 2014-01-23. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: that is so strange, how did you find this?  
> **username_4**: 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.  
> **username_0**: that's so brilliant and intuitive, it feels like a million other unrelated problems just solved themselves automatically.  
> **username_4**: @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 ...  
> **username_2**: 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.  
> **username_4**: @SashoNikolov: It is essentially the same, but in a "bare" sliding window algorithm, when you process the window of size $i$ you execute the sums of the first $i-1$ elements, in my construction above I simply reuse the previous sums (avoiding in this way the initial sum and the subtraction operations when sliding the window) at the cost of an extra $O(n)$ space.  

---

### Answer by username_5 on 2014-01-24. Score: 0

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.


---

### Answer by username_3 on 2014-01-23. Score: 0

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

> **Comments:**
> **username_0**: 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?  
> **username_3**: Didn't understand you're looking for the answer for all i's..  
> **username_3**: Anyways, is complexity is $O(n^2)$, same as your   approximation suggestion.  
> **username_6**: The worst case solution has a size $O(n)$ output unless you extract it lazily. Example, all 1's vector window size 1.  

---

### Answer by username_6 on 2014-01-23. Score: 0

Apply [parallel prefix](http://en.wikipedia.org/wiki/Prefix_sum). $O(n)$

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

[Reduce](http://www.mcs.anl.gov/research/projects/mpi/www/www3/MPI_Reduce.html) 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](https://gist.github.com/chadbrewbaker/4542999) last year for a Iowa Ruby Brigade kata.


---

