Top Two Teams by Points, Then Goal Difference, Then Goals Scored
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
A league records four statistics for each of its `n` teams in four parallel arrays: `wins[i]`, `draws[i]`, `scored[i]` (goals scored) and `conceded[i]` (goals conceded) all describe team `i`. Rank the teams and return the indices of the first-placed and second-placed teams.
A team earns 3 points for each win and 1 point for each draw, so team `i` has `points = 3 * wins[i] + draws[i]`.
### Function Signature
```python
def top_two_teams(wins: list[int], draws: list[int], scored: list[int], conceded: list[int]) -> list[int]:
```
### Rules
Teams are ranked by the following keys, each one used only to break a tie in all of the previous keys:
1. More points ranks higher.
2. Greater goal difference, `scored[i] - conceded[i]`, ranks higher.
3. More goals scored, `scored[i]`, ranks higher.
4. The smaller index ranks higher.
Return a list of exactly two indices, `[first, second]`. Because the last key never ties, the answer is unique.
### Constraints
- `2 <= n <= 100000`, where `n` is the common length of all four arrays
- `0 <= wins[i] <= 1000` and `0 <= draws[i] <= 1000`
- `0 <= scored[i] <= 100000` and `0 <= conceded[i] <= 100000`
- Goal difference can be negative.
### Examples
**Example 1**
- Input: `wins = [1, 3, 2, 3]`, `draws = [2, 0, 3, 0]`, `scored = [5, 7, 6, 9]`, `conceded = [5, 3, 5, 5]`
- Output: `[3, 1]`
- Explanation: Points are `[5, 9, 9, 9]`. Teams `1`, `2` and `3` tie on 9 points. Their goal differences are `4`, `1` and `4`, so team `2` drops behind. Teams `1` and `3` still tie, and team `3` scored more goals (9 against 7), so team `3` is first and team `1` is second.
**Example 2**
- Input: `wins = [2, 2]`, `draws = [1, 1]`, `scored = [4, 4]`, `conceded = [2, 2]`
- Output: `[0, 1]`
- Explanation: The two teams tie on every statistic, so the smaller index ranks higher.
**Example 3**
- Input: `wins = [0, 4, 3]`, `draws = [5, 0, 4]`, `scored = [2, 10, 3]`, `conceded = [1, 2, 3]`
- Output: `[2, 1]`
- Explanation: Points are `[5, 12, 13]`. Team `2` is first on points even though team `1` has the far better goal difference (8 against 0); goal difference only matters when points are equal.
Overview: Given parallel arrays of wins, draws, goals scored and goals conceded for each team, compute points as three per win plus one per draw and return the indices of the top two teams. Ties are broken by goal difference, then goals scored, then index, testing multi-key comparison and careful tie handling.
Read the full Capital One Software Engineer interview experience this question came from
A league keeps four statistics for each of its `n` teams in four parallel arrays of the same length: `wins[i]`, `draws[i]`, `scored[i]` (goals scored) and `conceded[i]` (goals conceded) all describe team `i`. Rank the teams and return the indices of the teams in first and second place.
A win is worth 3 points and a draw is worth 1 point, so team `i` has `points = 3 * wins[i] + draws[i]`.
Teams are compared by the following keys in order; a later key is only consulted when every earlier key is tied:
1. More points ranks higher.
2. Greater goal difference, `scored[i] - conceded[i]`, ranks higher. Goal difference can be negative.
3. More goals scored, `scored[i]`, ranks higher.
4. The smaller index ranks higher.
Return a list of exactly two indices, `[first, second]`. Because the index key never ties, the ranking is a strict total order and the answer is unique.
All values, including points (at most 4000) and goal differences (between -100000 and 100000), fit in a signed 32-bit integer.
**Example 1**
- Input: `wins = [1, 3, 2, 3]`, `draws = [2, 0, 3, 0]`, `scored = [5, 7, 6, 9]`, `conceded = [5, 3, 5, 5]`
- Output: `[3, 1]`
- Explanation: Points are `[5, 9, 9, 9]`, so teams `1`, `2` and `3` tie on 9. Their goal differences are `4`, `1` and `4`, so team `2` falls behind. Teams `1` and `3` are still tied, and team `3` scored more goals (9 against 7), so team `3` is first and team `1` is second.
**Example 2**
- Input: `wins = [0, 4, 3]`, `draws = [5, 0, 4]`, `scored = [2, 10, 3]`, `conceded = [1, 2, 3]`
- Output: `[2, 1]`
- Explanation: Points are `[5, 12, 13]`. Team `2` is first on points even though team `1` has the much better goal difference (8 against 0): goal difference only matters between teams on equal points.
**Example 3**
- Input: `wins = [2, 2]`, `draws = [1, 1]`, `scored = [4, 4]`, `conceded = [2, 2]`
- Output: `[0, 1]`
- Explanation: The two teams are identical on every statistic, so the smaller index ranks higher.
Constraints
- 2 <= n <= 100000, where n is the common length of wins, draws, scored and conceded
- 0 <= wins[i] <= 1000
- 0 <= draws[i] <= 1000
- 0 <= scored[i] <= 100000
- 0 <= conceded[i] <= 100000
- Goal difference scored[i] - conceded[i] can be negative (range -100000 to 100000); points are at most 4000
- Return exactly two distinct indices [first, second] in ranking order
Examples
Input: ([1, 3, 2, 3], [2, 0, 3, 0], [5, 7, 6, 9], [5, 3, 5, 5])
Expected Output: [3, 1]
Input: ([2, 2], [1, 1], [4, 4], [2, 2])
Expected Output: [0, 1]
Hints
- Write a single comparison that answers 'does team a rank above team b?' by checking points, then goal difference, then goals scored, then index.
- You never need the full ranking, only the top two. Can one pass that remembers the current best and runner-up do the job?
- When a new team beats the current leader, what happens to the old leader?