11
\$\begingroup\$

Inspired by this question and refined by Luis Mendo.

Challenge

Given a 2D matrix of integers, each row has a maximum value. One or more elements of each row will be equal to the maximum value of their respective row. Your goal is to determine which column(s) contain the most entries which are equal to their respective row's maximum value as well as the number of row-wise maxima found in these columns.

Input

  • The input will be a non-empty M x N matrix (M > 0 and N > 0) in whatever form is well-suited to your language of choice.

Output

  • Your program should return the index of each column containing the maximum number of row-wise maxima (either as separate values or a list). Either 0- or 1-based indexing can be used (specify in your description).
  • Your program should also return the number of maxima that were present in these columns (a single number).
  • The order/format of the output is flexible but should be explained in the text accompanying your answer.

Additional Information

  • All entries in the input matrix will be positive integers.
  • If the maximum value of a row is shared by multiple elements in that row, all occurrences of that value count towards their columns' total.
  • If multiple columns contain the same number of maxima, you should return a list of all columns which had this number of maxima.

An Example

Consider input

 7  93
69  35
77  30     

Row 1 has maxium 93, which occurs only once, namely at column 2. Row 2: occurs at column 1. Row 3: also at column 1. So the winner column is 1, with 2 maxima. Thus the output will be [1] [2]. If we change the input to

 7  93
69  35
77  77

the output will be [1 2] [2], because both columns have 2 maxima.

Test Cases

input                 =>    output ( [1-based index array], [nMaxima] )
----------------------------------------------
 7  93
69  35                =>    [1], [2]
77  30

 7  93
69  35                =>    [1 2], [2]
77  77     

1   2   3   4         =>    [4], [2]
5   6   7   8

16   2   3  13
 5  11  10   8        =>    [1  2  4], [1]
 9   7   6  12    

 1   1   1   1        =>    [1  2  3  4], [1]

25   6  13  25        =>    [1  4], [1]

1
2
3                     =>    [1], [4] 
4

100                   =>    [1], [1]

Scoring

This is , the shortest code in bytes wins. Tiebreaker goes to the earlier answer.

Leaderboard

Below is a stack snippet for analyzing all entries.

var QUESTION_ID=80788,OVERRIDE_USER=51939;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • 7
    \$\begingroup\$ Fun fact; the Dutch queen is called Maxima, so technically we can only have 1 Maxima. \$\endgroup\$ – Bassdrop Cumberwubwubwub May 27 '16 at 10:37
  • 1
    \$\begingroup\$ Fun fact; there is also an opensource CAS called Maxima. \$\endgroup\$ – flawr May 27 '16 at 11:57

14 Answers 14

3
\$\begingroup\$

Jelly, 9 bytes

="Ṁ€SµM,Ṁ

Input is a 2D list, output is a pair: a list of 1-based indices and the maximal number of maxima.

Try it online! or verify all test cases.

How it works

="Ṁ€SµM,Ṁ  Main link. Argument: M (matrix)

  Ṁ€       Apply maximum to each row.
="         Zipwith equal; compare the entries of the nth row with its maxmium.
    S      Sum; reduce across columns to count the maxima in each row.
     µ     Begin a new, monadic link. Argument: A (list of maxima)
      M    Yield all indices with maximal value.
        Ṁ  Yield the maximum of A.
       ,   Pair the results to both sides.
\$\endgroup\$
3
\$\begingroup\$

J, 27 bytes

((I.@:=;])>./)@(+/@:=>./"1)

This is a monadic verb, used as follows in the case of the second example:

   f =: ((I.@:=;])>./)@(+/@:=>./"1)
   m =: 3 2 $ 7 93 69 35 77 77
   f m
+---+-+
|0 1|1|
+---+-+

The output consists of two boxes, and uses 0-based indexing. Try it here!

Explanation

((I.@:=;])>./)@(+/@:=>./"1)  Input is m.
(            )@(          )  Composition: apply right hand side, then left hand side.
                     >./"1   Take maximum of each row of m.
                    =        Replace row maxima by 1 and other values by 0,
                +/@:         then take sum (number of maxima) on each column.
                             The result is the array of number of row maxima in each column.
          >./                Compute the maximum of this array
 (     ;])                   and put it in a box with
  I.@:=                      the indices of those entries that are equal to it.
\$\endgroup\$
3
\$\begingroup\$

MATL, 17 bytes

vH3$X>G=XstX>tb=f

The first output is the max number of maxima and the second output is the columns in which this occured (1-based indexing).

Try it Online!

Explanation

v       % Vertically concatenate everything on the stack (nothing), yields []
        % Implicitly grab the input
H       % Push the number 2 to the stack
3$X>    % Compute the maximum value of each row (along the second dimension)
G       % Explicitly grab input again
=       % Compare each row of the input to the row-wise max (automatically broadcasts). 
Xs      % Sum the number of matches in each column
t       % Duplicate the array
X>      % Determine the max number of maxima in all columns
t       % Duplicate this value
b=f     % Find the index of the columns which had the maximum number of maxima
        % Implicitly display stack contents
\$\endgroup\$
3
\$\begingroup\$

MATL, 17 bytes

!tvX>!G=5#fFTT#XM

Input is a 2D array, with rows separated by semicolons. So the inputs for the test cases are

[7 93; 69 35; 77  30]
[7 93; 69 35; 77  77]
[1 2 3 4; 5 6 7 8]
[16 2 3 13; 5 11 10 8; 9 7 6 12]
[1 1 1 1]
[25 6 13 25]
[1; 2; 3; 4]
[100]

Output is: first the maximum amount of maxima, then one or more column indices.

Try it online!

Explanation

This uses a different approach from Suever's answer.

First a matrix of logical values (true and false) is computed, where true indicates the presence of a row-maximum. Then the column indices of the true values are extracted into a vector. Finally, the mode of that vector is computed (maximum number of maxima), along with all values that are the most frequent (desired column indices).

!        % Implicit input. Transpose
tv       % Duplicate. Concatenate vertically. This forces next function (max)
         % to work along columns even if input is a row vector
X>       % Maximum of each column (gives row vector)
!        % Transpose into column vector
G        % Push input again
=        % Test for equality, with broadcast. Gives matrix of true and false
5#f      % Column indices of true values, as a column vector
FTT#XM   % Mode of that vector, and all values that occur maximum number of times
         % Implicit display
\$\endgroup\$
3
\$\begingroup\$

Pyth, 20 19 17 bytes

1 byte thanks to @Suever.

1 byte thanks to @Jakube.

{MC.MhZrSsxLeSdQ8

Test suite.

Output is 0-indexed.

Order is reversed.

All inputs

[[7,93],[69,35],[77,30]]
[[7,93],[69,35],[77,77]]
[[1,2,3,4],[5,6,7,8]]
[[16,2,3,13],[5,11,10,8],[9,7,6,12]]
[[1,1,1,1]]
[[25,6,13,25]]
[[1],[2],[3],[4]]
[[100]]

All outputs

[[2], [0]]

[[2], [0, 1]]

[[2], [3]]

[[1], [0, 1, 3]]

[[1], [0, 1, 2, 3]]

[[1], [0, 3]]

[[4], [0]]

[[1], [0]]

How it works

{MC.MhZrSsxLeSdQ8

               Q   Yield input.
           L       For each array in input (as d):
            eSd      Yield maximum of d.
          x          Yield the 0-indexed indices of the maximum in d.
         s          Flatten.
        S           Sort.
       r         8  Run-length encoding.
                    Now the array is:
                      [number of maxima in column, index of column]
                      for all the columns
   .MhZ             Yield the sub-arrays whose first element is maximum.
                     The first element of each sub-array
                     is "number of maxima in column".
                     Now the array is:
                       [number of maxima in column, index of column]
                       for all the required columns
  C                 Transpose.
                    Now the array is:
                      [[number of maxima in each column],
                       [index of each required column]]
                    Note that every element in the
                    first sub-array is the same.
{M                  Deduplicate each.
\$\endgroup\$
3
\$\begingroup\$

CJam, 38 35 31 bytes

2 bytes fewer thanks to @FryAmTheEggMan, with help also from @quartata. Thanks also to @Dennis for removing 4 more bytes.

q~_::e>.f=:.+_:e>_@f{=U):Ua*~}p

Input is of the form

[[7 93] [69 35] [77 77]]

Output is an array of 1-based column indices and a number.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ q~_::e>.f=:.+_:e>_@f{=U):Ua*~}p saves a few bytes. Turning it into a code block would save 1 more. \$\endgroup\$ – Dennis May 28 '16 at 5:25
  • \$\begingroup\$ @Dennis Thanks! Now I need to understand what {=U):Ua*~} does... \$\endgroup\$ – Luis Mendo May 28 '16 at 10:26
2
\$\begingroup\$

Pyke, 17 bytes

FDSeRmq),AsDSe
R%

Try it here!

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

Python 2, 106 bytes

x=map(sum,zip(*[map(max(r).__eq__,r)for r in input()]))
m=max(x);print[i for i,n in enumerate(x)if n==m],m

Input is a 2D list of floats, output is a pair: a list of 0-based indices and an integer.

Test it on Ideone.

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

Julia, 54 bytes

f(x,m=maximum,t=sum(x.==m(x,2),1))=find(t.==m(t)),m(t)

Input is a matrix, output is a pair: a list of 1-based indices and the maximal number of maxima.

Try it online!

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

JavaScript (ES6), 111 bytes

a=>[m=Math.max(...a=a[0].map((_,i)=>a.map(a=>c+=a[i]==Math.min(...a),c=0)|c)),[...a.keys()].filter(i=>a[i]==m)]

Returns an array of two elements; the first is the maximum count of maxima, the second is the array of zero-indexed columns with that count.

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

Octave, 47 46 bytes

@(r){m=max(s=sum(r==max(r,0,2),1)),find(s==m)}

This creates an anonymous function that automatically assigns itself to ans and can be run using ans([1 2 3; 4 5 6]). It returns a two-element cell array where the first element is the maximum number of maxima and the second is the 1-based index of the columns containing these maxima.

All test cases

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

Python 3, 142 bytes

The algorithm here is basically, go through each row and increase the score of columns that have the max of that row. Then find the max of the scores and find the columns that have that max score and return them. Columns are 1-indexed. I tried one-lining this into a lambda, but with generating the scores column by column it was 153 bytes.

def f(r):
    s=[0]*len(r[0]);e=enumerate
    for x in r:
        for i,j in e(x):
            s[i]+=(0,1)[j==max(x)]
    m=max(s);return[i+1for i,j in e(s)if j==m],m

Test Cases

x=[[7, 93],
[69, 35],              
[77, 30]]

print(f(x)) #=>    [[1], 2]

x=[[ 7, 93],
[69, 35],             
[77, 77]]    

print(f(x)) #=>    [[1 2], 2]

x=[[1,  2,   3,  4],        
[5,  6,  7,  8]]

print(f(x)) #=>    [[4], 2]

x=[[16,  2,  3, 13],
 [5, 11, 10,  8],      
 [9,  7, 6, 12]]

print(f(x)) #=>    [[1  2  4], 1]

x=[[1,  1,  1,  1]]      

print(f(x)) #=>    [[1  2  3  4], 1]

x=[[25,   6,  13,  25]]        

print(f(x)) #=>    [[1  4], 1]

x=[[1],
[2],
[3],                   
[4]]

print(f(x)) #=>    [[1], 4] 

x=[[100]]                   

print(f(x)) #=>    [[1], 1]
\$\endgroup\$
1
\$\begingroup\$

Clojure, 150 bytes

(fn[M](let[F(dissoc(frequencies(mapcat(fn[r](map-indexed #(if(=(apply max r)%2)%)r))M))nil)m(apply max(vals F))][(map first(filter #(#{m}(% 1))F))m]))

Man that is long, I've got a feeling this could be simplified a lot. At least it produces the correct output.

[(f [[ 7  93][69  35][77  30]])
 (f [[ 7  93][69  35][77  77]])
 (f [[16   2   3  13][5  11  10   8][9   7   6  12]])]

[[(0) 2] [(1 0) 2] [(0 1 3) 1]]
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 14 (or 12) bytes

εZQ}øOZ©Qƶ0K®‚

Outputs in the format [[1-indexed columns-list], maxima].

Try it online or verify all test cases.

If it's allowed to have items 0 in the columns-list which we ignore, it could be 2 bytes less by removing the 0K:

Try it online or verify all test cases.

Explanation:

ε               # Map each row in the (implicit) input-matrix:
 Z              #  Get the maximum of the row (without popping)
  Q             #  Check for each value in this row if its equal to the row-maximum
   }ø           # After the map: zip/transpose the matrix; swapping rows/columns
     O          # Take the sum of each inner list (the truthy/falsey values of the columns)
      Z         # Get the maximum column-sum (without popping)
       ©        # Store it in the register (without popping)
        Q       # Check for each column-sum if its equal to this maximum
         ƶ      # Multiply each truthy/falsey value in the list by its 1-based index
          0K    # Remove all 0s
            ®‚  # Pair the resulting list with the maximum we stored in the register
                # (and output the result implicitly)
\$\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.