2049. Count Nodes With the Highest Score

Here is the discussion post. 

Here is the gist. 

Intuition

I am review unsolved 40 medium level tree algorithms, and then I came cross this algorithm. I thought about the solution for near 10 minutes, and then I decided to study only C# solution shared.

Approach

Here are highlights:

1. Build a graph using hashmap, C# Dictionary class
2. Define three variables inside the class
3. Apply DFS to calculate the score
4. Write a test case for example 1, and debug through the code

I did not come out the idea by myself, so I took extra time to test the following test cases:

1. int[]{-1}, analysis: maxScore = 1, number of nodes = 1
2. int[]{-1, 0}, analysis: maxScore = 1, but number of nodes is 2; Remove 0 or remove 1
3. int{-1, 0, 0}, analysis: maxScore = 2, and number of nodes is 2, remove 1 or remove 2.
4. int[]{-1, 2, 0, 2, 0}, result: 3

        static void Main(string[] args)
        {
            var test = new Solution();

            var result1 = test.CountHighestScoreNodes(new int[]{-1});  // 1
            var result2 = test.CountHighestScoreNodes(new int[]{-1,0}); // maxScore = 1, but number of nodes is 2; two cases, remove 0, remove 1
            var result3 = test.CountHighestScoreNodes(new int[]{-1, 0, 0}); // maxScore = 2, and number of nodes is 2

            var result4 = test.CountHighestScoreNodes(new int[]{-1, 2, 0, 2, 0}); 
        }

Complexity

• Time complexity:

O(N), N is total number of nodes in the tree. Apply post order traversal once.

• Space complexity:

Code

public class Solution {
    Dictionary<int, int[]> children = new Dictionary<int, int[]>();
        long maxScore = 0;
        int  numberNodes = 0;
        
    public int CountHighestScoreNodes(int[] parents)
        {
            int n = parents.Length;
            var lstParents = new List<int>(parents);

            // build a graph based on parents - left or right child - does not matter
            for (int i = 0; i < parents.Length; i++)
            {
                var childNodes = new int[] { -1, -1 };

                // two children
                // 
                var parentNode = parents[i];

                if (children.ContainsKey(parentNode))
                {
                    children[parentNode][1] = i;
                }
                else
                {
                    childNodes[0] = i;
                    children.Add(parentNode, childNodes);
                }
            }

            // Extra - no children 
            // Leaf node 
            for (int i = 0; i < parents.Length; i++)
            {
                var arr = new int[] { -1, -1 };

                if (!children.ContainsKey(i))
                {
                    children.Add(i, arr);
                }
            }

            countNodesDFS(0, n);
            return numberNodes;
        }

        /// <summary>   
        /// Return number of nodes that have the highest score
        /// node's value from 0 to n - 1
        /// </summary>
        /// <param name="root"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        private long countNodesDFS(int root, int n)
        {
            long score = 0;
            long subtreeCount = 0;

            if (root == -1)
            {
                return 0;
            }

            long leftCount = countNodesDFS(children[root][0], n);
            long rightCount = countNodesDFS(children[root][1], n);

            subtreeCount = leftCount + rightCount + 1;
            long remain = n - subtreeCount;
            
            score = (leftCount == 0 ? 1 : leftCount) * (rightCount == 0 ? 1 : rightCount);
            score *= remain == 0 ? 1 : remain;

            if (score > maxScore)
            {
                maxScore = score;
                numberNodes = 1;
            }
            else if (score == maxScore)
            {
                numberNodes++;
            }

            return subtreeCount;
        }        
}