Timeline for Find the smallest subarray with sum larger than a threshold

8 events

when toggle format	what		by	license	comment
Dec 6, 2023 at 5:07	vote	accept	zebda
Dec 5, 2023 at 19:39	comment	added	Steven		Yes, in your example $i=2, j=2$ never happens. That's expected, since the algorithm runs in linear time only $O(n)$ of the $\Omega(n^2)$ possible pairs of indices $i, j$ will be encountered. If you use `while` $i \le n$ then the last iteration will increment $i$ from $n$ to $n+1$, which is out of bounds.
Dec 5, 2023 at 19:15	comment	added	zebda		I think the algorithm should run `while` $i\leq n$ instead of $i<n$.
Dec 5, 2023 at 19:08	comment	added	zebda		In the case $[5, 10, 1, 8, 13]$, and $T=21$. I will start with $\sigma(1,1)=5$, then increment $j=2$. Now, I have $\sigma(1,2)=15$ and $j$ increments until $j$ reaches $j=4$. Now $i$ increments and we have $i=2$ and $j=4$ and then $j$ keeps increasing. I will never check $\sigma(2,2)$, right? But I guess that's useless to check, right?
Dec 5, 2023 at 18:52	comment	added	Steven		No. When $i$ increments leave $j$ to its previous value. Exactly one pointer increments in each iteration. The other is unaffected.
Dec 5, 2023 at 18:50	comment	added	zebda		When $i$ increments, $j$ should be set to $i$, right?
Dec 5, 2023 at 18:34	history	edited	Steven	CC BY-SA 4.0	deleted 102 characters in body
Dec 5, 2023 at 18:26	history	answered	Steven	CC BY-SA 4.0