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.
O(NK²)
answer and include a relatively less golfedO(NK)
program. \$\endgroup\$