Memoization II

-
I wrote about memoization many years ago. Memoization is a glorified caching. Here is when it can come handy: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/

1372. Longest ZigZag Path in a Binary Tree
Medium
Given a binary tree root, a ZigZag path for a binary tree is defined as follow:
  • Choose any node in the binary tree and a direction (right or left).
  • If the current direction is right then move to the right child of the current node otherwise move to the left child.
  • Change the direction from right to left or right to left.
  • Repeat the second and third step until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.

Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1]
Output: 0

Constraints:
  • Each tree has at most 50000 nodes..
  • Each node's value is between [1, 100].
Accepted
2,271
Submissions
4,951

I followed the hint in this problem, but unfortunately the solution timed out. In order to work around the timeout, memoization (remembering previous solutions) came handy. This is simply the code for memoization, highlighted below:

private int LongestZigZag(TreeNode node,
                            bool direction /*false: left, true: right*/)
{
    if (node == null) return 0;
    string key = node.GetHashCode().ToString() + direction.ToString();
    if (cache.ContainsKey(key)) return (int)cache[key];
    int val = 1 + LongestZigZag(direction ? node.right : node.left, !direction);
    cache.Add(key, val);
    return val;
}

Basically for each node and each direction (L or R), cache the solution and reuse it. Notice that I used GetHashCode() to create a key for each node, albeit this is strictly not recommended due to the possibility of collisions. But in this case, probably because the input wasn't massive, it worked. Cheers, ACC.


public class Solution
{
    private Hashtable cache = new Hashtable();
    public int LongestZigZag(TreeNode root)
    {
        int retVal = 0;
        Process(root, ref retVal);
        return retVal > 0 ? retVal - 1 : retVal;
    }

    private void Process(TreeNode node, ref int max)
    {
        if (node == null) return;

        max = Math.Max(max, Math.Max(LongestZigZag(node, true), LongestZigZag(node, false)));
        Process(node.left, ref max);
        Process(node.right, ref max);
    }

    private int LongestZigZag(TreeNode node,
                                bool direction /*false: left, true: right*/)
    {
        if (node == null) return 0;
        string key = node.GetHashCode().ToString() + direction.ToString();
        if (cache.ContainsKey(key)) return (int)cache[key];
        int val = 1 + LongestZigZag(direction ? node.right : node.left, !direction);
        cache.Add(key, val);
        return val;
    }
}

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