Python- Algorithmic statement

Question

I want to write a program which does the follows : -

Sample Input:

3
10 4 18 2 6 19 24 1 20

Expected Output:

4 2 2 2 6 1 1

The input will from a file in which the first line will contain the window size N, the second line will contain a stream of numbers separated by space. You need to output the smallest numbers in each window separated by space.

This is what I wrote:-

with open ("file") as f1:
    n = int(f1.readline())
    numbers = f1.readline()

# converting the string of numbers into a list
numbers_list = map(int,numbers[:-1].split(' ')) 

# getting all the sub-lists of size n from the numbers_list and printing their respective minimum elements.
print [min(numbers_list[i:i+n]) for i in xrange(len(numbers_list)-n+1)] 

My o/p

[4, 2, 2, 2, 6, 1, 1]

Is there some better solution than this? Any optimized version of this solution.

Answer 1

map(min, [nums[x:x+window] for x in xrange(len(nums)-(window-1))])

However, this creates an intermediate list, so:

[min(nums[x:x+window]) for x in xrange(len(nums)-(window+1))] 

is actually better, which is what you currently have.

There is a more time efficient way, however, it would be more code. Once you have the min-value for a window, all you're doing is looking at the next slot, so all you need to do is compare the min value from the previous (window-1) elements to the next value. Whichever is smaller will be the next number in your results list. Repeat.

For example, if you have a four element list and your window is size 3. The first value in your results list will be the minimum of the first three elements, and the second value in your results list will be the minimum of the last three elements.

There's a two element overlap there. So you can save the minimum value of the last window-1 elements and compare that to the next value in the list to get the min value for the next window. Repeat.

With respect to the file handling,

with open ("file") as f1:
    n = int(f1.readline())
    numbers_list = map(int, f1.readline().split(' ')) 

is slightly more efficient.