Given a 2D array of strings arr[][4], representing the scores of M football matches played in a tournament involving N teams, the task is to print the names of the teams in ascending order of their ranks.
- The rules of a match are as follows:
- Each team plays 2 matches.
- The winning team gets 2 points and the losing team gets 0.
- In the case of a tie, both teams share a point each.
- If GD, GA, and GF stand for Goal Difference, Goals Against, and Goals For respectively. The rank of a team is decided in the following priority order:
- Points > GD > GF > Lexicographical order of names.
Examples:
Input: arr[][] = { { “Spain”, “England”, “3″, “0″ }, { “England”, “France”, “1″, “1″ }, { “Spain”, “France”, “0”, “2” } }, N = 3, M = 3
Output: France Spain England
Explanation: Points Table after 3 matches apiece:
Teams Matches
PlayedGF GA GD Points Ranking Spain
2
3
2
1
2
2
England
2
1
4
-3
1
3
France
2
3
1
2
3
1
Input: arr[][] = { { “Spain”, “England”, “3″, “0″ }, { “England”, “France”, “1″, “1″ }, { “Spain”, “Spain”, “0”, “2” } }, N = 3, M = 3
Output: Invalid Input
Approach: The problem can be solved using sorting a dictionary by multiple attributes.
Follow the steps below to solve the problem:
- Traverse the list arr[][] and print “Invalid” if arr[i][0] is equal to arr[i][1] and break.
- Initialize a dictionary say table to store the GA, GF, and GD for a particular teams.
- Traverse the list arr[][] and perform the following operations:
- Increment GF for arr[i][0], table[arr[i][0]][0] by arr[i][2] and GA for the arr[i][0], table[arr[i][0]][1] by arr[i][3].
- Increment GF for arr[i][1], table[arr[i][1]][0] by arr[i][3] and GA for the arr[i][1], table[arr[i][1]][1] by arr[i][2].
- Update GD for arr[i][0], table[arr[i][0]] by table[arr[i][0][2] – table[arr[i][0][3].
- Update GD for arr[i][1], table[arr[i][1]] by table[arr[i][1][2] – table[arr[i][1][3].
- If arr[i][2] == arr[i][3], then increment table[arr[i][0][0] and table[arr[i][1]][0] both by 1.
- If arr[i][2] > arr[i][3], then increment table[arr[i][0][0] by 2.
- If arr[i][2] < arr[i][3], then increment table[arr[i][1][0] by 2.
- Now, sort the dictionary table based on the priority points > GD > GF and names as:
- table = sorted(table.items(), key=lambda r: (-r[1][0], -r[1][1], -r[1][2], r[0]))
- Finally, print the names of the teams in sorted table.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the ranking of teamsvoid rankTeams(vector<vector<string>> arr) { for (int i = 0; i < arr.size(); i++) { if (arr[i][0] == arr[i][1]) { cout << "Invalid" << endl; return; } // Convert the goal to integer arr[i][2] = to_string(stoi(arr[i][2])); arr[i][3] = to_string(stoi(arr[i][3])); } // Stores the list of GD, GA, and GF map<string, vector<int>> table; // Traverse the list for (int i = 0; i < arr.size(); i++) { // Store the list of GA, GF // and GD of first team vector<int> li1 = { 0, 0, 0, 0 }; // Store the list of GA, GF // and GD of second team vector<int> li2 = { 0, 0, 0, 0 }; // If arr[i][0] is in table if (table.count(arr[i][0])) { li1 = table[arr[i][0]]; } // If arr[i][1] is in table if (table.count(arr[i][1])) { li2 = table[arr[i][1]]; } // Increment GF by arr[i][2] li1[2] += stoi(arr[i][2]); // Increment GA by arr[i][3] li1[3] += stoi(arr[i][3]); // Increment GF by arr[i][3] li2[2] += stoi(arr[i][3]); // Increment GA by arr[i][2] li2[3] += stoi(arr[i][2]); // Update GD li1[1] = li1[2] - li1[3]; li2[1] = li2[2] - li2[3]; // If tie if (arr[i][2] == arr[i][3]) { li1[0]++; li2[0]++; } // If arr[i][0] wins else if (stoi(arr[i][2]) > stoi(arr[i][3])) { li1[0] += 3; } // If arr[i][1] wins else { li2[0] += 3; } // Update table with li1 table[arr[i][0]] = li1; // Update table with li2 table[arr[i][1]] = li2; } // List to store teams and their points vector<vector<string>> res; // Traverse the table for (auto& entry : table) { // Store the team name string key = entry.first; // Store the points int val = entry.second[0]; // Add to res res.push_back({ key, to_string(val) }); } // Sort the list res sort(res.begin(), res.end(), [](const vector<string>& a, const vector<string>& b) { if (stoi(a[1]) == stoi(b[1])) { return a[0] < b[0]; } return stoi(b[1]) < stoi(a[1]); }); // Print the ranking of teams for (int i = 0; i < res.size(); i++) { cout << res[i][0] << endl; }}// Driver codeint main() { // Input vector<vector<string>> arr = { { "Spain", "England", "3", "0" }, { "England", "France", "1", "1" }, { "Spain", "France", "0", "2" } }; rankTeams(arr); return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { // Input List<List<String>> arr = new ArrayList<>(); arr.add(Arrays.asList("Spain", "England", "3", "0")); arr.add(Arrays.asList("England", "France", "1", "1")); arr.add(Arrays.asList("Spain", "France", "0", "2")); rankTeams(arr); } // Function to find the ranking of teams public static void rankTeams(List<List<String>> arr) { // Traverse the list arr for (int i = 0; i < arr.size(); i++) { // arr.get(i).get(0) is equal to arr.get(i).get(1) if (arr.get(i).get(0).equals(arr.get(i).get(1))) { System.out.println("Invalid"); return; } // Convert the goal to integer arr.get(i).set(2, Integer.toString(Integer.parseInt(arr.get(i).get(2)))); arr.get(i).set(3, Integer.toString(Integer.parseInt(arr.get(i).get(3)))); } // Stores the list of GD, GA, and GF Map<String, List<Integer>> table = new HashMap<>(); // Traverse the list for (int i = 0; i < arr.size(); i++) { // Store the list of GA, GF // and GD of first team List<Integer> li1 = new ArrayList<>(Arrays.asList(0, 0, 0, 0)); // Store the list of GA, GF // and GD of second team List<Integer> li2 = new ArrayList<>(Arrays.asList(0, 0, 0, 0)); // If arr[i][0] is in table if (table.containsKey(arr.get(i).get(0))) { li1 = table.get(arr.get(i).get(0)); } // If arr[i][1] is in table if (table.containsKey(arr.get(i).get(1))) { li2 = table.get(arr.get(i).get(1)); } // Increment GF by arr[i][2] li1.set(2, li1.get(2) + Integer.parseInt(arr.get(i).get(2))); // Increment GA by arr[i][3] li1.set(3, li1.get(3) + Integer.parseInt(arr.get(i).get(3))); // Increment GF by arr[i][3] li2.set(2, li2.get(2) + Integer.parseInt(arr.get(i).get(3))); // Increment GA by arr[i][2] li2.set(3, li2.get(3) + Integer.parseInt(arr.get(i).get(2))); // Update GD li1.set(1, li1.get(2) - li1.get(3)); li2.set(1, li2.get(2) - li2.get(3)); // If tie if (arr.get(i).get(2).equals(arr.get(i).get(3))) { li1.set(0, li1.get(0) + 1); li2.set(0, li2.get(0) + 1); } // If arr[i][0] wins else if (Integer.parseInt(arr.get(i).get(2)) > Integer.parseInt(arr.get(i).get(3))) { li1.set(0, li1.get(0) + 3); } // else if (Integer.parseInt(arr.get(i).get(2)) > Integer.parseInt(arr.get(i).get(3))) { li1.set(0, li1.get(0) + 3); } // If arr[i][1] wins else { li2.set(0, li2.get(0) + 3); } // Update table with li1 table.put(arr.get(i).get(0), li1); // Update table with li2 table.put(arr.get(i).get(1), li2); } // List to store teams and their points List<List<String>> res = new ArrayList<>(); // Traverse the table for (Map.Entry<String, List<Integer>> entry : table.entrySet()) { // Store the team name String key = entry.getKey(); // Store the points int val = entry.getValue().get(0); // Add to res res.add(Arrays.asList(key, Integer.toString(val))); } // Sort the list res Collections.sort(res, new Comparator<List<String>>() { public int compare(List<String> a, List<String> b) { if (Integer.parseInt(a.get(1)) == Integer.parseInt(b.get(1))) { return a.get(0).compareTo(b.get(0)); } return Integer.parseInt(b.get(1)) - Integer.parseInt(a.get(1)); } }); // Print the ranking of teams for (int i = 0; i < res.size(); i++) { System.out.println(res.get(i).get(0)); }}} |
Python3
# Python program for the above approach# Function to find the ranking of teamsdef RankTeams(arr): # Traverse the list arr for i in range(len(arr)): # arr[i][0] is equal to arr[i][1] if(arr[i][0] == arr[i][1]): print("Invalid") return # Convert the goal to integer arr[i][2] = int(arr[i][2]) arr[i][3] = int(arr[i][3]) # Stores the list of GD, GA, and GF table = {} # Traverse the list for i in range(len(arr)): # Store the list of GA, GF # and GD of first team li1 = [0] * 4 # Store the list of GA, GF # and GD of second team li2 = [0] * 4 # If arr[i][0] is in table if arr[i][0] in table: li1 = table[arr[i][0]] # If arr[i][1] is in table if arr[i][1] in table: li2 = table[arr[i][1]] # Increment GF by arr[i][2] li1[2] += arr[i][2] # Increment GA by arr[i][3] li1[3] += arr[i][3] # Increment GF by arr[i][3] li2[2] += arr[i][3] # Increment GA by arr[i][2] li2[3] += arr[i][2] # Update GD li1[1] = li1[2] - li1[3] li2[1] = li2[2] - li2[3] # If tie if(arr[i][2] == arr[i][3]): li1[0] += 1 li2[0] += 1 # If arr[i][0] wins elif(arr[i][2] > arr[i][3]): li1[0] += 2 # If arr[i][1] wins elif(arr[i][2] < arr[i][3]): li2[0] += 2 # Update list in table table[arr[i][0]] = li1 table[arr[i][1]] = li2 # Traverse the sorted table in the given priority for key, value in sorted(table.items(), key = lambda r: (-r[1][0], -r[1][1], -r[1][2], r[0])): # Print the team name print(key, end ='\n')# Driver Code# Inputarr = [['Spain', 'England', '3', '0'], ['England', 'France', '1', '1'], ['Spain', 'France', '0', '2']]RankTeams(arr) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find the ranking of teams static void RankTeams(List<List<string>> arr) { // Traverse the list arr for (int i = 0; i < arr.Count; i++) { // arr[i][0] is equal to arr[i][1] if (arr[i][0] == arr[i][1]) { Console.WriteLine("Invalid"); return; } // Convert the goal to integer arr[i][2] = int.Parse(arr[i][2]).ToString(); arr[i][3] = int.Parse(arr[i][3]).ToString(); } // Stores the list of GD, GA, and GF Dictionary<string, List<int>> table = new Dictionary<string, List<int>>(); // Traverse the list for (int i = 0; i < arr.Count; i++) { // Store the list of GA, GF // and GD of first team List<int> li1 = new List<int>() { 0, 0, 0, 0 }; // Store the list of GA, GF // and GD of second team List<int> li2 = new List<int>() { 0, 0, 0, 0 }; // If arr[i][0] is in table if (table.ContainsKey(arr[i][0])) { li1 = table[arr[i][0]]; } // If arr[i][1] is in table if (table.ContainsKey(arr[i][1])) { li2 = table[arr[i][1]]; } // Increment GF by arr[i][2] li1[2] += int.Parse(arr[i][2]); // Increment GA by arr[i][3] li1[3] += int.Parse(arr[i][3]); // Increment GF by arr[i][3] li2[2] += int.Parse(arr[i][3]); // Increment GA by arr[i][2] li2[3] += int.Parse(arr[i][2]); // Update GD li1[1] = li1[2] - li1[3]; li2[1] = li2[2] - li2[3]; // If tie if (arr[i][2] == arr[i][3]) { li1[0]++; li2[0]++; } // If arr[i][0] wins else if (int.Parse(arr[i][2]) > int.Parse(arr[i][3])) { li1[0] += 2; } // If arr[i][1] wins else if (int.Parse(arr[i][2]) < int.Parse(arr[i][3])) { li2[0] += 2; } // Update list in table table[arr[i][0]] = li1; table[arr[i][1]] = li2; } // Traverse the sorted table in the given priority foreach (KeyValuePair<string, List<int>> kvp in table.OrderByDescending(key => key.Value[0]) .ThenByDescending(key => key.Value[1]) .ThenByDescending(key => key.Value[2]) .ThenBy(key => key.Key)) { // Print the team name Console.WriteLine(kvp.Key); } } // Driver Code static void Main(string[] args) { // Input List<List<string>> arr = new List<List<string>>() { new List<string> { "Spain", "England", "3", "0" }, new List<string> { "England", "France", "1", "1" }, new List<string> { "Spain", "France", "0", "2" } }; RankTeams(arr); } }// This codeis contributed by adityashatmfh |
Javascript
// Function to find the ranking of teamsfunction RankTeams(arr) { // Traverse the list arr for (let i = 0; i < arr.length; i++) { // arr[i][0] is equal to arr[i][1] if (arr[i][0] === arr[i][1]) { console.log("Invalid"); return; } // Convert the goal to integer arr[i][2] = parseInt(arr[i][2]); arr[i][3] = parseInt(arr[i][3]); } // Stores the list of GD, GA, and GF let table = {}; // Traverse the list for (let i = 0; i < arr.length; i++) { // Store the list of GA, GF // and GD of first team let li1 = [0, 0, 0, 0]; // Store the list of GA, GF // and GD of second team let li2 = [0, 0, 0, 0]; // If arr[i][0] is in table if (table[arr[i][0]]) { li1 = table[arr[i][0]]; } // If arr[i][1] is in table if (table[arr[i][1]]) { li2 = table[arr[i][1]]; } // Increment GF by arr[i][2] li1[2] += arr[i][2]; // Increment GA by arr[i][3] li1[3] += arr[i][3]; // Increment GF by arr[i][3] li2[2] += arr[i][3]; // Increment GA by arr[i][2] li2[3] += arr[i][2]; // Update GD li1[1] = li1[2] - li1[3]; li2[1] = li2[2] - li2[3]; // If tie if (arr[i][2] === arr[i][3]) { li1[0] += 1; li2[0] += 1; } // If arr[i][0] wins else if (arr[i][2] > arr[i][3]) { li1[0] += 2; } // If arr[i][1] wins else if (arr[i][2] < arr[i][3]) { li2[0] += 2; } // Update list in table table[arr[i][0]] = li1; table[arr[i][1]] = li2; } // Traverse the sorted table in the given priority for (let [key, value] of Object.entries(table).sort((a, b) => b[1][0] - a[1][0] || b[1][1] - a[1][1] || b[1][2] - a[1][2] || a[0].localeCompare(b[0]))) { // Print the team name console.log(key); }}// Driver Code// Inputlet arr = [['Spain', 'England', '3', '0'], ['England', 'France', '1', '1'], ['Spain', 'France', '0', '2']]RankTeams(arr)// This code is contributed by Aditya Sharma |
Output:
France Spain England
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
