A brute-force approach for Max BST

-

I've tried this problem before, twice, with no luck. I remember trying an O(N)-time solution, but got wrong answers twice. Decided to go for an N^2 solution, this time it worked. Here is the problem: Largest BST Subtree - LeetCode

333. Largest BST Subtree
Medium

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

  • The left subtree values are less than the value of their parent (root) node's value.
  • The right subtree values are greater than the value of their parent (root) node's value.

Note: A subtree must include all of its descendants.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

 

Example 1:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Example 2:

Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -104 <= Node.val <= 104
Accepted
59,902
Submissions
157,343

The approach that I took was an N^2 one:

1/ Create a method that checks whether a given node is the root of a BST. Do it using post-order (in-order only really works if the tree contains only unique elements). This is an O(N)

2/ As part of (1), make it return the number of nodes in the subtree (no extra time added)

3/ Finally call it for each subnode in the tree. Another O(N)

Combined this would be O(N^2). Since N=10000, we're talking about 10^8. I thought it was going to time out - it didn't. Code is below, cheers, ACC.

public int LargestBSTSubtree(TreeNode root)
{
    int retVal = 0;
    LargestBSTSubtree(root, ref retVal);
    return retVal;
}

private void LargestBSTSubtree(TreeNode node, ref int maxNodes)
{
    if (node == null) return;

    int max = Int32.MinValue;
    int min = Int32.MaxValue;
    int numberNodes = 0;

    if (IsBST(node, ref max, ref min, ref numberNodes))
    {
        maxNodes = Math.Max(maxNodes, numberNodes);
    }

    LargestBSTSubtree(node.left, ref maxNodes);
    LargestBSTSubtree(node.right, ref maxNodes);
}

private bool IsBST(TreeNode node, ref int max, ref int min, ref int numberNodes)
{
    if (node == null) return true;

    int leftMax = Int32.MinValue;
    int leftMin = Int32.MaxValue;
    int leftNumberNodes = 0;
    if (!IsBST(node.left, ref leftMax, ref leftMin, ref leftNumberNodes)) return false;

    int rightMax = Int32.MinValue;
    int rightMin = Int32.MaxValue;
    int rightNumberNodes = 0;
    if (!IsBST(node.right, ref rightMax, ref rightMin, ref rightNumberNodes)) return false;

    if (leftMax >= node.val) return false;
    if (rightMin <= node.val) return false;

    max = node.val;
    max = Math.Max(max, leftMax);
    max = Math.Max(max, rightMax);

    min = node.val;
    min = Math.Min(min, leftMin);
    min = Math.Min(min, rightMin);

    numberNodes = 1 + leftNumberNodes + rightNumberNodes;

    return true;
}

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