2225. Find Players With Zero or One Losses

Question

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

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

1. Iterate through all the matches record, and put into the win/lose hash maps.
2. Filter out the players that never lose (Not in lose map).
3. Filter out the players that lost exactly once (Value = 1 in map).
4. Sort results and return.

Solution

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        unordered_map<int, int> win;
        unordered_map<int, int> lose;
        vector<int> wResp;
        vector<int> lResp;
        
        for(auto m: matches){
            win[m[0]]++;
            lose[m[1]]++;
         }
        
        for(auto w: win){
            if(w.first && !lose[w.first]) wResp.push_back(w.first);
        }
        
        for(auto l: lose){
            if (l.second == 1) lResp.push_back(l.first);
        }
        
        sort(wResp.begin(),wResp.end());
        sort(lResp.begin(),lResp.end());
        
        return {wResp,lResp};
    }
};

func findWinners(matches [][]int) [][]int {
    win := make(map[int]int)
    lose := make(map[int]int)
    
    winResp := []int{}
    loseResp := []int{}
    
    for _, m := range matches{
        win[m[0]]++
        lose[m[1]]++
    }
    
    for k, m := range win{
        if _, exists := lose[k]; !exists && m > 0{
            winResp = append(winResp,k)
        }
    }
    
    for k, m := range lose{
        if m == 1{
            loseResp = append(loseResp,k)
        }
    }
    
    sort.Ints(winResp)
    sort.Ints(loseResp)

    return [][]int{winResp,loseResp}
}