Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2374.html
2374. Node With Highest Edge Score
- Difficulty: Medium.
- Related Topics: Hash Table, Graph.
- Similar Questions: Two Sum, Sort Characters By Frequency, Sort Array by Increasing Frequency.
Problem
You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge.
The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].
The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.
Return the node with the highest **edge score. If multiple nodes have the same **edge score, return the node with the smallest index.
Example 1:
Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.
Example 2:
Input: edges = [2,0,0,2]
Output: 0
Explanation:
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.
Constraints:
-
n == edges.length -
2 <= n <= 105 -
0 <= edges[i] < n -
edges[i] != i
Solution (Java, C++, Python)
-
class Solution { public int edgeScore(int[] edges) { int n = edges.length; int[] score = new int[n]; int maxScore = 0; int node = 0; for (int i = 0; i < n; i++) { score[edges[i]] += i; if (score[edges[i]] >= maxScore) { if (score[edges[i]] == maxScore) { node = Math.min(node, edges[i]); } else { node = edges[i]; } maxScore = score[edges[i]]; } } return node; } } ############ class Solution { public int edgeScore(int[] edges) { int n = edges.length; long[] cnt = new long[n]; for (int i = 0; i < n; ++i) { cnt[edges[i]] += i; } int ans = 0; for (int i = 0; i < n; ++i) { if (cnt[ans] < cnt[i]) { ans = i; } } return ans; } } -
class Solution: def edgeScore(self, edges: List[int]) -> int: cnt = Counter() for i, v in enumerate(edges): cnt[v] += i ans = 0 for i in range(len(edges)): if cnt[ans] < cnt[i]: ans = i return ans ############ # 2374. Node With Highest Edge Score # https://leetcode.com/problems/node-with-highest-edge-score/ class Solution: def edgeScore(self, edges: List[int]) -> int: n = len(edges) scores = [0] * n for node, out in enumerate(edges): scores[out] += node res = maxScore = -1 for node, score in enumerate(scores): if score > maxScore: maxScore = score res = node return res -
class Solution { public: int edgeScore(vector<int>& edges) { int n = edges.size(); vector<long long> cnt(n); for (int i = 0; i < n; ++i) { cnt[edges[i]] += i; } int ans = 0; for (int i = 0; i < n; ++i) { if (cnt[ans] < cnt[i]) { ans = i; } } return ans; } }; -
func edgeScore(edges []int) int { n := len(edges) cnt := make([]int, n) for i, v := range edges { cnt[v] += i } ans := 0 for i, v := range cnt { if cnt[ans] < v { ans = i } } return ans } -
function edgeScore(edges: number[]): number { const n = edges.length; const sum = new Array(n).fill(0); for (let i = 0; i < n; i++) { sum[edges[i]] += i; } let res = 0; for (let i = 0; i < n; i++) { if (sum[res] < sum[i]) { res = i; } } return res; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).