Find Players With Zero or One Losses

Medium
684.

Find Players With Zero or One Losses

Find Players With Zero or One Losses is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google, Indeed and Palantir interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matches
 * @return {number[][]}
 */
var findWinners = function(matches) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Players With Zero or One Losses — Problem & Solution

Find Players With Zero or One Losses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Players With Zero or One Losses is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google, Indeed and Palantir interviews.

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.

Hints for Find Players With Zero or One Losses

  1. Hint 1

    One tally per player: how many times they lost.

  2. Hint 2

    A winner still needs an entry, initialised to zero, or they will be missing from the first list.

  3. Hint 3

    Then filter for a tally of 0 and a tally of 1, sorting each list.

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

  1. For each match, ensure the winner has an entry (defaulting to 0) and increment the loser's entry.
  2. Walk the map, collecting keys with a count of 0 into one list and keys with a count of 1 into the other.
  3. 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]

Java

public static int[][] findWinners(int[][] matches) {
    TreeMap<Integer, Integer> losses = new TreeMap<>();
    for (int[] m : matches) {
        losses.putIfAbsent(m[0], 0);
        losses.put(m[1], losses.getOrDefault(m[1], 0) + 1);
    }
    List<Integer> zero = new ArrayList<>();
    List<Integer> one = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : losses.entrySet()) {
        if (e.getValue() == 0) zero.add(e.getKey());
        else if (e.getValue() == 1) one.add(e.getKey());
    }
    int[][] out = new int[2][];
    out[0] = new int[zero.size()];
    for (int i = 0; i < zero.size(); i++) out[0][i] = zero.get(i);
    out[1] = new int[one.size()];
    for (int i = 0; i < one.size(); i++) out[1][i] = one.get(i);
    return out;
}

C++

vector<vector<int>> findWinners(vector<vector<int>>& matches) {
    map<int, int> losses;
    for (auto& m : matches) {
        if (!losses.count(m[0])) losses[m[0]] = 0;
        losses[m[1]]++;
    }
    vector<int> zero, one;
    for (auto& e : losses) {
        if (e.second == 0) zero.push_back(e.first);
        else if (e.second == 1) one.push_back(e.first);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets