LeetCode 2497: Maximum Star Sum of a Graph
Problem Description
Explanation:
To solve this problem, we can iterate through all nodes and treat each node as the center of a star graph. We calculate the sum of the values of the center node and its neighbors for each node. We keep track of the k largest sums found so far and return the maximum sum.
- Create an adjacency list to represent the graph.
- Iterate through all nodes.
- For each node, calculate the sum of the values of the center node and its neighbors.
- Update the k largest sums found so far.
- Return the maximum sum among the k largest sums.
Time complexity:
- Constructing the adjacency list: O(n) where n is the number of nodes.
- Iterating through all nodes: O(n).
- Calculating sum for each node: O(d) where d is the degree of the node.
- Finding the k largest sums: O(n log k).
- Overall time complexity: O(n log k).
Space complexity:
- Adjacency list: O(n).
- Other variables: O(k).
- Overall space complexity: O(n).
:
Solutions
class Solution {
public int maxStarSum(int[] vals, int[][] edges, int k) {
int n = vals.length;
List<Integer>[] adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<>();
}
for (int[] edge : edges) {
adjList[edge[0]].add(edge[1]);
adjList[edge[1]].add(edge[0]);
}
PriorityQueue<Integer> pq = new PriorityQueue<>(k, Collections.reverseOrder());
for (int center = 0; center < n; center++) {
int sum = vals[center];
for (int neighbor : adjList[center]) {
sum += vals[neighbor];
}
pq.offer(sum);
if (pq.size() > k) {
pq.poll();
}
}
int maxSum = 0;
while (!pq.isEmpty()) {
maxSum = Math.max(maxSum, pq.poll());
}
return maxSum;
}
}Loading editor...