Compute minimax of an array

Question

Consider an array x such as [1 5 3 4] and a number n, for example 2. Write all length-n sliding subarrays: [1 5], [5 3], [3 4]. Let the minimax of the array be defined as the minimum of the maxima of the sliding blocks. So in this case it would be the minimum of 5, 5, 4, which is 4.

Challenge

Given an array x and a positive integer n, output the minimax as defined above.

The array x will only contain positive integers. n will always be at least 1 and at most the length of x.

Computation may be done by any procedure, not necessarily as defined above.

Code golf, fewest bytes wins.

Test cases

x, n, result

[1 5 3 4], 2 4
[1 2 3 4 5], 3 3
[1 1 1 1 5], 4 1
[5 42 3 23], 3 42

Answer 1

Dyalog APL, 4 bytes

⌊/⌈/

This is a monadic function train that expects array and integer as right and left arguments, resp.

Try it with TryAPL.

How it works

A train of two functions is an atop, meaning that the right one is called first (with both arguments), then the left one is called on top of it (with the result as sole argument).

A monadic f/ simply reduces its argument by f. However, if called dyadically, f/ is n-wise reduce, and takes the slice size as its left argument.

⌊/⌈/ Monadic function. Right argument: A (array). Left argument: n (list)
 ⌈/ N-wise reduce A by maximum, using slices of length n.
⌊/ Reduce the maxima by minimum.

• Cyoce: Wait... How do you reduce something that has already been reduced? Isn't it just a singular element?
• Dennis: @Cyoce The N-wise reduce yields an array of maxima. For example 2 ⌈/ 1 2 3 4 computes the maxima of (1 2) (2 3) (3 4), so it returns 2 3 4.
• Cyoce: Ok. I thought it meant that an N-wise reduce took the first N elements and reduce them with the function, e.g a 2-wise reduce is just a normal reduce
• njpipeorgan: How many bytes should ⌊ be counted as? 1 or 2?
• Dennis: @njpipeorgan That depends on the encoding. APL has its own legacy code page (which predates Unicode by several decades), and it encodes ⌊ and ⌈ as a single byte each.

Answer 2

CJam (11 bytes)

{ew::e>:e<}

Online demo

• GamrCorps: A full program would be q~ew::e>:e<, which is also 11 bytes

Answer 3

Ruby 39 bytes

->(x,n){x.each_slice(n).map(&:max).min}

Where x is the array and n is the number to chunk the array by.

• Not that Charles: don't you mean each_cons?

Answer 4

Oracle SQL 11.2, 261 bytes

SELECT MIN(m)FROM(SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND:2-1 FOLLOWING)c FROM(SELECT TRIM(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))))WHERE:2=c;

Un-golfed

SELECT MIN(m)
FROM (
 SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,
 SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)c
 FROM (
 SELECT TRIM(COLUMN_VALUE)a,rownum i 
 FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))
 )
 )
WHERE :2=c;

Answer 5

Pyth, 10 bytes

hSmeSd.:QE

Explanation:

 - autoassign Q = eval(input())
 .:QE - sublists(Q, eval(input())) - all sublists of Q of length num
 meSd - [sorted(d)[-1] for d in ^]
hS - sorted(^)[0]

Takes input in the form list newline int

Try it here!

Or run a Test Suite!

Or also 10 bytes

hSeCSR.:EE

Explanation:

 .:EE - sublists(Q, eval(input())) - all sublists of Q of length num 
 SR - map(sorted, ^)
 eC - transpose(^)[-1]
hS - sorted(^)[0]

Test Suite here

Answer 6

Jelly, 6 bytes

ṡ»/€«/

Try it online!

How it works

ṡ»/€«/ Main link. Left input: A (list). Right input: n (integer)
ṡ Split A into overlapping slices of length n.
 »/€ Reduce each slice by maximum.
 «/ Reduce the maxima by minimum.

Answer 7

JavaScript (ES6), (削除) 84 (削除ここまで) (削除) 83 (削除ここまで) 72 bytes

(x,y)=>Math.min(...x.slice(y-1).map((a,i)=>Math.max(...x.slice(i,i+y))))

Thanks to user81655 for helping shave off 11 bytes

• edc65: Being all positive: (x,y,M=Math.max)=>-M(...x.slice(y-1).map((a,i)=>-M(...x.slice(i,i+y))))

Answer 8

Perl 6, 32 bytes

{@^a.rotor($^b=>1-$b)».max.min}

Usage:

my &minimax = {@^a.rotor($^b=>1-$b)».max.min}
say minimax [1,5,3,4], 2; # 4
say minimax [1,2,3,4,5], 3; # 3
say minimax [1,1,1,1,5], 4; # 1
say minimax [5,42,3,23], 3; # 42

Answer 9

R, (削除) 41 (削除ここまで) 35 bytes

Requires zoo to be installed.

function(x,n)min(zoo::rollmax(x,n))

edit - 6 bytes by realizing zoo::rollmax exists!

Answer 10

Vyxal, 4 bytes

lvGg

Try it Online!

Why reduce by things when you can just vectorise.

Explained

lvGg
l # overlaps of input list of size input integer. 
 vG # maximum of each window
 g # minimum of that

Answer 11

Husk, 4 bytes

▼m▲さんかくX

Try it online!

Explanation

▼m▲さんかくX
 X each consecutive slice of length
 m▲さんかく maximum of each
▼ minimum

Answer 12

Jelly, 4 bytes

ṡṀ€Ṃ

Try it online!

Since Dennis' answer, the Ṁaximum and Ṃinimum monadic atoms have been added

Answer 13

Julia 0.6, 51 bytes

f(x,n)=min([max(x[i-n+1:i]...)for i=n:endof(x)]...)

Try it online!

Nothing too groundbreaking. This is a function that accepts an array and an integer and returns an integer. It just uses the basic algorithm. It would be a whole lot shorter if min and max didn't require splatting arrays into arguments.

We get each overlapping subarray, take the max, and take the min of the result.

Answer 14

MATL, 6 bytes

YCX>X<

Try it online!

YC % Implicitly input array and number. Build a matrix with columns formed
 % by sliding blocks of the array with size given by the number
X> % Maximum of each column
X< % Minimum of all maxima. Implicitly display

Answer 15

Python 3, 55 bytes.

lambda x,n:min(max(x[b:b+n])for b in range(len(x)-n+1))

Test cases:

assert f([1, 5, 3, 4], 2) == 4
assert f([1, 2, 3, 4, 5], 3) == 3
assert f([1, 1, 1, 1, 5], 4) == 1
assert f([5, 42, 3, 23], 3 ) == 42

Answer 16

Python 2, 50 bytes

f=lambda l,n:l[n-1:]and min(max(l[:n]),f(l[1:],n))

Recursively computes the minimum of two things: the max of the first n entries, and the recursive function on the list with first element removed. For a base case of the list having fewer than n elements, gives the empty list, which serves as infinity because Python 2 puts lists as greater than numbers.

Answer 17

Mathematica, 23 bytes

Min@BlockMap[Max,##,1]&

Test case

%[{1,2,3,4,5},3]
(* 3 *)

Answer 18

J, 9 bytes

[:<./>./\

Similar to the APL answer. >./\ applies >./ (maximum) to the (left arg)-subsets of the right arg. Then, <./ finds the minimum of that, since it's capped with [:.

Test cases

 f =: [:<./>./\
 2 f 1 5 3 4
4
 3 f 1 2 3 4 5
3
 3 f 1 1 1 1 5
1
 3 f 5 42 3 23
42

Answer 19

Factor, 34 bytes

[ clump [ supremum ] map infimum ]

Try it online!

Explanation

 ! { 1 5 3 4 } 2
clump ! { { 1 5 } { 5 3 } { 3 4 } }
[ supremum ] map ! { 5 5 4 }
infimum ! 4

Answer 20

05AB1E, 6 bytes

ŒIù€àß

Try it online or verify all test cases.

Explanation:

Π# Get all sublists of the (implicit) input-list
 Iù # Only keep those of a size equal to the second input
 ۈ # Get the maximum of each inner list
 ß # Pop and push the minimum of that
 # (after which the result is output implicitly)

Answer 21

Java 8, (削除) 128 (削除ここまで) (削除) 126 (削除ここまで) (削除) 124 (削除ここまで) 105 bytes

a->n->{int r=0,m,j,t,i=-1;for(;i++<a.length-n;r=r<1|m<r?m:r)for(m=j=0;j<n;m=t>m?t:m)t=a[i+j++];return r;}

Try it online.

Explanation:

a->n->{ // Method with Integer-array & Integer as parameters
 // and Integer return-type
 int r=0, // Result-integer, starting at 0
 m, // Max-integer, uninitialized
 j,t, // Temp integers
 i=-1;for(;i++<a.length-n // Loop `i` in the range (-1,length-n]:
 ; // After every iteration:
 r= // Change the result to:
 r<1 // If the result is 0 (first iteration),
 |m<r? // or the max is smaller than the result:
 m // Change the result to this max
 : // Else:
 r) // Keep it unchanged
 for(m= // Reset the max to 0
 j=0;j<n // Inner loop `j` in the range [0,n):
 ; // After every iteration:
 m=t>m?t:m) // Set `m` to the max of `m` and `t`
 t=a[i+j++]; // Set `t` to the `i+j`'th item of the array
 return r;} // After the nested loops, return the result

Answer 22

Rust, 46 bytes

|s,n|s.windows(n).map(|a|a.iter().max()).min()

Try it online!

Takes in a &[u32] and returns an Option<Option<&u32>>. The result will be Some(Some(&minimax)) so long as valid input is supplied.

Answer 23

Burlesque, 7 bytes

CO)>]<]

Try it online!

CO # Sliding window length N
)>] # Map max of block
<] # Min of result

Answer 24

Julia 1.0, 48 bytes

x\n=minimum(n:length(x).|>i->max(x[i-n+1:i]...))

Try it online!

based on Alex A.'s answer

Answer 25

JavaScript (ES6), 70 bytes

x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max

Using currying, this function saves 2 bytes from the previous answer.

Demo

f=x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max
a=[[[1,5,3,4],2,4],[[1,2,3,4,5],3,3],[[1,1,1,1,5],4,1],[[5,42,3,23],3,42]]
document.write(`<pre>${a.map(r=>`${f(r[0])(r[1])==r[2]?'PASS':'FAIL'} ${r[1]}=>${r[2]}`).join`\n`}`)

Answer 26

Racket 84 bytes

(λ(l i)(apply min(for/list((j(-(length l)(- i 1))))(apply max(take(drop l j) i)))))

Ungolfed:

(define f
 (λ (l i)
 (apply min (for/list ((j (- (length l)
 (- i 1))))
 (apply max (take (drop l j) i))
 ))))

Testing:

(f '[1 5 3 4] 2)
(f '[1 2 3 4 5] 3)
(f '[5 42 3 23] 3)

Output:

4
3
42

Answer 27

Clojure, 51 bytes

#(apply min(for[p(partition %2 1 %)](apply max p)))

Answer 28

SmileBASIC, 68 bytes

M=MAX(X)DIM T[N]FOR I=.TO LEN(X)-N-1COPY T,X,I,N
M=MIN(M,MAX(T))NEXT

Nothing special here. Inputs are X[] and N

Answer 29

T-SQL, 131 bytes

SELECT top 1max(iif(a<c,c,a))FROM x y
CROSS APPLY(SELECT a c FROM x WHERE y.b<b and b<y.b+@)z
GROUP BY b
HAVING-@=~sum(1)ORDER BY 1

Try it online

Answer 30

R, 64 bytes

function(x,n)min(apply(matrix(x,l<-sum(x|1)+1,n)[n:l-n,],1,max))

Try it online!

Answer without using zoo.