2225. Find Players With Zero or One Losses

Find Players With Zero or One Loss

Problem Description

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

Example 2:

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 <= 105
• matches[i].length == 2
• 1 <= winneri, loseri <= 105
• winneri != loseri
• All matches[i] are unique.

Approach) Generic Solution (Straight Forward)

/**
 * @param {number[][]} matches
 * @return {number[][]}
 */
var findWinners = function(matches) {
    const zeroLoss = {};
    const oneLoss  = {};
    const moreLosses = {};
    
    for(let i = 0; i < matches.length; i++) {
        const winner = matches[i][0];
        const loser = matches[i][1];
        
        // Add winner
        if(!moreLosses[winner] && !oneLoss[winner]) {
            zeroLoss[winner] = true;
        }
        
        // Add or move loser
        if(zeroLoss[loser]){
            delete zeroLoss[loser];
            oneLoss[loser] = true;
        } else if(oneLoss[loser]) {
            delete oneLoss[loser];
            moreLosses[loser] = true;
        } else if(moreLosses[loser]){
            continue; 
        } else {
            oneLoss[loser] = true;
        }
    }
    
    const sortedZeroLosses = Object.keys(zeroLoss).sort((a, b) => a - b);
    const sortedOneLosses = Object.keys(oneLoss).sort((a, b) => a - b);
    return [sortedZeroLosses, sortedOneLosses]
};

Approach) Generic Solution (Using Javascript In-Built Function)

var findWinners = function(matches) {
    const hash = matches.reduce((res, [winner, loser]) => {
        if (!res[winner]) {
            res[winner] = 0;
        }
        
        if (!res[loser]) {
            res[loser] = 0;
        }
        
        res[loser]++;
        
        return res;
    }, {});
    
    return Object.keys(hash).reduce((res, x) => {
        const count = hash[x];
        
        if (count === 0) {
            res[0].push(x);
        } else if (count === 1) {
            res[1].push(x);
        }
        
        return res;
    }, [[], []]);
};

Approach) Map + Sorting

/**
 * @param {number[][]} matches
 * @return {number[][]}
 */
var findWinners = function(matches) {
    const players = new Map()
    for (const match of matches.values()) {
        const [winner, loser] = match
        if (!players.has(winner))
            players.set(winner, 0)
        
        players.set(loser, 1 + (players.get(loser) || 0))
    }
    
    
    const list0 = [], list1 = []
    for (const [player, freq] of players.entries()) {
        if (freq === 0) list0.push(player)
        else if (freq === 1)    list1.push(player)
    }
    
    
    function compare(a, b) {
        return a - b
    }
    list0.sort(compare)
    list1.sort(compare)
    
    
    return [list0, list1]
};

Approach) Map + Set + Sort

const counter = (a_or_s) => { let m = new Map(); for (const x of a_or_s) m.set(x, m.get(x) + 1 || 1); return m; };

const findWinners = (matches) => {
    let lose = matches.map(x => x[1]), m = counter(lose);
    let res = [new Set(), new Set()];
    for (const [x, occ] of m) {
        if (occ == 1) res[1].add(x);
    }
    for (const [winner,] of matches) {
        if (!m.has(winner)) res[0].add(winner);
    }
    return res.map(se => [...se].sort((x, y) => x - y));
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 2225. Find Players With Zero or One Loss

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!