# Minimum of last k [closed]

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.

• Please use the code-golf tag when asking for shortest code. Commented Feb 5, 2011 at 8:34
• Why the complexity contraint if the goal is shortest code? Commented Feb 5, 2011 at 13:42
• I don't really understand the formula after sucht that..., can you explain it further to me? Commented Feb 6, 2011 at 14:21
• @FUZxxl: r[i] is minimum of the last k elements in l ending at i. Commented Feb 6, 2011 at 14:43
• This task is probably as complex as a sort, so O(len(l)) can be obtained Commented Jan 26, 2017 at 11:23

# 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.

• Complexity is O(N*K) Commented Feb 6, 2011 at 14:42
• I think you can remove the ; in length(l));r[i]
Commented Jan 26, 2017 at 11:29

# 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


# 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

• Welcome to PPCG! We actually don't require "non-competing" anymore. Our policy has changed in the last year. You may answer using any language you want. Commented Aug 31, 2018 at 23:47

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 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  ## 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! # Haskell, 92 bytes This is a 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.