1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

If you have a slice of length at least 4 (called the original slice from now on), you can partition it into 2 subslices of length at least 2 (say you take the first 2 elements as the first subslice, the remaining elements as the second). This gives you 2 slices that would also be possible as minimal slices.

Now the key insight is that smallest average of those 2 subslices is as most as big as the average of your original slice.

If it is smaller, then you are done, the original slice cannot have minimal average. If the smallest average is the same, then both subslices need to attain that value, that means including the first subslice. Since the first subslice has the same starting index as the original slice, you don't need to consider the original slice any more, because if it is minimal, its starting index will be considered when you consider the first subslice.

This proves that you don't need to consider slices of length 4 or more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.