# Posts tagged as “BST”

Problem:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.


Example 2:

Input:
flowers: [1,2,3]
k: 1
Output: -1


Note:

1. The given array will be in the range [1, 20000].

Idea:

BST/Buckets

# Solution 1: TLE with latest test cases

## Python

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) – Add a integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

For example:

Idea:

1. Min/Max heap
2. Balanced binary search tree

Time Complexity: