LeetCode 2497: Maximum Star Sum of a Graph Solution

Master LeetCode problem 2497 (Maximum Star Sum of a Graph), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2497. Maximum Star Sum of a Graph

Medium

Array Greedy Graph Sorting Heap (Priority Queue)

Problem Explanation

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).

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2497 (Maximum Star Sum of a Graph)?

This page provides optimized solutions for LeetCode problem 2497 (Maximum Star Sum of a Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2497 (Maximum Star Sum of a Graph)?

The time complexity for LeetCode 2497 (Maximum Star Sum of a Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2497 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2497 in Java, C++, or Python.

Back to LeetCode Solutions