19
\$\begingroup\$

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

20 Answers 20

19
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Wait... How do you reduce something that has already been reduced? Isn't it just a singular element? \$\endgroup\$ – Cyoce Feb 15 '16 at 20:21
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Feb 15 '16 at 20:23
  • \$\begingroup\$ 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 \$\endgroup\$ – Cyoce Feb 15 '16 at 20:26
  • \$\begingroup\$ How many bytes should be counted as? 1 or 2? \$\endgroup\$ – njpipeorgan Feb 16 '16 at 2:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Dennis Feb 16 '16 at 3:08
7
\$\begingroup\$

CJam (11 bytes)

{ew::e>:e<}

Online demo

|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ A full program would be q~ew::e>:e<, which is also 11 bytes \$\endgroup\$ – GamrCorps Feb 15 '16 at 16:18
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ don't you mean each_cons? \$\endgroup\$ – Not that Charles Feb 16 '16 at 2:05
3
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

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;
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Being all positive: (x,y,M=Math.max)=>-M(...x.slice(y-1).map((a,i)=>-M(...x.slice(i,i+y)))) \$\endgroup\$ – edc65 Feb 15 '16 at 21:50
2
\$\begingroup\$

Julia, 51 bytes

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

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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`}`)

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 23 bytes

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

Test case

%[{1,2,3,4,5},3]
(* 3 *)
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Java 7, 128 126 124 bytes

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

Ungolfed & test code:

Try it here.

class M{
  static int c(int[] x, int n){
    int i = -1,
        j,
        q,
        m = 0;
    for(; i++ < x.length - n; m = m < 1 | q < m
                                           ? q
                                           : m){
      for(q = x[i], j = 1; j < n; j++){
        q = x[i+j] > q
             ? x[i+j]
             : q;
      }
    }
    return m;
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 1, 5, 3, 4 }, 2));
    System.out.println(c(new int[]{ 1, 2, 3, 4, 5 }, 3));
    System.out.println(c(new int[]{ 1, 1, 1, 1, 5 }, 4));
    System.out.println(c(new int[]{ 5, 42, 3, 23 }, 3));
  }
}

Output:

4
3
1
42
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Clojure, 51 bytes

#(apply min(for[p(partition %2 1 %)](apply max p)))
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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

|improve this answer|||||
\$\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.