Rolling median of all K-length ranges

Question

Given an array of integers of length N and an odd integer K, return N - K + 1 integers, where the ith integer represents the median of a K-length subarray starting from i.

You may write a full program or a function.

The input is N, K and the input array. You can take input in any reasonable form, and you don't have to take the length if it's unnecessary.

Sample test (input is in the form N, K, then array)

10 3
3 5 8 2 4 7 5 2 7 4

Output

5 5 4 4 5 5 5 4

How the output is obtained:

The first number is the median of the range [1, 3], or [1, 1 + K - 1]
The second number is the median of the range [2, 4]
...

This is code-golf, so shortest code wins! (In bytes.)

For those that want to test the efficiency of their solution, see the Sliding Window Median CSES problem. — Unmitigated, Commented Jul 7 at 2:37
@Unmitigated It's Charcoal so it's not going to win any speed awards but I thought I'd write a golfed O(NK²) answer and include a relatively less golfed O(NK) program. — Neil, Commented Jul 7 at 20:58
Algorithmically, it can be solved in O(N log N) time using two binary heaps, a balanced binary search tree, or a segment tree. — Bubbler, Commented Jul 8 at 1:06

lyxal · Accepted Answer · 2024-07-06 11:16:28Z

7

Jelly, 3 bytes

ṡÆṁ

Try it online!

Is vectorising median a good golflang design choice? I don't know. But it definitely helps here.

Takes the list then k.

Explained

ṡÆṁ⁡‎‎⁪⁡⁪⁠⁪⁡⁪‏‏⁡⁠⁡‌⁢‎‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏‏⁡⁠⁡‌
ṡ    # ‎⁡Get all overlaps in the list of length k
 Æṁ  # ‎⁢Find the median of each
💎

Created with the help of Luminespire.

answered Jul 6 at 11:16

lyxal

33.7k2 gold badges63 silver badges139 bronze badges

Add a comment |

pajonk · Accepted Answer · 2024-07-07 11:41:53Z

7

R, 45 39 bytes

Edit: -6 bytes thanks to @Dominic van Essen.

\(x,N,K)Map(\(i)median(x[1:K+i]),K:N-K)

Attempt This Online!

R + zoo, 15 bytes

zoo::rollmedian

Attempt This Online!

(Doesn't use the input N)

edited Jul 7 at 11:41

answered Jul 6 at 16:30

pajonk

17.1k3 gold badges25 silver badges71 bronze badges

\$\begingroup\$ I saw you'd answered, so didn't peek before having a go myself... but when I finally looked I saw what I'd got was pretty similar: 39 bytes \$\endgroup\$
– Dominic van Essen
Commented Jul 7 at 10:34
\$\begingroup\$ @DominicvanEssen thanks, that's better index management. \$\endgroup\$
– pajonk
Commented Jul 7 at 11:42

Add a comment |

chunes · Accepted Answer · 2024-07-06 10:31:42Z

6

Factor, 24 bytes

[ clump [ median ] map ]

Try it online!

answered Jul 6 at 10:31

chunes

25.3k3 gold badges22 silver badges53 bronze badges

Add a comment |

Mukundan314 · Accepted Answer · 2024-07-06 18:19:11Z

4

Python 3, 58 bytes

lambda n,x,k:[sorted(x[i:i+k])[k//2]for i in range(n-k+1)]

Try it online!

Python 3, 61 bytes

Does not require n

lambda x,k:[sorted(x[i:i+k])[k//2]for i in range(len(x)-k+1)]

Try it online!

answered Jul 6 at 18:19

Mukundan314

12.5k1 gold badge15 silver badges57 bronze badges

\$\begingroup\$ 53: lambda x,k:x[k-1:]and[sorted(x[:k])[k//2]]+f(x[1:],k) \$\endgroup\$
– no comment
Commented Jul 7 at 20:58
\$\begingroup\$ @nocomment that's amazing, I think you should post it as a separate answer. \$\endgroup\$
– Mukundan314
Commented Jul 8 at 6:02
\$\begingroup\$ Ok done. Btw is there a guide somewhere about when to suggest improvements and when to post a separate answer? I had been wondering about that already. It seems there's usually only one answer per language and I got the impression that that's the goal. \$\endgroup\$
– no comment
Commented Jul 8 at 8:35
\$\begingroup\$ @nocomment, No, there are no specific rules or guidelines that dictate when to suggest improvements versus posting a separate answer. It is mostly subjective and depends on the amount of effort you put in. The main reason I suggested posting your answer separately is because I spent quite a while trying to get a recursive version but couldn't succeed. \$\endgroup\$
– Mukundan314
Commented Jul 8 at 13:06

Add a comment |

Luis Mendo · Accepted Answer · 2024-07-06 20:27:44Z

4

Octave with Image Package, 31 bytes

@(x,k)median(im2col(x,[1 k]),1)

Try it online!

How it works

@(x,k) defines an anonymous function inputs x (row vector) and k (scalar).

im2col(x,[1 k]) produces sliding blocks from x of length k, arranged as columns of a matrix. For inputs x = [3 5 8 2 4 7 5 2 7 4], k = 3 this gives

3   5   8   2   4   7   5   2
5   8   2   4   7   5   2   7
8   2   4   7   5   2   7   4

median(...,1) computes the median along the first dimension, that is, vertically.

edited Jul 6 at 20:27

answered Jul 6 at 15:52

Luis Mendo

105k9 gold badges133 silver badges370 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2024-07-06 10:05:46Z

3

Vyxal, 4 bytes

lv∆ṁ

Try it Online!

l    # Get all overlapping slices of length k
 v∆ṁ # Take the median of each

answered Jul 6 at 10:05

emanresu A

39.1k5 gold badges95 silver badges224 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2024-07-06 10:15:27Z

3

JavaScript (Node.js), 67 bytes

x=>k=>g=n=>n<k?[]:[...g(n-1),x.slice(n-k,n).sort((p,q)=>p-q)[k>>1]]

Try it online!

JavaScript (Node.js), 76 71 bytes

Don't read n

x=>n=>x.flatMap(c=>++k<0?[]:x.slice(k,k+n).sort((p,q)=>p-q)[n>>1],k=-n)

Try it online!

Both functions can reduce 10 bytes if input as Uint32Array

edited Jul 6 at 10:15

answered Jul 6 at 9:53

l4m2

24.8k2 gold badges23 silver badges92 bronze badges

\$\begingroup\$ 57 bytes by taking a typed array as input. \$\endgroup\$
– Arnauld
Commented Jul 6 at 10:10

Add a comment |

Graham · Accepted Answer · 2024-07-06 12:55:28Z

3

APL+WIN, 30 bytes

Prompts for vector of numbers followed by k

(⌈.5×k)⌷¨(⊂¨⍒¨i)⌷¨i←(k←⎕),/v←⎕

Try it online! Thanks to Dyalog Classic

answered Jul 6 at 12:55

Graham

6,4061 gold badge14 silver badges11 bronze badges

Add a comment |

lyxal · Accepted Answer · 2024-07-06 13:58:14Z

3

Japt, 8 bytes

ãV ËÍgVz

Try it

ãV ËÍgVz     :Implicit input of array U & integer V
ãV           :Sub-arrays of U of length V
   Ë         :Map
    Í        :  Sort
     g       :  Get element at 0-based index
      Vz     :    V floor divided by 2

edited Jul 6 at 13:58

lyxal

33.7k2 gold badges63 silver badges139 bronze badges

answered Jul 6 at 12:17

Shaggy

42.2k4 gold badges34 silver badges94 bronze badges

Add a comment |

Aiden Chow · Accepted Answer · 2024-07-08 00:10:24Z

3

Desmos, 44 42 bytes

f(L,N,K)=[L[i-K+1...i].medianfori=[K...N]]

Try It On Desmos!

Try It On Desmos! - Prettified

edited Jul 8 at 0:10

answered Jul 7 at 1:20

Aiden Chow

13.7k1 gold badge16 silver badges54 bronze badges

Add a comment |

no comment · Accepted Answer · 2024-07-08 11:45:41Z

3

Python 3, 55 bytes

f=lambda x,k:x[k-1:]and[sorted(x[:k])[k//2]]+f(x[1:],k)

Try it online!

edited Jul 8 at 11:45

answered Jul 8 at 8:29

no comment

1515 bronze badges

\$\begingroup\$ Nice answer! Since the function references itself, the consensus is to include f= in the byte count. \$\endgroup\$
– Jitse
Commented Jul 8 at 11:31
\$\begingroup\$ @Jitse Oh ok, I moved it into the counting block. Is that the usual way? \$\endgroup\$
– no comment
Commented Jul 8 at 11:46
\$\begingroup\$ It is! Generally, if you need to access the function elsewhere in your code (recursively or otherwise), you include the variable assignment into the main code block. Otherwise you can leave it out (like in the case of the other Python answer). \$\endgroup\$
– Jitse
Commented Jul 8 at 12:11

Add a comment |

chunes · Accepted Answer · 2024-07-06 11:33:54Z

Uiua ^SBCS, 13 bytes

⊡⌊÷2⊸⧻⍉≡⊏⊸≡⍏◫

Try it!

⊡⌊÷2⊸⧻⍉≡⊏⊸≡⍏◫⁡‎‎⁪⁡⁪⁠⁪⁤⁡⁪‏‏⁡⁠⁡‌⁢‎‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏‏⁡⁠⁡‌⁣‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏‏⁡⁠⁡‌⁤‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏⁡⁠⁡‌
            ◫  # ‎⁡windows of length k
       ≡⊏⊸≡⍏   # ‎⁢sort each window
      ⍉        # ‎⁣transpose
⊡⌊÷2⊸⧻         # ‎⁤get the middle row

Jonathan Allan · Accepted Answer · 2024-07-06 14:50:20Z

2

Jelly, 4 3 bytes

ṡÆṁ

A dyadic Link that accepts the list of orderable numbers on the left and the infix length on the right and yields a list of numbers.

Try it online!

How?

ṡÆṁ - Link: list of numbers L, positive integer N
ṡ   - overlapping slices of {L} of length {N}
 Æṁ - median (vectorises)

edited Jul 6 at 14:50

answered Jul 6 at 14:25

Jonathan Allan

108k7 gold badges64 silver badges276 bronze badges

\$\begingroup\$ (from looking at the edit history) I was wondering if something like ⁹Ƥ would work until I also realised Æṁ vectorises. Very interesting behaviour \$\endgroup\$
– lyxal
Commented Jul 6 at 14:39
\$\begingroup\$ I was thinking that maybe ÆṁƤ would work taking the length from STDIN (like some other hypers), then stormed to use a ⁹. Also, I didn't realise you already posted this! (I will use the excuse that I am pretty under the weather right now.) \$\endgroup\$
– Jonathan Allan
Commented Jul 6 at 14:45
1

\$\begingroup\$ I hope you get better quickly. No worries about the duplicate, as that's allowed on CGSE, and shows that great minds think alike :p \$\endgroup\$
– lyxal
Commented Jul 6 at 14:47

Add a comment |

z.. · Accepted Answer · 2024-07-06 20:40:15Z

2

Google Sheets, 60 bytes

=MAP(SEQUENCE(B1-B2+1),LAMBDA(i,MEDIAN(OFFSET(A4,i-1,,B2))))

answered Jul 6 at 20:40

z..

8711 gold badge1 silver badge7 bronze badges

Add a comment |

Greg Martin · Accepted Answer · 2024-07-06 22:31:48Z

2

Wolfram Language (Mathematica), 23 bytes

Median/@##~Partition~1&

Try it online! Unnamed function expecting two arguments in the format [{3,5,8,2,4,7,5,2,7,4},3]. ##~Partition~1 is the same as Partition[#1,#2,1], which creates the array of length-#2 sublists of #1.

answered Jul 6 at 22:31

Greg Martin

15.8k4 gold badges20 silver badges71 bronze badges

Add a comment |

Neil · Accepted Answer · 2024-07-07 20:55:45Z

Charcoal, 43 bytes

ＮθＦＮ⊞υＮＦＥ…·θＬυ✂υκι¹«Ｗ›⊗Ｌ⁻ι⟦⌈ι⟧θ≔⁻ι⟦⌈ι⟧ι⟦Ｉ⌈ι

Try it online! Link is to verbose version of code. Takes K as the first input and N as the second input. Explanation: This was tricky without resorting to eval hacks to invoke external sort or median functions.

ＮθＦＮ⊞υＮ

Input K, N and the input array.

ＦＥ…·θＬυ✂υκι¹«

Loop over all of the slices of the input array of length K.

Ｗ›⊗Ｌ⁻ι⟦⌈ι⟧θ

While removing the highest remaining element from the slice would still leave the median in the remaining elements...

≔⁻ι⟦⌈ι⟧ι

... remove the highest remaining element.

⟦Ｉ⌈ι

Output the median, which is now the highest remaining element.

The above implementation is probably O(NK²). 65 bytes for a more efficient O(NK) version:

ＮθＦＮ⊞υＮ≔⟦⟧ζ≔⟦⟧εＦυ«ＦΦζ›κι⊞ε⊟ζ⊞ζιＷε⊞ζ⊟ε¿⁼Ｌζθ«≔⌕ζ§υⅉδ⟦Ｉ§ζ÷θ²⟧≔Φζ⁻λδζ

Try it online! Link is to verbose version of code. Takes K as the first input and N as the second input. Explanation:

ＮθＦＮ⊞υＮ

Input K, N and the input array.

≔⟦⟧ζ≔⟦⟧ε

Start with an empty sorted window and an empty temporary array.

Ｆυ«

Loop over the input array.

ＦΦζ›κι⊞ε⊟ζ⊞ζιＷε⊞ζ⊟ε

Insert the current element into the sorted position in the current window in O(K) time.

¿⁼Ｌζθ«

If the sorted window has length K, then...

≔⌕ζ§υⅉδ

Find the index of the element of the window to remove before the next loop.

⟦Ｉ§ζ÷θ²⟧

Output the middle element of the array.

≔Φζ⁻λδζ

Remove the element that's about to drop out of the window.

Kevin Cruijssen · Accepted Answer · 2024-07-08 06:51:38Z

2

05AB1E, 6 bytes

ŒIù€Åm

Try it online.

Explanation:

Œ       # Get all sublists of the first (implicit) input-list
 Iù     # Only keep the sublists of a length of the second input-integer
   €    # Map over each k-sized sublist:
    Åm  #  Calculate the median
        # (after which the resulting list is output implicitly)

answered Jul 8 at 6:51

Kevin Cruijssen

128k12 gold badges141 silver badges381 bronze badges

Add a comment |

G B · Accepted Answer · 2024-07-08 11:03:52Z

2

Ruby, 41 bytes

->l,n{l.each_cons(n).map{|a|a.sort[n/2]}}

Try it online!

answered Jul 8 at 11:03

G B

22.2k1 gold badge20 silver badges53 bronze badges

Add a comment |

chunes · Accepted Answer · 2024-07-06 19:38:09Z

1

Arturo, 47 bytes

$[a,k]->map 0..-size a k'i->median a\[i..i+k-1]

Needs modern Arturo so median isn't bugged. So no online link.

answered Jul 6 at 19:38

chunes

25.3k3 gold badges22 silver badges53 bronze badges

\$\begingroup\$ You run Arturo as an administrator? \$\endgroup\$
– Neil
Commented Jul 7 at 6:01

Add a comment |

Stack Exchange Network

Rolling median of all K-length ranges

19 Answers 19

Jelly, 3 bytes

Explained

R, 45 39 bytes

R + zoo, 15 bytes

Factor, 24 bytes

Python 3, 58 bytes

Python 3, 61 bytes

Octave with Image Package, 31 bytes

How it works

Vyxal, 4 bytes

JavaScript (Node.js), 67 bytes

JavaScript (Node.js), 76 71 bytes

APL+WIN, 30 bytes

Japt, 8 bytes

Desmos, 44 42 bytes

Python 3, 55 bytes

Uiua ^SBCS, 13 bytes

Jelly, 4 3 bytes

How?

Google Sheets, 60 bytes

Wolfram Language (Mathematica), 23 bytes

Charcoal, 43 bytes

05AB1E, 6 bytes

Ruby, 41 bytes

Arturo, 47 bytes

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

Hot Network Questions

Rolling median of all K-length ranges

19 Answers 19

Jelly, 3 bytes

Explained

R, 45 39 bytes

R + zoo, 15 bytes

Factor, 24 bytes

Python 3, 58 bytes

Python 3, 61 bytes

Octave with Image Package, 31 bytes

How it works

Vyxal, 4 bytes

JavaScript (Node.js), 67 bytes

JavaScript (Node.js), 76 71 bytes

APL+WIN, 30 bytes

Japt, 8 bytes

Desmos, 44 42 bytes

Python 3, 55 bytes

Uiua SBCS, 13 bytes

Jelly, 4 3 bytes

How?

Google Sheets, 60 bytes

Wolfram Language (Mathematica), 23 bytes

Charcoal, 43 bytes

05AB1E, 6 bytes

Ruby, 41 bytes

Arturo, 47 bytes

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

Related

Hot Network Questions

Uiua ^SBCS, 13 bytes

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