Print the names of the teams in increasing order of their rankings

0 0 9 minutes read

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
Played GF 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 teams
void 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 code
int 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 teams
def 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
 
# Input
arr = [['Spain', 'England', '3', '0'], 
       ['England', 'France', '1', '1'],
       ['Spain', 'France', '0', '2']]
 
RankTeams(arr)

C#

// C# program for the above approach
 
using 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 teams
function 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
 
// Input
let 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 zambiatek!