05_min_avg_two_slice.py

"""https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/"""

# Time complexity:
# Building and checking avg of slices of length 2 and 3 is O(1),
# Single pass is O(N) with O(1) work per element,
# Overall: O(N)

# My solution: I calculated prefix sums O(N) and then checked all
# possible slices with O(1) work per slice. However this has overall
# O(N^2) time complexity which does not pass the performance tests.

def solution(a: list[int]) -> int:
    """
    This solution was generated by gemini-3-pro (explanations added)

    Find starting position of the slice (contiguous part of array) with the minimal average.
    E.g. A = [4,2,2,5,1,5,8], the slice of range [1,2] has the minimal average of 2.
    Return starting position of min_avg slice.
    If multiple same min_avg, return the smallest starting position.
    """

    # If a slice can be decomposed into 2 slices, at least one of those slices
    # must have an average less than or equal to the average of the larger slice:
    #   1. One slice has a higher average and the other a lower average.
    #   2. Both slices have the same average.
    # So decomposing is SAFE (does not affect correctness).

    # Our base slice lengths, which can't be subdivided, are 2 and 3 (slices of length 1 are disallowed).
    # If slices of length 1 were allowed, we could return min(A) directly.

    n = len(a)
    min_avg = float('inf')
    min_start_pos = 0
    for i in range(n - 1):
        # Check slice of size 2
        avg2 = (a[i] + a[i + 1]) / 2
        if avg2 < min_avg:
            min_avg = avg2
            min_start_pos = i
        # Check slice of size 3
        if i < n - 2:
            avg3 = (a[i] + a[i + 1] + a[i + 2]) / 3
            if avg3 < min_avg:
                min_avg = avg3
                min_start_pos = i
    return min_start_pos