All problems

Lost Tie-Break Order

Hard · topological sort

A league table lists n teams from best to worst. Row i of standings holds the m scores of the team in position i, one for each of m criteria numbered 0 to m - 1. For every criterion, a lower score is better.

The league ranks teams with a priority order: a list that contains each criterion number exactly once, most important first. To compare two teams, look at the criteria in priority order and find the first one where their scores differ. The team with the lower score there ranks higher. Teams with identical scores on every criterion may stand in either order.

The priority order has been lost, but the table is correct: for every pair of neighbouring rows, the upper team must not rank lower than the team below it.

Return a priority order that explains the table. If several do, return the one that comes first when lists are compared like words (at the first position where two orders differ, the smaller criterion number wins). If no priority order can explain the table, return an empty list.

Examples

Example 1

Input: standings = [[1, 3], [2, 1]]

Output: [0, 1]

Criterion 0 alone separates the teams (1 is lower than 2). Checking criterion 1 first would put the lower team on top, so the order must be 0, then 1.

Example 2

Input: standings = [[1, 0], [0, 1]]

Output: [1, 0]

The upper team has the higher score on criterion 0, so criterion 1 must be checked first, where it is lower.

Example 3

Input: standings = [[0, 1], [1, 0], [0, 1]]

Output: []

The first two rows need criterion 0 to be checked first, and the last two rows need criterion 1 first. Both cannot hold.

Constraints