Introduction

The Codility MinAvgTwoSlice problem asks for the starting index of the slice with the smallest average. The trick is not brute force; the key observation is that the minimum-average slice must have length 2 or 3, which turns an apparently hard problem into a linear scan.

Why the naive approach is too slow

A direct solution would examine every possible slice, compute its average, and keep the smallest one.

That is too expensive because there are O(n^2) slices, and computing each average directly can make it even worse.

The interview value of this problem is recognizing a mathematical shortcut rather than optimizing brute force mechanically.

The key observation

If a slice has length 4 or more, it can be split into smaller parts. If that larger slice had the minimum average, then at least one of those smaller parts must have an average less than or equal to the whole slice.

From that reasoning, it follows that the global minimum-average slice must show up among slices of size 2 or 3.

That means you only need to check:

• every pair A[i], A[i+1]
• every triple A[i], A[i+1], A[i+2]

Once you know that, the solution becomes O(n).

Python implementation

Here is a standard solution.

1def min_avg_two_slice(A):
2    min_index = 0
3    min_avg = (A[0] + A[1]) / 2
4
5    for i in range(len(A) - 1):
6        avg2 = (A[i] + A[i + 1]) / 2
7        if avg2 < min_avg:
8            min_avg = avg2
9            min_index = i
10
11        if i < len(A) - 2:
12            avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3
13            if avg3 < min_avg:
14                min_avg = avg3
15                min_index = i
16
17    return min_index
18
19
20print(min_avg_two_slice([4, 2, 2, 5, 1, 5, 8]))

This returns 1, which is the expected answer for the classic example.

Why checking only 2 and 3 works

The proof intuition is worth understanding because that is the actual heart of the challenge.

A slice of length 4 can be split into two slices of length 2. A slice of length 5 can be split into a slice of length 2 and a slice of length 3. More generally, any longer slice can be decomposed into pieces of size 2 and 3.

If all those smaller pieces had strictly larger averages than the whole slice, their weighted combination could not produce the whole slice's smaller average. Therefore at least one component must have an average no larger than the full slice.

That is enough to justify scanning only pairs and triples.

Tie handling

Codility usually expects the smallest starting position when several slices have the same minimum average. The implementation above naturally preserves the first index because it only updates when it finds a strictly smaller average.

That is a small but important detail.

Complexity

The algorithm visits each array position once and does constant work per position. That gives:

• time complexity O(n)
• extra space O(1)

This is exactly the kind of performance Codility expects.

Common Pitfalls

A common mistake is trying prefix sums plus all slice lengths. Prefix sums help average calculation, but they do not fix the O(n^2) number of slices.

Another issue is forgetting to check slices of length 3. The answer is not always a pair.

It is also easy to update the answer incorrectly on ties and accidentally return a later index instead of the earliest valid one.

Summary

• The minimum-average slice problem has a linear-time solution.
• The crucial insight is that the minimum slice must have length 2 or 3.
• Scan every pair and every triple, keeping the smallest average seen.
• Preserve the earliest index when averages tie.
• The real challenge is spotting the proof idea, not writing the loop.