Consider a round-robin tournament, in which each contestant plays one game against every other contestant. There are no draws, so every game has a winner and a loser. A contestant A is a king of the tournament, if for every other contestant B, either A beat B, or A beat another contestant C who in turn beat B. It can be shown that every tournament has at least one king (although there may be several). In this challenge, your task is to find the kings of a given tournament.

Input and output

Your input is an N × N boolean matrix T, and optionally the number N ≥ 2 of contestants. Each entry T[i][j] represents the outcome of the game between contestants i and j, with value 1 representing a win for i and 0 a win for j. Note that T[i][j] == 1-T[j][i] if i != j. The diagonal of T consists of 0s.

Your output shall be the list of kings in the tournament that T represents, using either 0-based or 1-based indexing. The order of the kings is irrelevant, but there should not be duplicates.

Both input and output can be taken in any reasonable format.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

These test cases use 0-based indexing. For 1-based indexing, increment each output value.

 2 [[0,0],[1,0]] -> [1]
 3 [[0,1,0],[0,0,0],[1,1,0]] -> [2]
 3 [[0,1,0],[0,0,1],[1,0,0]] -> [0,1,2]
 4 [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,1,1,0]] -> [0]
 4 [[0,1,1,0],[0,0,1,0],[0,0,0,1],[1,1,0,0]] -> [0,2,3]
 5 [[0,1,0,0,1],[0,0,0,0,1],[1,1,0,0,0],[1,1,1,0,1],[0,0,1,0,0]] -> [3]
 5 [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,0,0],[0,0,1,0,1],[1,0,1,0,0]] -> [0,1,4]
 5 [[0,0,0,0,0],[1,0,1,1,0],[1,0,0,0,1],[1,0,1,0,1],[1,1,0,0,0]] -> [1,3,4]
 6 [[0,0,0,0,0,0],[1,0,1,1,0,0],[1,0,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,1],[1,1,1,0,0,0]] -> [1,2,3,4,5]
 6 [[0,0,1,1,1,0],[1,0,0,1,1,1],[0,1,0,0,1,0],[0,0,1,0,0,1],[0,0,0,1,0,1],[1,0,1,0,0,0]] -> [0,1,2,3,5]
 6 [[0,1,1,0,0,1],[0,0,0,1,0,1],[0,1,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,0],[0,0,1,0,1,0]] -> [0,1,2,3,4,5]
 8 [[0,0,1,1,0,1,1,1],[1,0,1,0,1,1,0,0],[0,0,0,1,1,0,0,0],[0,1,0,0,0,1,0,0],[1,0,0,1,0,1,0,0],[0,0,1,0,0,0,1,0],[0,1,1,1,1,0,0,1],[0,1,1,1,1,1,0,0]] -> [0,1,4,6,7]
20 [[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1],[1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1],[0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1],[0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1],[1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1],[0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1],[0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0],[1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0],[1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1],[1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1],[1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0],[0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1],[1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1],[0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1],[0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1],[0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1],[0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1],[1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]] -> [0,1,3,4,5,7,8,11,15,17,18]
  • \$\begingroup\$ (Are there any run time or memory limits?) Nevermind. I completely misunderstood the spec. \$\endgroup\$
    – Dennis
    Mar 28, 2016 at 18:27
  • \$\begingroup\$ @Dennis Nope. As long as your program would theoretically work given unlimited time and memory, you're fine. \$\endgroup\$
    – Zgarb
    Mar 28, 2016 at 18:30
  • \$\begingroup\$ Just to clarify: T[a][b] is the same match as T[b][a] but viewed from opposite angle, so T[a][b] == !T[b][a] \$\endgroup\$
    – edc65
    Mar 28, 2016 at 21:04
  • \$\begingroup\$ @edc65 That's a good observation. I edited it into the challenge. \$\endgroup\$
    – Zgarb
    Mar 28, 2016 at 21:10

6 Answers 6


Matlab, 36 35 29 bytes


Let us find out if i is a king. Then for each j the value T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1. But the second condition can also be replaced by sum_over_k(T[i][k] * T[k][l])>0, but this is just an entry of the matrix T*T (if you consider T as a matrix). The OR can then be replayed by adding T to that result, so we just have to check if n-1 values of the row i of T*T+T are greater than zero, to see whether i is king. This is exactly what my function does.

(This is MATLAB, so the indices are 1-based.)

The MATLAB matrices should be encoded with semicolons as line delimiters:

  • \$\begingroup\$ You can probably save a few bytes taking the number of contestants as input, instead of doing size(T,1) \$\endgroup\$
    – Luis Mendo
    Mar 28, 2016 at 22:06

Jelly, 13 12 11 bytes


Output is 1-based. Try it online!

Alternatively, using bitwise operators instead of array manipulation:


Again, output is 1-based. Try it online!


For contestant A, we can find all B such that A beat C beat B by taking all rows that correspond to a C such that C beat A. Ifr the Bth entry of the Cth is 1, we have that C beat B.

If we compute the logical ORs of all corresponding entries of the selected columns, we get a a single vector indicating whether A beat B by transitivity or not. Finally, ORing the resulting vector with the corresponding row of the input matrix gives Booleans whether A beat B, either by transitivity or directly.

Repeating this for every row, we count the number of 1's in each vector, therefore computing the amount of contestants each A beat. Maximal counts correspond to kings of the tournament.

How it works

a"€¹o/€oḅ1M  Main link. Argument: M (matrix)

   ¹         Yield M.
  €          For each row of M:
a"           Take the logical AND of each entry of that row and the corr. row of M.
    o/€      Reduce each resulting matrix by logical OR.
       o     Take the logical OR of the entries of the resulting maxtrix and the
             corr. entries of M.
        ḅ1   Convert each row from base 1 to integer, i.e. sum its elements.
          M  Get all indices of maximal sums.
×Ḅ|/€|ḄBS€M  Main link. Argument: M (matrix)

 Ḅ           Convert each row of M from base 2 to integer. Result: R
×            Multiply the entries of each column of M by the corr. integer.
  |/€        Reduce each row fo the resulting matrix by bitwise OR.
     |Ḅ      Bitwise OR the results with R.
       BS€   Convert to binary and reduce by sum.
             This counts the number of set bits for each integer.
          M  Get all indices of maximal popcounts.
  • 1
    \$\begingroup\$ You know, people keep posting these and saying x "bytes", but is "ḅ" really encoded in 1 byte in any standard encoding? Sorry, but I find these hyper-condensed stack-based languages completely uninteresting because it feels like cheating to just assign every conceivable function to a unicode character. \$\endgroup\$
    – MattPutnam
    Mar 28, 2016 at 19:26
  • 2
    \$\begingroup\$ @MattPutnam Jelly uses its own custom encoding. (Also it isn't stack-based) \$\endgroup\$ Mar 28, 2016 at 19:27
  • 2
    \$\begingroup\$ @MattPutnam I've had similar sentiments, but they don't detract at all from traditional golfing. No one looks down on the traditional languages just because these exist, and unlike other SE sites, this doesn't exactly have the 'this answer is obvjectively better than that answer'. Also, while technically not disallowed, they don't alter the language to support a question (although they may, after the fact, realize a useful shortcut for future questions and make that an operation). \$\endgroup\$
    – corsiKa
    Mar 28, 2016 at 19:31
  • \$\begingroup\$ Why do these algorithms output the kings? \$\endgroup\$
    – xnor
    Mar 28, 2016 at 20:01
  • \$\begingroup\$ @Dennis I see now, its basically Boolean matrix multiplication done via logic or bit arithmetic. Actual matrix multiplication wouldn't be shorter? \$\endgroup\$
    – xnor
    Mar 28, 2016 at 20:37

Python using numpy, 54 bytes

import numpy
lambda M:(M**0+M+M*M).all(1).nonzero()[0]

Takes in a numpy matrix, outputs a numpy row matrix of 0-based indices.

Another way to think of a king is as a contestant for which all contestants are in the union of the king, the people the king beat, and the people those people beat. In other words, for every contestant, there is a path of length at most 2 from the king to them among the "beat" relation.

The matrix I + M + M*M encodes the numbers of paths of 0, 1, or 2 steps from each source to each target. A player is a king if their row of this matrix has only positive entries. Since 0 is Falsey, all tells us if a row is all nonzero. We apply this to each row and output the indices of the nonzero results.

  • \$\begingroup\$ Looks exactly like my approach but with a differnt interpretation, interesting=) \$\endgroup\$
    – flawr
    Mar 28, 2016 at 19:19

JavaScript (ES6), 83 bytes

  • \$\begingroup\$ You can save 1 with a=>a.map((b,i)=>b.every((c,j)=>c|i==j|b.some((d,k)=>d&a[k][j]))&&i+1).filter(a=>a) but it means you have to output 1-indexed which is a serious bummer \$\endgroup\$ Mar 29, 2016 at 13:55

MATL, 12 10 9 bytes


Input is: first the number of contestants, and on a separate line a matrix with rows separated by semicolons. Output is 1-based.

For example, the fifth test case has input

[0,1,1,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]

and the last test case has input

[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1; 1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1; 0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1; 0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1; 1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1; 0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1; 0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0; 1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0; 1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1; 1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1; 1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0; 0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1; 0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1; 1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1; 0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1; 0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1; 0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1; 0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1; 1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]

Try it online!


Xy    % Implicitly take input: number. Push identity matrix with that size
+     % Implicitly take input: matrix. Add to identity matrix
HY^   % Matrix square
!     % Transpose
A     % Row vector with true entries for columns that contain all nonzero values
f     % Indices of nonzero values
  • 1
    \$\begingroup\$ MATL < Jelly \m/ \$\endgroup\$
    – flawr
    Mar 29, 2016 at 17:38

Javascript 136 131 121 112 bytes


Call using:



watchout because output is 1-indexed (saved a few bytes not trying to filter out 0s vs falses)


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.