4
\$\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 Feb 5 '11 at 8:34
  • 1
    \$\begingroup\$ Why the complexity contraint if the goal is shortest code? \$\endgroup\$ – hallvabo Feb 5 '11 at 13:42
  • 4
    \$\begingroup\$ I don't really understand the formula after sucht that..., can you explain it further to me? \$\endgroup\$ – FUZxxl Feb 6 '11 at 14:21
  • 1
    \$\begingroup\$ @FUZxxl: r[i] is minimum of the last k elements in l ending at i. \$\endgroup\$ – Alexandru Feb 6 '11 at 14:43
  • \$\begingroup\$ This task is probably as complex as a sort, so O(len(l)) can be obtained \$\endgroup\$ – edc65 Jan 26 '17 at 11:23
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 Feb 6 '11 at 14:42
  • \$\begingroup\$ I think you can remove the ; in length(l));r[i] \$\endgroup\$ – JAD Jan 26 '17 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 Aug 31 '18 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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