An answer to this question on Stack Overflow.

Question

I'm trying to solve this problem in Python3. I know how to find min1 and min2, but I cannot guess how to search 5 elements in a single pass.

Problem Statement

The input program serves measurements performed by a device at intervals of 1 minute. All data are in natural numbers not exceeding 1000. The problem is to find the smallest sum of the squares of two measurements performed at intervals not less than 5 minutes apart. The first line will contain one natural number -- the number of measurements N. It is guaranteed that 5 < N <= 10000. Each of the following N lines contains one natural number -- the result of the next measurement.

Your program should output a single number, the lowest sum of the squares of two measurements performed at intervals not less than 5 minutes apart.

Sample input: 9 12 45 5 4 21 20 10 12 26

Expected output: 169

Answer

Try this:

#!/usr/bin/env python3
import queue
inp = [9,12,45,5,4,21,20,10,12,26]
q        = queue.Queue()                         #Make a new queue
smallest = False                                 #No smallest number, yet
best     = False                                 #No best sum of squares, yet
for x in inp:
  q.put(x)                                       #Place current element on queue
  #If there's an item from more than five minutes ago, consider it
  if q.qsize()>5:
    temp = q.get()    #Pop oldest item from queue into temporary variable
    if not smallest:  #If this is the first item more than 5 minutes old
      smallest = temp #it is the smallest item by default
    else:             #otherwise...
      smallest = min(temp,smallest) #only store it if it is the smallest yet
    #If we have no best sum of squares or the current item produces one, then
    #save it as the best
    if (not best) or (x*x+smallest*smallest<best):
      best = x*x+smallest*smallest
print(best)

The idea is to walk through the queue keeping track of the smallest element we have seen yet which is older than five minutes and comparing it against the newest element keeping track of the smallest sum of squares as we go.

I think you'll find the answer to be pretty intuitive if you think about it.

The algorithm operates in O(N) time.