3
\$\begingroup\$

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.

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

6 Answers 6

1
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Commented Aug 31, 2018 at 23:47
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.