A smart thermostat stores its distinct historical setpoints in a binary search tree. Starting from an empty tree, the setpoints are inserted one at a time in the order given (standard BST insertion: go left when the new value is smaller than the current node, otherwise go right). Given an inclusive band [lo, hi], report how many stored setpoints x satisfy lo <= x <= hi.
Line 1: an integer n, the number of setpoints.
Line 2: n space-separated distinct integers, the setpoints in insertion order.
Line 3: two space-separated integers lo and hi with lo <= hi.
A single integer: the count of stored setpoints within [lo, hi].
Example 1
Input
6 40 20 60 10 30 50 25 55
Expected
3
Explanation
Stored setpoints in [25, 55] are 30, 40, and 50, so the count is 3.
Example 2
Input
5 5 2 8 1 9 100 200
Expected
0
Explanation
No stored setpoint lies in [100, 200], so the count is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →