Binary Search Tree Solution (Runtime: 4ms, Beats 100%)
\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the item with the highest beauty value within a given price ran
![Screenshot 2024-11-12 at 20.22.14.png](https://assets.leetcode.com/users/images/018bdb88-c442-4f79-8064-c69dd05cea2d_1731439612.468659.png)\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the item with the highest beauty value within a given price range for each query. Since items can be inserted in any order and need to be queried based on price, a binary search tree (BST) structure can efficiently store the items, allowing us to search by price in \\(O(\\log N)\\) time on average.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Insert items into a Binary Search Tree (BST):** Each item is added based on its price, and for each price, we only keep the maximum beauty. We recursively add each item, building a tree where nodes with higher prices go to the right and nodes with lower prices go to the left.\n2. **Search for the maximum beauty in the BST for each query:** For each query, traverse the tree to find nodes with prices less than or equal to the query price, and keep track of the highest beauty encountered.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n  - **Average case:** \\(O(N \\log N + Q \\log N)\\), where \\(N\\) is the number of items, and \\(Q\\) is the number of queries.\n  - **Worst case:** \\(O(N^2 + Q \\cdot N)\\) if the BST is unbalanced.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n  - \\(O(N + Q)\\), where \\(N\\) is the space for the BST, and \\(Q\\) is for the result array.\n\n# Code\n```java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        // Initialize the root node of the binary search tree (BST) to store items based on price\n        Node root = null;\n\n        // Insert each item into the BST\n        for (int[] item : items) {\n            int price = item[0];\n            int beauty = item[1];\n            if (root == null) {\n                root = new Node(price, beauty); // Initialize root with the first item\n            } else {\n                root.add(price, beauty); // Insert subsequent items into the BST\n            }\n        }\n\n        int[] result = new int[queries.length];\n\n        // For each query, find the maximum beauty for items priced at or below the query value\n        for (int i = 0; i < queries.length; i++) {\n            int query = queries[i];\n            result[i] = root != null ? root.find(query) : 0;\n        }\n\n        return result;\n    }\n\n    // Define a nested Node class to represent each node in the binary search tree\n    private static class Node {\n        Node left;  // Left child node\n        Node right; // Right child node\n        int price;  // Price of the item\n        int beauty; // Beauty value of the item\n\n        public Node(int price, int beauty) {\n            this.price = price;\n            this.beauty = beauty;\n        }\n\n        // Finds the maximum beauty of an item\n        int find(int price) {\n            Node node = this;\n            int maxBeauty = 0;\n\n            // Traverse the tree to find the maximum beauty for items\n            while (node != null) {\n                if (node.price <= price) {\n                    // update maxBeauty if needed\n                    maxBeauty = Math.max(maxBeauty, node.beauty);\n                    node = node.right; // Move to the right child to find potentially higher prices within the range\n                } else {\n                    node = node.left;\n                }\n            }\n            return maxBeauty;\n        }\n\n        // Adds a new item to the BST based on its price and beauty\n        void add(int price, int beauty) {\n            // If price is greater than current node\'s price, consider adding it to the right\n            if (price > this.price) {\n                // It doesn\'t make sense to add the node with higher price if it\'s beauty is less than current node\'s beauty\n                if (beauty > this.beauty) {\n                    if (this.right != null) {\n                        this.right.add(price, beauty); // Recursive call to add to the right child\n                    } else {\n                        this.right = new Node(price, beauty); // Create new right child if null\n                    }\n                }\n            }\n            // If price is less than or equal to current price, add to the left or update current node\n            else {\n                if (beauty >= this.beauty) {\n                    // Update current node if the new beauty is greater or equal\n                    this.price = price;\n                    this.beauty = beauty;\n                } else {\n                    // Otherwise, add to the left subtree if beauty is not the highest for this price range\n                    if (this.left != null) {\n                        this.left.add(price, beauty);\n                    } else {\n                        this.left = new Node(price, beauty);\n                    }\n                }\n            }\n        }\n    }\n}\n```
['Java']