MediumNo. 2497
Maximum Star Sum of a Graph — LeetCode 2497 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Graph, Array, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There is an undirected graph consisting of n nodes numbered from 0 to n - 1. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node.
Example
- Input
- vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
- Output
- 16
- Explanation
- The above diagram represents the input graph.
Python solution
class Solution:
def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
g = defaultdict(list)
for a, b in edges:
if vals[b] > 0:
g[a].append(vals[b])
if vals[a] > 0:
g[b].append(vals[a])
for bs in g.values():
bs.sort(reverse=True)
return max(v + sum(g[i][:k]) for i, v in enumerate(vals))Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2497. Maximum Star Sum of a Graph is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1686 | Stone Game VI | Medium |
Frequently asked questions
- How hard is LeetCode 2497. Maximum Star Sum of a Graph?
LeetCode 2497. Maximum Star Sum of a Graph is rated Medium on LeetCode.
- What topics does LeetCode 2497. Maximum Star Sum of a Graph cover?
LeetCode 2497. Maximum Star Sum of a Graph is tagged Greedy, Graph, Array, Sorting and Heap (Priority Queue) on LeetCode.