Find Players With Zero or One Losses - Practice Coding Problems

Find Players With Zero or One Losses - Problem

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i 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.

Input & Output

Example 1 — Basic Tournament

$ 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,6]]

💡 Note: Players 1, 2, 10 never lost (0 losses). Players 4, 5, 6 lost exactly once. Player 3 lost twice (excluded), players 7, 8, 9 lost once but 7, 8, 9 are not winners so they're excluded from first list.

Example 2 — Simple Case

$ Input: matches = [[2,3],[1,3],[3,4]]

› Output: [[1,2],[3]]

💡 Note: Players 1 and 2 never lost. Player 3 lost exactly once. Player 4 lost once but since 4 never won, only players who played are considered.

Example 3 — Single Match

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

› Output: [[1],[2]]

💡 Note: Player 1 won and never lost (0 losses). Player 2 lost exactly once.

Constraints

1 ≤ matches.length ≤ 10⁵
matches[i].length == 2
1 ≤ winner_i, loser_i ≤ 10⁵
winner_i ≠ loser_i
All matches[i] are unique

Visualization

Tap to expand

Understanding the Visualization

Input Matches

Array of [winner, loser] pairs from tournament

Count Losses

Track how many times each player lost

Categorize & Sort

Group players by 0 or 1 losses, return sorted lists

Key Takeaway

🎯 Key Insight: Use hash map to count losses efficiently in one pass, then filter and sort by loss count

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to count losses per player using a hash map. Track all players and increment loss count for losers. Then filter players with exactly 0 or 1 losses and sort the results. Best approach uses hash map counting in O(n + p log p) time and O(p) space.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Count Losses Efficiently	O(n + p log p)	O(p)	Use hash map to count losses for each player in one pass
Brute Force - Count Losses for Each Player	O(n × p)	O(p)	For each player, scan all matches to count their losses

Hash Map - Count Losses Efficiently — Algorithm Steps

Step 1: Initialize hash map to count losses
Step 2: Single pass through matches to count losses and track all players
Step 3: Categorize players by loss count and sort results

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create hash map for loss counting

Count Losses

Single pass: increment loser count, ensure winner tracked

Filter & Sort

Extract players with 0 or 1 losses, sort results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int** solution(int** matches, int matchesSize, int* matchesColSize, int* returnSize, int** returnColumnSizes) {
    // Use arrays to simulate hash map (assuming player IDs are reasonable)
    int lossCount[100001] = {0}; // Support player IDs up to 100000
    int playerExists[100001] = {0};
    int maxPlayer = 0;
    
    // Single pass to count losses and track players
    for (int i = 0; i < matchesSize; i++) {
        int winner = matches[i][0];
        int loser = matches[i][1];
        
        playerExists[winner] = 1;
        playerExists[loser] = 1;
        lossCount[loser]++;
        
        if (winner > maxPlayer) maxPlayer = winner;
        if (loser > maxPlayer) maxPlayer = loser;
    }
    
    int* noLosses = (int*)malloc(maxPlayer * sizeof(int));
    int* oneLoss = (int*)malloc(maxPlayer * sizeof(int));
    int noLossCount = 0, oneLossCount = 0;
    
    // Categorize players by loss count
    for (int i = 1; i <= maxPlayer; i++) {
        if (playerExists[i]) {
            if (lossCount[i] == 0) {
                noLosses[noLossCount++] = i;
            } else if (lossCount[i] == 1) {
                oneLoss[oneLossCount++] = i;
            }
        }
    }
    
    // Sort results
    qsort(noLosses, noLossCount, sizeof(int), compare);
    qsort(oneLoss, oneLossCount, sizeof(int), compare);
    
    // Prepare return arrays
    int** result = (int**)malloc(2 * sizeof(int*));
    *returnColumnSizes = (int*)malloc(2 * sizeof(int));
    
    result[0] = noLosses;
    result[1] = oneLoss;
    (*returnColumnSizes)[0] = noLossCount;
    (*returnColumnSizes)[1] = oneLossCount;
    *returnSize = 2;
    
    return result;
}

int main() {
    // Simplified parsing for demonstration
    int matches[][2] = {{1,3},{2,3},{3,6},{5,6},{5,7},{4,5},{4,8},{4,9},{10,4},{10,9}};
    int matchesSize = 10;
    int* matchesColSize = (int*)malloc(matchesSize * sizeof(int));
    for (int i = 0; i < matchesSize; i++) matchesColSize[i] = 2;
    
    int** matchesPtr = (int**)malloc(matchesSize * sizeof(int*));
    for (int i = 0; i < matchesSize; i++) {
        matchesPtr[i] = matches[i];
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(matchesPtr, matchesSize, matchesColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + p log p)

O(n) to process matches + O(p log p) to sort results where p is number of players

⚡ Linearithmic

Space Complexity

O(p)

Hash map stores loss count for each of p players

✓ Linear Space

83.2K Views

Medium Frequency

~15 min Avg. Time

2.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Count Losses Efficiently — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler