2225. Find Players With Zero or One Losses

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 list answer of size 2 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.

Example 1:

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].

//approach-1
class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        //this is my code
        int n= matches.length;
        List<List<Integer>> res=new ArrayList<>();
        Set<Integer> players=new HashSet<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                if(!players.contains(matches[i][j]))
                    players.add(matches[i][j]);
            }
        }
        //store the loses of each player
        HashMap<Integer,Integer> count_loss=new HashMap<>();
        for(int i=0;i<n;i++){
            if(!count_loss.containsKey(matches[i][1]))
                count_loss.put(matches[i][1],1);
            else
                count_loss.put(matches[i][1],count_loss.get(matches[i][1])+1);
        }
        List<Integer> one_loss=new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry: count_loss.entrySet()){
            int key=entry.getKey();
            int loss= entry.getValue();
            if(loss==1)
                one_loss.add(key);
        }
        List<Integer> no_loss=new ArrayList<>();
        for(int x:players){
            if(!count_loss.containsKey(x))
                no_loss.add(x);
        }
        Collections.sort(no_loss);
        Collections.sort(one_loss);
        res.add(no_loss);
        res.add(one_loss);
        return res;
    }
}

Approach 2: Hash Set

Time complexity: O(n\cdot \log n)O(n⋅logn)
space com= O(n)

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Set<Integer> zeroLoss = new HashSet<>(), oneLoss = new HashSet<>(),\
                moreLosses = new HashSet<>();

        for (int[] match : matches) {
            int winner = match[0], loser = match[1];
            // Add winner.
            if (!oneLoss.contains(winner) && !moreLosses.contains(winner)) {
                zeroLoss.add(winner);
            }
            // Add or move loser.
            if (zeroLoss.contains(loser)) {
                zeroLoss.remove(loser);
                oneLoss.add(loser);
            } else if (oneLoss.contains(loser)) {
                oneLoss.remove(loser);
                moreLosses.add(loser);
            } else if (moreLosses.contains(loser)) {
                continue;
            } else {
                oneLoss.add(loser);
            }
        }

        List<List<Integer>> answer =
            Arrays.asList(new ArrayList<>(), new ArrayList<>());
        answer.get(0).addAll(zeroLoss);
        answer.get(1).addAll(oneLoss);
        Collections.sort(answer.get(0));
        Collections.sort(answer.get(1));

        return answer;
    }
}
//Approach 2: Hash Set + Hash Map

Time complexity: O(n\cdot \log n)O(n⋅logn)
space com= O(n)

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Set<Integer> seen = new HashSet<>();
        Map<Integer, Integer> lossesCount = new HashMap<>();

        for (int[] match : matches) {
            int winner = match[0], loser = match[1];
            seen.add(winner);
            seen.add(loser);
            lossesCount.put(loser, lossesCount.getOrDefault(loser, 0) + 1);
        }

        // Add players with 0 or 1 loss to the corresponding list.
        List<List<Integer>> answer =
            Arrays.asList(new ArrayList<>(), new ArrayList<>());
        for (int player : seen) {
            if (!lossesCount.containsKey(player)) {
                answer.get(0).add(player);
            } else if (lossesCount.get(player) == 1) {
                answer.get(1).add(player);
            }
        }

        Collections.sort(answer.get(0));
        Collections.sort(answer.get(1));

        return answer;
    }
}
//Approach 3: Hash Map

Time complexity: O(n\cdot \log n)O(n⋅logn)
space com= O(n)

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> lossesCount = new HashMap<>();
        for (int[] match : matches) {
            int winner = match[0], loser = match[1];
            lossesCount.put(winner, lossesCount.getOrDefault(winner, 0));
            lossesCount.put(loser, lossesCount.getOrDefault(loser, 0) + 1);
        }

        List<List<Integer>> answer = Arrays.asList(new ArrayList<>(), new ArrayList<>());
        for (Integer player : lossesCount.keySet())
            if (lossesCount.get(player) == 0) {
                answer.get(0).add(player);
            } else if (lossesCount.get(player) == 1) {
                answer.get(1).add(player);
            }

        Collections.sort(answer.get(0));
        Collections.sort(answer.get(1));

        return answer;
    }
}