Problem 2225

(Last updated: )

Question statement:

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, sorted in ascending order.
  • answer[1] is a list of all players that have lost exactly one match, sorted in ascending order.

Solution

Main idea:

The first readily available approach is to create a dictionary that counts each player’s total wins and losses across all games, and return a sorted list those players whose total losses are 0 and 1 respectively.

The shortcoming of the above approach is that we need to create a dictionary and then iterate through that dictionary a second time. It would be nice to do this in a single pass. This leads us to the second approach.

For the second approach, we maintain three sets that we update as we scan the matches array:

  • allwin: Tracks players who have won all matches up until the current index
  • oneloss: Tracks players who have lost exactly one game up until the current index.
  • manyloss: Tracks the players who have lost more than one match up until the current index.

Running through the matches, at index i, we check if player i[0] is in the oneloss or manyloss sets. If they are, then they don’t go into the allwin set (and otherwise they do). Then we check if player i[1] is in the allwin set, and if they are, we remove them from the allwin set. This handles the logic for retaining the players who have never lost a game in the allwin set.

Now, we check if player i[1] is in the manyloss set; if they are, we don’t update either of the loss sets and move on to the next match. In the second case, we check if they are not in the manyloss set but belong to the the oneloss set, in which case then we remove them from the oneloss set and put them into the manyloss set. In the final case, if player i[1] is in neither the oneloss or the manyloss sets, then we put them in the oneloss set, and move on to the next match.

Iterate until the end of the array. Turn the allwin and oneloss sets to lists, sort them and push them into a single array, which we return as our answer.

Code for approach 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
    allwin = []
    oneloss = []
    dic = {}

    for i in matches:
        if i[0] in dic:
            dic[i[0]][0]+=1
        else:
            dic[i[0]] = [1,0]
        
        if i[1] in dic:
            dic[i[1]][1] +=1
        else:
            dic[i[1]] = [0,1] 
    
    for i in dic:
        if dic[i][1]==0:
            allwin.append(i)
        elif dic[i][1] == 1:
            oneloss.append(i)
        else:
            continue

    return [sorted(allwin), sorted(oneloss)]

Code for approach 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
    allwin = set()
    onelost = set()
    manylost = set()
    for i in matches:
        allwin.add(i[0])
        if(i[0] in onelost or i[0] in manylost):
            allwin.remove(i[0]) 
        if(i[1] in allwin):
            allwin.remove(i[1])
        if(i[1] in onelost):
            onelost.remove(i[1])
            manylost.add(i[1])
            continue
        if(i[1] in manylost):
            continue
            
        onelost.add(i[1])

    return [sorted(list(allwin)), sorted(list(onelost))]

Comments:

Time complexity: O(nlog n) where the most time consuming aspect was the sorting in the very end.

At the time of submission, the first approach passes leetcode submission cases in 1441ms, beating 77.87% of users. It uses 72.06MB of memory, beating 36.02% of users. The second approach passes leetcode submission cases in 1383ms, beating 94.21% of users. It uses 72.06MB of memory, beating 36.02% of users.

One cool O(n) solution that I found in the discussion that bypassed the sorting took advantage of the constraint that the player id caps at 100000. The idea was to simply create a static array of length 100000, and update the winning scores and losing scores for player i at index i (using +1 vs 0 switch for wins and incrementing by -1 for losses).