# Subarray minimal average

I was solving this programming challenge about finding a subarray of at least size $2$ s.t. it has minimal average.

Suppose you have an array of integers $[a_1,a_2,...,a_k]$ you are looking for finding an index $i$ and a length $l$ s.t. $[\frac{a_i+a_{i+1}+...+a_{i+l-1}}{l}]$ is minimal.

You can easily solve this problem in $O(n^2)$ by looking at all the possible pairs $(i,l)$ and check for the best average. But you can cut down the time complexity to $O(n)$ if you realise that is it sufficient to look for subarray of length $2$ or $3$ only.

What I am struggling with is having a formal proof that given a sequence of number $[a_1,a_2,...,a_k]$ with average $A^1_k$ then there always exists a subsequence of length either

• $2$, $[a_i,a_{i+1}]$ with average $A^i_2$ or
• $3$, $[a_j,a_{j+1},a_{j+2}]$ with average $A^j_3$

s.t. $A^i_2 \le A^1_k$ OR $A^j_3 \le A^1_k$