2049. Count Nodes With the Highest Score LeetCode Solution

In this guide, you will get 2049. Count Nodes With the Highest Score LeetCode Solution with the best time and space complexity. The solution to Count Nodes With the Highest Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Nodes With the Highest Score solution in C++
Count Nodes With the Highest Score solution in Java
Count Nodes With the Highest Score solution in Python
Additional Resources

2049. Count Nodes With the Highest Score LeetCode Solution image

Problem Statement of Count Nodes With the Highest Score

There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n – 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1.
Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.
Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
– The score of node 0 is: 3 * 1 = 3
– The score of node 1 is: 4 = 4
– The score of node 2 is: 1 * 1 * 2 = 2
– The score of node 3 is: 4 = 4
– The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
– The score of node 0 is: 2 = 2
– The score of node 1 is: 2 = 2
– The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints:

n == parents.length
2 <= n <= 105
parents[0] == -1
0 <= parents[i] <= n – 1 for i != 0
parents represents a valid binary tree.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2049. Count Nodes With the Highest Score LeetCode Solution in C++

class Solution {
 public:
  int countHighestScoreNodes(vector<int>& parents) {
    int ans = 0;
    vector<vector<int>> tree(parents.size());

    for (int i = 0; i < parents.size(); ++i) {
      if (parents[i] == -1)
        continue;
      tree[parents[i]].push_back(i);
    }

    dfs(tree, 0, 0, ans);
    return ans;
  }

 private:
  int dfs(const vector<vector<int>>& tree, int u, long&& maxScore, int& ans) {
    int count = 1;
    long score = 1;
    for (const int v : tree[u]) {
      const int childCount = dfs(tree, v, std::move(maxScore), ans);
      count += childCount;
      score *= childCount;
    }
    const int aboveCount = tree.size() - count;
    score *= max(aboveCount, 1);
    if (score > maxScore) {
      maxScore = score;
      ans = 1;
    } else if (score == maxScore) {
      ++ans;
    }
    return count;
  }
};
/* code provided by PROGIEZ */

2049. Count Nodes With the Highest Score LeetCode Solution in Java

class Solution {
  public int countHighestScoreNodes(int[] parents) {
    List<Integer>[] tree = new List[parents.length];

    for (int i = 0; i < tree.length; ++i)
      tree[i] = new ArrayList<>();

    for (int i = 0; i < parents.length; ++i) {
      if (parents[i] == -1)
        continue;
      tree[parents[i]].add(i);
    }

    dfs(tree, 0);
    return ans;
  }

  private int ans = 0;
  private long maxScore = 0;

  private int dfs(List<Integer>[] tree, int u) {
    int count = 1;
    long score = 1;
    for (final int v : tree[u]) {
      final int childCount = dfs(tree, v);
      count += childCount;
      score *= childCount;
    }
    final int aboveCount = tree.length - count;
    score *= Math.max(aboveCount, 1);
    if (score > maxScore) {
      maxScore = score;
      ans = 1;
    } else if (score == maxScore) {
      ++ans;
    }
    return count;
  }
}
// code provided by PROGIEZ

2049. Count Nodes With the Highest Score LeetCode Solution in Python

class Solution:
  def countHighestScoreNodes(self, parents: list[int]) -> int:
    tree = [[] for _ in range(len(parents))]

    for i, parent in enumerate(parents):
      if parent == -1:
        continue
      tree[parent].append(i)

    ans = 0
    maxScore = 0

    def dfs(u: int) -> int:  # Returns node count
      nonlocal ans
      nonlocal maxScore
      count = 1
      score = 1
      for v in tree[u]:
        childCount = dfs(v)
        count += childCount
        score *= childCount
      score *= len(parents) - count or 1
      if score > maxScore:
        maxScore = score
        ans = 1
      elif score == maxScore:
        ans += 1
      return count

    dfs(0)
    return ans
 # code by PROGIEZ