Problem

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a listanswer of size2 where:

  • answer[0] is a list of all players that have not lost any matches.
  • answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

  • You should only consider the players that have played at least one match.
  • The testcases will be generated such that no two matches will have the same outcome.

Examples

Example 1

1
2
3
4
5
6
7

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2

1
2
3
4
5
6

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints

  • 1 <= matches.length <= 10^5
  • matches[i].length == 2
  • 1 <= winneri, loseri <= 10^5
  • winneri != loseri
  • All matches[i] are unique.

Solution

Method 1 – Counting Losses with Hash Map

Intuition

We count the number of losses for each player using a hash map. Players with zero losses are those who never appear as a loser, and players with exactly one loss appear once as a loser. We only consider players who played at least one match.

Approach

  1. Initialize a hash map to count losses for each player.
  2. For each match, increment the loss count for the loser and ensure the winner is in the map (with 0 losses if not present).
  3. Iterate through the map:
    • Add players with 0 losses to the first list.
    • Add players with 1 loss to the second list.
  4. Sort both lists and return them as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        unordered_map<int, int> loss;
        for (auto& m : matches) {
            loss[m[0]] += 0;
            loss[m[1]]++;
        }
        vector<int> zero, one;
        for (auto& [p, l] : loss) {
            if (l == 0) zero.push_back(p);
            else if (l == 1) one.push_back(p);
        }
        sort(zero.begin(), zero.end());
        sort(one.begin(), one.end());
        return {zero, one};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func findWinners(matches [][]int) [][]int {
    loss := map[int]int{}
    for _, m := range matches {
        loss[m[0]] += 0
        loss[m[1]]++
    }
    zero, one := []int{}, []int{}
    for p, l := range loss {
        if l == 0 {
            zero = append(zero, p)
        } else if l == 1 {
            one = append(one, p)
        }
    }
    sort.Ints(zero)
    sort.Ints(one)
    return [][]int{zero, one}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> loss = new HashMap<>();
        for (int[] m : matches) {
            loss.put(m[0], loss.getOrDefault(m[0], 0));
            loss.put(m[1], loss.getOrDefault(m[1], 0) + 1);
        }
        List<Integer> zero = new ArrayList<>(), one = new ArrayList<>();
        for (var e : loss.entrySet()) {
            if (e.getValue() == 0) zero.add(e.getKey());
            else if (e.getValue() == 1) one.add(e.getKey());
        }
        Collections.sort(zero);
        Collections.sort(one);
        return List.of(zero, one);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun findWinners(matches: Array<IntArray>): List<List<Int>> {
        val loss = mutableMapOf<Int, Int>()
        for (m in matches) {
            loss[m[0]] = loss.getOrDefault(m[0], 0)
            loss[m[1]] = loss.getOrDefault(m[1], 0) + 1
        }
        val zero = mutableListOf<Int>()
        val one = mutableListOf<Int>()
        for ((p, l) in loss) {
            if (l == 0) zero.add(p)
            else if (l == 1) one.add(p)
        }
        zero.sort()
        one.sort()
        return listOf(zero, one)
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findWinners(self, matches: list[list[int]]) -> list[list[int]]:
        loss = {}
        for w, l in matches:
            loss[w] = loss.get(w, 0)
            loss[l] = loss.get(l, 0) + 1
        zero = [p for p, v in loss.items() if v == 0]
        one = [p for p, v in loss.items() if v == 1]
        return [sorted(zero), sorted(one)]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn find_winners(matches: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::HashMap;
        let mut loss = HashMap::new();
        for m in matches.iter() {
            *loss.entry(m[0]).or_insert(0) += 0;
            *loss.entry(m[1]).or_insert(0) += 1;
        }
        let mut zero = vec![];
        let mut one = vec![];
        for (&p, &l) in &loss {
            if l == 0 { zero.push(p); }
            else if l == 1 { one.push(p); }
        }
        zero.sort();
        one.sort();
        vec![zero, one]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    findWinners(matches: number[][]): number[][] {
        const loss: Record<number, number> = {};
        for (const [w, l] of matches) {
            loss[w] = loss[w] ?? 0;
            loss[l] = (loss[l] ?? 0) + 1;
        }
        const zero: number[] = [], one: number[] = [];
        for (const p in loss) {
            if (loss[p] === 0) zero.push(+p);
            else if (loss[p] === 1) one.push(+p);
        }
        zero.sort((a, b) => a - b);
        one.sort((a, b) => a - b);
        return [zero, one];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of unique players, due to sorting.
  • 🧺 Space complexity: O(n), for the loss map and answer arrays.