Given a set of match results, how can I get all teams with at most 10 losses in O(n) time?

I'm trying to write pseudo code to solve the following problem:

Input: n teams in a basketball match. Each team Ti, Tj play and their win/loss record is in matrix A
(for i < j, A[i, j] = 1 if Ti beats Tj)

A team gets a medal if they don't lose more than 10 times.

Output: all teams that receive medals. Find in O(n) time.

This is my pseudo-code so far. Pseudo-code is enough for now but I don't think this works correctly nor does it run in linear time.

//input: matrix A of win/losses
//output: list of teams with medals
set S to an array of length n, with value 0 for all indices //keeps track of number of losses
for each team:
    for each game played in the team's row in M:
        if the team won:
            increment the opponent’s number of losses in the opponent’s index of S
        else:
            increment the team's number of losses in team's index of S
            if at any point a value in the array S reaches 11, remove that team from the list of teams we consider //so basically ignore all the games they play from hereon out
    end for loop
end for loop
take this new potential list of teams with medals
iterate through each team's row in M, counting losses       //to check if they lost against any of the teams we removed from the previous for loop
if losses > 10, remove the team from list
return final list

Solution

Building on qwertyman's approach, we can solve this in O(n) as follows:

Keep track of the number of losses for each team
Keep track of the remaining teams (i.e. those with 10 or less losses - we do this by keeping an array of indices and swapping elements around for constant time removal)
Loop over all possible match-ups from the remaining teams
- Increase the loss count of the losing team
- If that loss count is greater than 10, remove that team from the remaining teams
- Note: This loop might appear to take O(n²), but the number of remaining teams decreases fast enough for this to only take O(n).
  You can see this from the fact that we increase a loss count ever iteration, and the maximum sum of loss counts is 11*n (because once a loss count is 11, we remove it from consideration and don't increase it any more), thus this loop runs at most 11*n = O(n) times.
Now there will be at most 21 teams remaining.
This is if we're not aware of any losses of a remaining team against any team already removed (it's easy to see that this is the best case), and then each remaining team won against 10 of the other 20 remaining teams. 22 teams is impossible, because each team will need to have won at least 11/21 games to maintain 10 or less losses, leading to more wins than losses, which is impossible considering that each game has 1 winner and 1 loser.
For each remaining team, we simply run over all games for that team and count the number of losses (21 loops of O(n) = O(n)) and output the teams with 10 or less losses.

Java-like code: (slightly modified working version for readability)

// returns true if i beat j or false if j beat i
boolean beat(int i, int j);
// return the loser in the game between i and j
int loser(int i, int j);
// swaps i with the last element in indices and decreases index count, takes O(1)
void removeIndex(int i);

// x = indices[y] corresponds to a remaining team x
int[] indices = new int[n];
// number of elements in indices, decreased in removeIndex
int indicesCount = n;

// initialise our array of indices
for (int i = 0; i < n; i++)
    indices[i] = i;

// initialise our array of losses
losses = new int[n];

// loop over all possible match-ups and eliminate (some) teams with > 10 losses
for (int a = 0; a < indicesCount; )
{
    for (int b = a+1; losses[indices[a]] <= 10 && b < indicesCount; )
    {
        losses[loser(indices[a], indices[b])]++;

        if (losses[indices[b]] > 10)
            removeIndex(b);
        else
            b++;
    }
    if (losses[indices[a]] > 10)
        removeIndex(a);
    else
        a++;
}

// find teams with <= 10 losses
for (int i = 0; i < indicesCount; i++)
{
    int lossCount = 0;
    for (int j = 0; j < n; j++)
        if (indices[i] == j)
            continue;
        else if (beat(j, indices[i]))
            lossCount++;
    if (lossCount <= 10)
        // output indices[i]
}

Live demo.