14
\$\begingroup\$

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 , so shortest code wins! (In bytes.)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ "rolling median" might be a good name for this \$\endgroup\$
    – emanresu A
    Commented Jul 6 at 10:04
  • 1
    \$\begingroup\$ For those that want to test the efficiency of their solution, see the Sliding Window Median CSES problem. \$\endgroup\$ Commented Jul 7 at 2:37
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Commented Jul 7 at 20:58
  • \$\begingroup\$ Algorithmically, it can be solved in O(N log N) time using two binary heaps, a balanced binary search tree, or a segment tree. \$\endgroup\$
    – Bubbler
    Commented Jul 8 at 1:06

19 Answers 19

7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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)

\$\endgroup\$
2
  • \$\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\$ Commented Jul 7 at 10:34
  • \$\begingroup\$ @DominicvanEssen thanks, that's better index management. \$\endgroup\$
    – pajonk
    Commented Jul 7 at 11:42
6
\$\begingroup\$

Factor, 24 bytes

[ clump [ median ] map ]

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\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\$ 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\$ Commented Jul 8 at 13:06
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 4 bytes

lv∆ṁ

Try it Online!

l    # Get all overlapping slices of length k
 v∆ṁ # Take the median of each
\$\endgroup\$
3
\$\begingroup\$

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

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

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

\$\endgroup\$
3
\$\begingroup\$

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

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

\$\endgroup\$
3
\$\begingroup\$

Python 3, 55 bytes

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

Try it online!

\$\endgroup\$
3
  • \$\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
2
\$\begingroup\$

Uiua SBCS, 13 bytes

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

Try it!

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

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)
\$\endgroup\$
3
  • \$\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\$ 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
2
\$\begingroup\$

Google Sheets, 60 bytes

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

enter image description here

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 43 bytes

NθFN⊞υNFE…·θLυ✂υκι¹«W›⊗L⁻ι⟦⌈ι⟧θ≔⁻ι⟦⌈ι⟧ι⟦I⌈ι

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.

NθFN⊞υN

Input K, N and the input array.

FE…·θLυ✂υκι¹«

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

W›⊗L⁻ι⟦⌈ι⟧θ

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

≔⁻ι⟦⌈ι⟧ι

... remove the highest remaining element.

⟦I⌈ι

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:

NθFN⊞υN≔⟦⟧ζ≔⟦⟧εFυ«FΦζ›κι⊞ε⊟ζ⊞ζιWε⊞ζ⊟ε¿⁼Lζθ«≔⌕ζ§υⅉδ⟦I§ζ÷θ²⟧≔Φζ⁻λδζ

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

NθFN⊞υN

Input K, N and the input array.

≔⟦⟧ζ≔⟦⟧ε

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

Fυ«

Loop over the input array.

FΦζ›κι⊞ε⊟ζ⊞ζιWε⊞ζ⊟ε

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

¿⁼Lζθ«

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

≔⌕ζ§υⅉδ

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

⟦I§ζ÷θ²⟧

Output the middle element of the array.

≔Φζ⁻λδζ

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

\$\endgroup\$
2
\$\begingroup\$

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

Ruby, 41 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Arturo, 47 bytes

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

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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