Find Players With Zero or One Losses — Medium Problem & Solution

Each entry matches[i] = [winner, loser] records one completed match.

Difficulty: Medium
Topics: Arrays, Hash Table, Sorting, Counting
Asked at: Amazon, Google, Paytm
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each entry matches[i] = [winner, loser] records one completed match.

Return a list of two lists: the players who have never lost, and the players who have lost exactly once. Both lists must be sorted in increasing order. Only players who appear in at least one match are considered.

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 never lost; 4, 5, 7 and 8 each lost once.

Example 2

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation: Players 3 and 4 each lost twice, so the second list is empty.

Example 3

Input: matches = [[1,2]]
Output: [[1],[2]]

Constraints

1 <= matches.length <= 100000
matches[i].length == 2
1 <= winner, loser <= 100000
Each pair of players meets at most once.

How to solve Find Players With Zero or One Losses

A single map from player to loss count answers both questions. The subtlety is that winners must be inserted with a count of zero so they are not forgotten.

Approach

For each match, ensure the winner has an entry (defaulting to 0) and increment the loser's entry.
Walk the map, collecting keys with a count of 0 into one list and keys with a count of 1 into the other.
Sort both lists ascending.

Why it works

Every player who appears in any match ends up in the map — losers by incrementing, winners by the explicit zero-initialisation — so the two filters cover exactly the players the statement considers.

Complexity

Time — O(m log m)
Space — O(m)

Pitfalls

Only inserting losers loses every undefeated player, which is the whole first list.
Returning the lists in map iteration order rather than sorted.
An empty list must still appear as [] — the answer always has two entries.

Reference solution

Python

from typing import List

def findWinners(matches: List[List[int]]) -> List[List[int]]:
    losses = {}
    for w, l in matches:
        losses.setdefault(w, 0)
        losses[l] = losses.get(l, 0) + 1
    zero = sorted(p for p, c in losses.items() if c == 0)
    one = sorted(p for p, c in losses.items() if c == 1)
    return [zero, one]

JavaScript

var findWinners = function(matches) {
    var losses = {};
    for (var i = 0; i < matches.length; i++) {
        var w = String(matches[i][0]), l = String(matches[i][1]);
        if (losses[w] === undefined) losses[w] = 0;
        losses[l] = (losses[l] === undefined ? 0 : losses[l]) + 1;
    }
    var zero = [], one = [];
    var keys = Object.keys(losses);
    for (var j = 0; j < keys.length; j++) {
        if (losses[keys[j]] === 0) zero.push(Number(keys[j]));
        else if (losses[keys[j]] === 1) one.push(Number(keys[j]));
    }
    zero.sort(function(a, b) { return a - b; });
    one.sort(function(a, b) { return a - b; });
    return [zero, one];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue