Last active
May 10, 2020 17:23
-
-
Save Gowtham-369/9c0d131fe2e4837ebf9dd454b351386b to your computer and use it in GitHub Desktop.
Day9 : 30 Day LeetCode may challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int findJudge(int N, vector<vector<int>>& trust) { | |
unordered_map<int,pair<int,int>>mp; | |
//pair<int,int> for outgoing(trust[i][0]) and incoming(trust[i][1]) | |
//judge has incoming = N-1 and outgoing = 0 | |
int n = trust.size(); | |
for(int i=0; i<n; i++){ | |
mp[trust[i][0]].first++;//first for outgoing from a number | |
mp[trust[i][1]].second++;//second for incoming to a number | |
} | |
for(int i=1; i<=N; i++){ | |
if (mp[i].first == 0 && mp[i].second == N-1) | |
return i; | |
} | |
return -1; | |
} | |
}; | |
/* | |
vector<int> in(N + 1), out(N + 1); | |
for (auto a : trust) { | |
++out[a[0]]; | |
++in[a[1]]; | |
} | |
for (int i = 1; i <= N; ++i) { | |
if (in[i] == N - 1 && out[i] == 0) return i; | |
} | |
return -1; | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. | |
If the town judge exists, then: | |
The town judge trusts nobody. | |
Everybody (except for the town judge) trusts the town judge. | |
There is exactly one person that satisfies properties 1 and 2. | |
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. | |
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1. | |
Example 1: | |
Input: N = 2, trust = [[1,2]] | |
Output: 2 | |
Example 2: | |
Input: N = 3, trust = [[1,3],[2,3]] | |
Output: 3 | |
Example 3: | |
Input: N = 3, trust = [[1,3],[2,3],[3,1]] | |
Output: -1 | |
Example 4: | |
Input: N = 3, trust = [[1,2],[2,3]] | |
Output: -1 | |
Example 5: | |
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] | |
Output: 3 | |
Note: | |
1 <= N <= 1000 | |
trust.length <= 10000 | |
trust[i] are all different | |
trust[i][0] != trust[i][1] | |
1 <= trust[i][0], trust[i][1] <= N |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment