Leetcode Contest 370

Starting off with contest

It's 8.03 in the morning. Going to attempt Weekly Contest 370.
Target: Solve 2 at least.

Midway Struggles

Leetcode website is very slow today. Happens most of the times at the time of contest.

End Result!

Able to solve 2 questions. Those were pretty easy questions.

Question 1: Find Champion I

_There are n teams numbered from 0 to n - 1 in a tournament.
Given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j that 0 <= i, j <= n - 1 and i != j team i is stronger than team j if grid[i][j] == 1, otherwise, team j is stronger than team i.
Team a will be the champion of the tournament if there is no team b that is stronger than team a.
Return the team that will be the champion of the tournament._

Approach:

I used Map data structure to check the frequency of the nodes as per the given conditions.
Then I returned the node with maximum frequency.

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        map<int, int> mp;
        for(int i = 0 ; i < grid.size() ;i++) {
            for(int j = 0 ; j < grid[0].size() ; j++) {
                if(i!=j) {
                    if(grid[i][j] == 0) {
                        mp[j]++;
                    }else {
                        mp[i]++;
                    }
                }
            }
        }
        int ans = INT_MIN;
        int res = 0;
        for(auto it : mp) {
            cout<<it.first<<" "<<it.second<<endl;
            if(ans < it.second) {
                ans = it.second;
                res = it.first;
            }
        }
        return res;
    }
};

Question 2: Find Champion II

_There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG. You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi in the graph.
A directed edge from a to b in the graph means that team a is stronger than team b and team b is weaker than team a.
Team a will be the champion of the tournament if there is no team b that is stronger than team a.
Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return -1._

Approach:

When I saw thus question , I immediately come up with in-degree things of the nodes.
I find the In-degree of every nodes and returned the node with indegree == 0

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        // vector<int> Adj[n];
        vector<int> inDegree(n, 0);
        for(vector<int> edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // Adj[u].push_back(v);
            inDegree[v]++;
        }

        int champ = -1;
        int cntChamp = 0;

        for(int i = 0 ; i < n ; i++) {
            if(inDegree[i] == 0) {
                if(cntChamp > 0) {
                    return -1;
                }
                champ = i;
                cntChamp++;
            }
        }
        return champ;
    }
};

Now What!

Will try up-solving other 2 questions of the contest. And will definitely try to improve in future contests.

Abhishek😉