Minimum of last k

Question

Write a function that takes two arguments: a number k and a list l, and that returns another list r such that r[i] = min(l[i-k+1:i]).

Examples

• Input k=2, l=1,2,3,4,5,6
• Ouput r=1,1,2,3,4,5
• Input k=3, l=-1,9,7,-9,8,3,5,0,12,1,2,3,-1,-2,-3
• Ouput r=-1,-1,-1,-9,-9,-9,3,0,0,0,1,1,-1,-2,-3

Constraints: O(len(l)) time complexity. Shortest code wins.

Answer 1

R, 75 bytes

f=function(k,l){r=l;for(i in 1:length(l));r[i]=min(l[max(1,(i-k+1)):i]);r}

Testing:

f(3, c(-1,9,7,-9,8,3,5,0,12,1,2,3,-1,-2,-3))
[1] -1 -1 -1 -9 -9 -9  3  0  0  0  1  1 -1 -2 -3

f(2, 1:6)
[1] 1 1 2 3 4 5

Not sure how to calculate the complexity of this.

Answer 2

SmileBASIC, 97 bytes

DEF M(K,L)DIM T[0],R[0]FOR I=1TO LEN(L)COPY T,L,MAX(I,K)-K,MIN(I,K)PUSH R,MIN(T)NEXT
RETURN R
END

Explanation: This line uses COPY dest[],source[],start,length to get part of the list into a temporary array:

COPY TEMP,LIST,MAX(I-K,0),MIN(I,K)

Example for a list of size 6, with K=3

I|start|length
1| 0   | 1
2| 0   | 2
3| 0   | 3
4| 1   | 3
5| 2   | 3
6| 3   | 3

Answer 3

K, 32 bytes

{|&/',/+((x*!_(#y)%x)+/:!x)_\:|y}

Translating the symbols to meaning, that is: reverse min over each flattened transpose (firstargument multipliedby enumerate truncate (countof secondargument) dividedby firstargument)add eachright enumerate first argument) cutby eachleft reverse secondargument

It's not as terse as J, as K is a simpler language, but it is still interesting

Answer 4

I come from the future (from this future) and, since I'm learning J, I thought I'd give it a try.

J, 21 bytes (non-competing)

<./"1@([,\$&_@<:@[,])

It prefixes the list with (K - 1) infinities, partitions it in overlapping chunks of length K and then computes the minimum of those. That's O(K*len(L)) if I'm not mistaken but, AFAICT, you need stateful computation to achieve O(len(L)) which isn't very idiomatic in J.

Usage:

   2 <./"1@([,\$&_@<:@[,]) 1 2 3 4 5 6
1 1 2 3 4 5

   3 <./"1@([,\$&_@<:@[,]) _1 9 7 _9 8 3 5 0 12 1 2 3 _1 _2 _3
_1 _1 _1 _9 _9 _9 3 0 0 0 1 1 _1 _2 _3

Answer 5

Matlab, 72 bytes

function[r]=f(k,l),for i=1:length(l),r(i)=min(l(max(1,i-k+1):i));end;end

Try it Online!

Answer 6

Haskell, 92 bytes

This is a restricted-complexity question asking specifically for a program that runs in O(len(l)) time, yet all the other answers in 7½ years have ignored that constraint. Here’s one that satisfies it.

g id
g _ _[]=[]
g h k l|(a,b)<-splitAt(k-1)l=h(scanl1 min a)++g(zipWith min$scanr1 min a)k b

Try it online!

How it works

Split the list into blocks of k − 1. Within each block, compute all prefix minima (with a left-to-right scan) and all suffix minima (with a right-to-left scan). Then any sublist of k numbers crosses exactly one block boundary, and can therefore be computed as the minimum of a suffix minimum from the first block and a prefix minimum from the second block.