### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Time series queries challenge

Sharing is caring!

Problem statement
A time series is a series of data points indexed in time order. They are commonly used in the financial world, especially in stock markets.

In this challenge you are working with a time series of stock prices. You are given $n$ historical records $(t_i, p_i)$ where the stock at time $t_i$ had a price $p_i$. You have to answer $2$ types of $q$ queries of the form :

1. For type $1$, given a value $v$, when was the first time that the price of the stock was at least $v$?

2. For type $2$, given a value $v$, what’s the maximum price of the stock at a time greater or equal to $v$?

If for any of these queries the answer is not defined, i.e. there are no historical records that match the query, the answer is $-1$.

Input Format
In the first line, there are two space-separated integers $n$ and $q$ denoting the number of historical records and the number of queries, respectively.

The second line contains $n$ space-separated integers denoting the time-stamps $t$. The next line contains $n$ space-separated integers denoting the price of stock $p$, where $i^{th}$ value corresponds to the $i^{th}$ time-stamp.

Next, $q$ lines follow and each of them describes a single query. Each query is given as two space-separated integers. The first of them is either $1$ or $2$ and denotes the type of the query followed by a single integer $v$ denoting the value to be queried.

Constraints
$1 \le n \le 10^5$
$1 \le q \le 10^5$
$1 \le t_i \le 10^9$
$1 \le p_i \le 10^9$
$1 \le v \le 10^9$
$t_i \textless t_{i+1}\ for\ 0 \le i \textless n - 1$

Output Format
For each of the $q$ queries, print the answer on a new line. If the answer is not defined, print $-1$.

Sample Input 0

Sample Output 0

Explanation 0
In the sample, there are $5$ data records and $5$ queries to answer. At time $1$ the price was $5$, at time $2$ the price was $3$, at time $4$ the price was $12$, at time $8$ the price was $1$, and finally, at time $10$ the price was $10$.

In the first query, we are asked for the minimum time at which the price was at least $10$. The answer is $4$ because at this time the price was $12$ and there is no earlier time with a price at least $10$.

In the second query, we are asked for the minimum time at which the price was at least $4$. The answer is $1$ because the price at this time was $5$ which is greater than $4$.

In the third query, we are asked for the maximum price at time $8$ or greater. The answer is $10$ because there are two data records with time at least $8$ and the highest price among them is $10$.

In the fourth query, we are asked for the maximum price at time $3$ or greater. The answer here is $12$.

In the last query, we are asked for the minimum time at which the price was at least $13$. Since there is no data record with price $13$ or greater, the answer is $-1$.

Solution
For the algorithm we will use a Binary Search Tree for query type 1 and Binary Search in range for query type 2.

So lets go ahead and implement a very simple Binary Search Tree (BST) data structure:

The BST implementation will take the price of a stock as a key and the time as value. It also has a `toString()` method to pretty print our BST and a `search(int v)` method to return the first value of a node that has `key >= v`. This will answer any queries of type 1. We then go on to implement a helper function that constructs a BST from our given arrays `t` and `p`:

For queries of type 2 we will use a simple Binary Search with range algorithm on our time array `t`. That is, we will search `t` for first `t[i]` with `t[i] >= v` and return `i`:

We also construct a precomputed array, `maxPriceFromIndex`, with `maxPriceFromIndex[i]` holding the maximum price starting from index `i` till index `n-1`:

Finally, we can combine the two algorithms to get our solution to the problem:

The full source code to the problem is listed below. It also includes a brute force solution.

Full code