Finding the Diameter of an N-Ary Tree: the "To-And-Thru" approach

-
Hello folks, this is a problem that exemplifies a technique that I like to call the To-And-Thru. We want to find the diameter of an N-ary tree (meaning a tree where each node has 0, 1 or more children). Take a look: https://leetcode.com/problems/diameter-of-n-ary-tree/

What you want is a near-linear solution in the number of nodes. If you assume that the tree has N nodes, and that each node has an average of LogN children, then the To-And-Thru algorithm below will run in O(N * (LogN)^2) time. Not really linear, but something that seems to be closer to NLogN.

The idea is the following:
  1. Post-Order DFS
  2. For each node, compute the following:
    1. The longest path TO the node
    2. The longest path THRU the node
  3. The above computation will take LogN*LogN since there are two nested loops (I guess there might be a way to reduce this to LogN, meaning one loop)
  4. As you compute 2.1 and 2.2, your diameter will be the Max
See figure below. Works well enough. Code is down below, stay safe, stay motivated!!! ACC



public class Solution {
    public int Diameter(Node root)
    {
        int maxThruNode = 0;
        int maxToNode = 0;
        int diameter = 0;

        Diameter(root, ref maxThruNode, ref maxToNode, ref diameter);

        return diameter > 0 ? diameter - 1 : diameter; //I'm counting the number of nodes in the path. Number of edges is #nodes-1
    }

    private void Diameter(Node node,
                          ref int maxThruNode,
                          ref int maxToNode,
                          ref int diameter)
    {
        if (node == null) return;

        if (node.children.Count == 0)
        {
            maxThruNode = 1;
            maxToNode = 1;
            return;
        }

        int[] childMaxThruNode = new int[node.children.Count];
        int[] childMaxToNode = new int[node.children.Count];

        int index = 0;
        foreach (Node child in node.children)
        {
            Diameter(child, ref childMaxThruNode[index], ref childMaxToNode[index], ref diameter);
            index++;
        }

        maxThruNode = 0;
        maxToNode = 0;
        for (int i = 0; i < childMaxThruNode.Length; i++)
        {
            maxToNode = Math.Max(childMaxToNode[i] + 1, maxToNode);
            diameter = Math.Max(maxToNode, diameter);
            for (int j = i + 1; j < childMaxThruNode.Length; j++)
            {
                maxThruNode = Math.Max(childMaxToNode[i] + childMaxToNode[j] + 1, maxThruNode);
                maxToNode = Math.Max(childMaxToNode[i] + 1, maxToNode);
                maxToNode = Math.Max(childMaxToNode[j] + 1, maxToNode);
                diameter = Math.Max(maxThruNode, diameter);
                diameter = Math.Max(maxToNode, diameter);
            }
        }
    }
}

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more