There is a tournament taking place where teams compete against each other. Only two teams compete against each other as a time, for each competition, one team is designated the home team while the other is the away team. In each competition there’s always one winner and one loser, there are no ties. A team receives 3 points if it wins and 0 points if it loses. The winning team is the team with the most points. Given an array of pairs representing the teams that have competed against each other an an array containing the result of each competition, create an algorithm that returns the winner of the tournament.

Overview

We get two lists and we iterate though them.

Flow Diagram

We need to iterate through the competitions list, find the winner and keep track of the current best team to return at the end.

Time Complexity

The algorithm will go through the array of competitions once, that will give us a time complexity of O(n).

Space Complexity

Each team in each competition is stored in a Map, as we add all teams to the map, we will have M teams stored in the map. So we might have any number of competitions in the list and some teams will be already in the map thus M teams and a space complexity of O(M)

Java Source Code

     public String tournamentWinner(final List<List<String>> competitions, final List<Integer> results) {
        var currentBestTeam = &quot";
        final Map&lt;String,Integer> scoresMap = new HashMap<>();
        scoresMap.put(currentBestTeam,0);

        var index = 0;
        for(final var competition : competitions) {
            final var result = results.get(index);
            final var homeTeam = competition.get(0);
            final var awayTeam = competition.get(1);
            final var winningTeam = result == HOME_TEAM_WON ? homeTeam : awayTeam;

            updateScores(winningTeam,POINTS_PER_WIN,scoresMap);

            currentBestTeam = scoresMap.get(winningTeam) > scoresMap.get(currentBestTeam) ? winningTeam : currentBestTeam;
            index++;
        }

        return currentBestTeam;
    }


    private void updateScores(final String team, final int points, final Map<String,Integer> scoresMap) {
        final int teamCurrentScore = scoresMap.getOrDefault(team,0);
        final int totalPoints = teamCurrentScore + points;
        scoresMap.put(team,totalPoints);
    }

Conclusion

There’s no sense in going to a tournament if you don’t believe that you can win it. And that is the belief I have always had. And that is not going to change.

Tiger Woods