# #4 Tournament Winner

###### tags: `Array` `Easy`

## Problem
There's an algorithms tournament taking place in which teams of programmers compete against each other to solve algorithmic problems as fast as possible. Teams compete in a round robin, where each team faces off against all other teams. Only two teams compete against each other at a time, and for each competition, one team is designated the home team, while the other team 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 winner of the tournament is the team that receives the most amount of points.

Given an array of pairs representing the teams that have competed against each other and an array containing the results of each competition, write a function that returns the winner of the tournament. The input arrays are named `competitions` and `results`, respectively. The competitions array has elements in the form of `[homeTeam, awayTeam]`, where each team is a string of at most 30 characters representing the name of the team. The `results` array contains information about the winner of each corresponding `competition` in the competitions array. Specifically, `results[i]` denotes the winner of `competitions[i]`, where a `1` in the `results` array means that the home team in the corresponding competition won and a `0` means that the away team won.

It's guaranteed that exactly one team will win the tournament and that each team will compete against all other teams exactly once. It's also guaranteed that the tournament will always have at least two teams.

### Sample Input

competitions = [
  ["HTML", "C#"],
  ["C#", "Python"],
  ["Python", "HTML"],
]
results = [0, 0, 1]

### Sample Output

"Python"
// C# beats HTML, Python Beats C#, and Python Beats HTML.
// HTML - 0 points 
// C# -  3 points
// Python -  6 points

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(k) space - where n is the number of competitions and k is the number of teams

:::

<hr/>

## Solutions

### Official

const HOME_TEAM_WON = 1;

// O(n) time | O(k) space
// where n is the number of competitions and k is the number of teams
function tournamentWinner(competitions, results) {
    let currentBestTeam = '';
    const scores = {[currentBestTeam]: 0};
  
    for (let idx = 0; idx < competitions.length; idx++) {
        const result = results[idx];
        const [homeTeam, awayTeam] = competitions[idx];
        
        const winningTeam = result === HOME_TEAM_WON ? homeTeam : awayTeam;
        
        updateScores(winningTeam, 3, scores);
        
        if (scores[winningTeam] > scores[currentBestTeam]) {
          currentBestTeam = winningTeam;
        }
  }
    
  return currentBestTeam;
}

function updateScores(team, points, scores) {
  if (!(team in scores)) scores[team] = 0;
  scores[team] += points;
}

<br>

---

### Everyone's

#### Loop + Sort
> Step 1: get final score for all teams
> Step 2: sort final score to find the winning team

:::spoiler SOL

function tournamentWinner(competitions, results) {
  const accumulatedPoint = {};
  for (let index = 0; index < competitions.length; index++) {
    const curRoundCompetitions = competitions[index];
    const curRoundResult = results[index];
    const [home, away] = curRoundCompetitions;
    if (curRoundResult === 1) {
      if (!accumulatedPoint[home]) accumulatedPoint[home] = 3;
      else accumulatedPoint[home] = accumulatedPoint[home] + 3;
    } else {
      if (!accumulatedPoint[away]) accumulatedPoint[away] = 3;
      else accumulatedPoint[away] = accumulatedPoint[away] + 3;
    }
  }
  const sortedCompetitionsByPoint = Object.keys(accumulatedPoint).sort(
    (a, b) => accumulatedPoint[b] - accumulatedPoint[a]
  );
  return sortedCompetitionsByPoint[0];
}

:::

<br>

#### Loop twice
> 1st: get final score for all teams
> 2nd: compare all final score to decide the winning team

:::spoiler 東

function tournamentWinner(competitions, results) {
  // Time O(n) | Space O(m), n: numbers of competition, m: number of team
  
  // Calculate score for each team 
  const teamScore = {};
  for (let gameIdx = 0;  gameIdx < results.length; gameIdx++) {
    // Decide win team
    let gameWinTeam;
    if (results[gameIdx] === 1) {
      gameWinTeam = competitions[gameIdx][0];
    } else {
      gameWinTeam = competitions[gameIdx][1];
    }

    // Add score to win team
    if (!teamScore[gameWinTeam]) {
        teamScore[gameWinTeam] = 3;
    } else {
        teamScore[gameWinTeam] += 3;
    }
  }

  // Detect team with max score 
  let tourWinTeam = "";
  let highestScore = 0;
  for (const [team, score] of Object.entries(teamScore)) {
    if (score > highestScore){
      tourWinTeam = team;
      highestScore = score;
    }
  }

  return tourWinTeam;
}

:::

:::spoiler Becky

const HOMETEAM_WON = 1;
const POINTS = 1;

function tournamentWinner(competitions, results) {
  const scores = new Map();

  for (let i = 0; i < competitions.length; i++) {
    const [homeTeam, awayTeam] = competitions[i];
    const result = results[i];
    let winnerTeam;
    if (result == HOMETEAM_WON){
     winnerTeam = homeTeam;
    }else{
     winnerTeam = awayTeam;
    }
    
    let currentScore;
    if (scores.get(winnerTeam)){
      currentScore = scores.get(winnerTeam);
    }else{
      currentScore = 0;
    }
    scores.set(winnerTeam, currentScore + POINTS);
  }

  let currBestScore = 0;
  let currBestTeam = '';

  scores.forEach((score, team) => {
    if (score > currBestScore) {
      currBestScore = score;
      currBestTeam = team;
    }
  });

  return currBestTeam;
}

:::

:::spoiler YC

const HOME_TEAM_WON = 1;
const POINTS = 3;

function tournamentWinner(competitions, results) {
  const scores = {};
  for (let i = 0; i < competitions.length; i++) {
    const [homeTeam, awayTeam] = competitions[i];
    const result = results[i];
    const winningTeam = result === HOME_TEAM_WON ? homeTeam : awayTeam;
    const currentScore = scores[winningTeam] || 0;
    scores[winningTeam]= currentScore + POINTS;
  }
  
  let currBestScore = 0;
  let currBestTeam = '';
  Object.entries(scores).forEach(([team, score]) => {
    if (score > currBestScore) {
      currBestScore = score;
      currBestTeam = team;
    }
  });

  return currBestTeam;
}

:::

:::spoiler Raiy 1st

function tournamentWinner(competitions, results) {
  const teams = {};

  competitions.forEach((battle, index) => {
    if (results[index] === 0) {
      // win battle[1]
      if (teams.hasOwnProperty(battle[1])) {
        teams[battle[1]] = teams[battle[1]] + 3;
      } else {
        teams[battle[1]] = 3;
      }
    } else {
      // win battle[0]
      if (teams.hasOwnProperty(battle[0])) {
        teams[battle[0]] = teams[battle[0]] + 3;
      } else {
        teams[battle[0]] = 3;
      }
    }
  });

  const winner = Object.keys(teams).reduce((a, b) =>
    teams[a] > teams[b] ? a : b
  );
  
  return winner;
}

:::

<br>

#### Loop once
> Declare 2 object(map): 1 for score for all team ; 1 for team with highest score
> Loop once, calculate score and then decide current highest score team in each iteration

:::spoiler Raiy 2nd

function tournamentWinner(competitions, results) {
  const teams = {};
  let winner = { team: 0 };

  competitions.forEach((battle, index) => {
    if (results[index] === 0) {
      // win battle[1]
      if (teams.hasOwnProperty(battle[1])) {
        teams[battle[1]] = teams[battle[1]] + 3;
        if (teams[battle[1]] > Object.values(winner)[0]) {
          winner = {};
          winner[battle[1]] = teams[battle[1]];
        }
      } else {
        teams[battle[1]] = 3;
        if (teams[battle[1]] > Object.values(winner)[0]) {
          winner = {};
          winner[battle[1]] = teams[battle[1]];
        }
      }
    } else {
      // win battle[0]
      if (teams.hasOwnProperty(battle[0])) {
        teams[battle[0]] = teams[battle[0]] + 3;
        if (teams[battle[0]] > Object.values(winner)[0]) {
          winner = {};
          winner[battle[0]] = teams[battle[0]];
        }
      } else {
        teams[battle[0]] = 3;
        if (teams[battle[0]] > Object.values(winner)[0]) {
          winner = {};
          winner[battle[0]] = teams[battle[0]];
        }
      }
    }
  });

  return Object.keys(winner)[0];
}

:::

:::spoiler 月

function tournamentWinner(competitions, results) {
  // O(2n) time | O(n) space
  const map = new Map()
  const winner = {
    winner: "",
    score: 0
  }
  for (let i=0 ; i<results.length ; i++){
    const currentTeams = competitions[i]
    switch(results[i]){
      case 0:
        map.set(currentTeams[1], map.has(currentTeams[1])? map.get(currentTeams[1])+3: 3)
        if(map.get(currentTeams[1]) > winner.score){
          winner.winner = currentTeams[1]
          winner.score = map.get(currentTeams[1])
        }
        break
      case 1:
        map.set(currentTeams[0], map.has(currentTeams[0])? map.get(currentTeams[0])+3: 3)
        if(map.get(currentTeams[0]) > winner.score){
          winner.winner = currentTeams[0]
          winner.score = map.get(currentTeams[0])
        }
        break
       default:
          return "error"
    }
  }
  return winner.winner
}

:::

<br>

#### Declare a result-point map, loop once
> Step 1 Declare a result-point object
> Step 2 Declare a winner info array
> Step 3: Loop once

:::spoiler Hao

function tournamentWinner(competitions, results) {
  /**
   * O(n) time | O(n) space
   */
  const resultPointMap = {
    0: [0, 3],
    1: [3, 0],
  };
  let pointRecords = {};
  let winnerInfo = [0, null];

  results.forEach((value, i) => {
    resultPointMap[String(value)].forEach((point, j) => {
      const team = competitions[i][j];
      if (!pointRecords[team]) pointRecords[team] = point;
      else pointRecords[team] += point;
      if (pointRecords[team] > winnerInfo[0]) winnerInfo = [pointRecords[team], team];
    });
  });
  return winnerInfo[1];
}

:::

<br>

---

## Supplement / Discussion

### Learning from solutions

- Using placeholder as initial value in storing object for getting max/min value to reduce number of loop and variable declaration

    let valueToFind = '';
    const storeObject = {[valueToFind]: 0};

- Specify what "n" stands for in time/space complexity

- Declare **`CONSTANT_VARIABLE`** outside function

- Decalre extra utility function

- Use array/object **Destructuring**, **Ternary operator** when applied

- **`in`** operator : checking if a property exist in an object

    const car = { make: 'Honda', model: 'Accord', year: 1998 };

    console.log('make' in car); // true
    console.log('color' in car); // false

    delete car.make;
    console.log('make' in car) //false

<br>

---

### Worth noticing

#### Sort object with its key/value, returning an sorted array of object value/key

const sortedCompetitionsByPoint = Object.keys(objectToSort).sort(
    (a, b) => objectToSort[b] - objectToSort[a]
  );

#### Iterate and find largest object value, returning key

const largestKey = Object.keys(targetObject).reduce((a, b) =>
    targetObject[a] > targetObject[b] ? a : b
  );