Try   HackMD

#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

Optimal Space & Time Complexity 
O(n) time | O(k) space - where n is the number of competitions and k is the number of teams

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;
}

Everyone's

Loop + Sort

Step 1: get final score for all teams
Step 2: sort final score to find the winning team

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];
}

Loop twice

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

東 


































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;
}
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;
}
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;
}
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;
}

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

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];
}
月 






























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
}

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

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];
}

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

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
  );
Last changed by 
 
哩扣寶寶船
0
488

Read more

#2 [Leetcode.21](https://leetcode.com/problems/merge-two-sorted-lists/) Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Feb 2, 2025
Merging Linked Lists

You&#39;re given two Linked Lists of potentially unequal length. These Linked Lists potentially merge at a shared intersection node. Write a function that returns the intersection node or returns None / null if there is no intersection.Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None null if it&#39;s the tail of the list.Note: Your function should return an existing node. It should not modify either Linked List, and it should not create any new Linked Lists.

Feb 2, 2025
Remove Kth Node From End

Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list.The removal should be done in place, meaning that the original data structure should be mutated (no new structure should be created).Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that&#39;s supposed to be removed. In other words, if the head is the node that&#39;s supposed to be removed, your function should simply mutate its value and next pointer.Note that your function doesn&#39;t need to return anything.You can assume that the input Linked List will always have at least two nodes and, more specifically, at least k nodes.Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it&#39;s the tail of the list.

Feb 2, 2025
121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solutions/1735550/python-javascript-easy-solution-with-very-clear-explanation/

Aug 27, 2023
Read more from 哩扣寶寶船
Published on HackMD