## [f]izzbuzzer

### 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

```5 5
1 2 4 8 10
5 3 12 1 10
1 10
1 4
2 8
2 3
1 13
```

Sample Output 0

```4
1
10
12
-1
```

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:

```private static class BSTNode {
public int key;
public int value;
public BSTNode left = null;
public BSTNode right = null;

public BSTNode(int key, int value) {
this.key = key;
this.value = value;
}

public BSTNode add(int key, int value) {
if (key <= this.key) {
if (this.left == null) {
this.left = new BSTNode(key, value);
return this.left;
} else {
}
} else {
if (this.right == null) {
this.right = new BSTNode(key, value);
return this.right;
} else {
}
}
}

public int search(int v) {
if (this.key >= v) {
return this.value;
}

if (v > this.key) {
if (this.right != null) {
return this.right.search(v);
}
}

return -1;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");

sb.append(this.key + "->");

if (this.left == null) {
sb.append("null");
} else {
sb.append(this.left.toString());
}

sb.append(", ");

if (this.right == null) {
sb.append("null");
} else {
sb.append(this.right.toString());
}

sb.append("]");
return sb.toString();
}
}
```

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`:

```private static BSTNode priceTimeTree(int[] t, int[] p) {
BSTNode root = new BSTNode(p[0], t[0]);

for (int i = 1; i < p.length; i++) {
}

return root;
}
```

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`:

```private static int binarySearch(int[] t, int l, int h, int v) {
if (l > h) {
return t.length;
} else {
int mid = l + (h - l) / 2;

if (t[mid] >= v) {
return Math.min(mid, binarySearch(t, l, mid - 1, v));
} else {
// Go right
return binarySearch(t, mid + 1, h, v);
}
}
}
```

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

```int[] maxPriceFromIndex = new int[n];
maxPriceFromIndex[n - 1] = p[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxPriceFromIndex[i] = Math.max(p[i], maxPriceFromIndex[i + 1]);
}
```

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

```private static int solve(int type, BSTNode priceTimeTree, int[] maxPriceFromIndex, int[] t, int[] p, int v) {
if (type == 1) {
return priceTimeTree.search(v);
} else {
// Binary search in array t for first t[i] with t[i] >= v
int i = binarySearch(t, 0, t.length - 1, v);
if (i < t.length) {
return maxPriceFromIndex[i];
} else {
return -1;
}
}
}
```

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

Full code

```public class TimeSeriesQueries {

/********************************
* BruteForce
*****************************************/

private static int max(int l, int h, int[] a) {
int ans = a[l];
for (int i = l; i <= h; i++) {
ans = Math.max(ans, a[i]);
}

return ans;
}

private static int bruteForce(int type, int[] t, int[] p, int v) {
if (type == 1) {
for (int i = 0; i < p.length; i++) {
if (p[i] >= v) {
return t[i];
}
}
} else {
for (int i = 0; i < t.length; i++) {
if (t[i] >= v) {
// Find maximum
return max(i, t.length - 1, p);
}
}
}
return -1;
}

/**********************************************************************************/

private static class BSTNode {
public int key;
public int value;
public BSTNode left = null;
public BSTNode right = null;

public BSTNode(int key, int value) {
this.key = key;
this.value = value;
}

public BSTNode add(int key, int value) {
if (key <= this.key) {
if (this.left == null) {
this.left = new BSTNode(key, value);
return this.left;
} else {
}
} else {
if (this.right == null) {
this.right = new BSTNode(key, value);
return this.right;
} else {
}
}
}

public int search(int v) {
if (this.key >= v) {
return this.value;
}

if (v > this.key) {
if (this.right != null) {
return this.right.search(v);
}
}

return -1;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");

sb.append(this.key + "->");

if (this.left == null) {
sb.append("null");
} else {
sb.append(this.left.toString());
}

sb.append(", ");

if (this.right == null) {
sb.append("null");
} else {
sb.append(this.right.toString());
}

sb.append("]");
return sb.toString();
}
}

private static BSTNode priceTimeTree(int[] t, int[] p) {
BSTNode root = new BSTNode(p[0], t[0]);

for (int i = 1; i < p.length; i++) {
}

return root;
}

private static int binarySearch(int[] t, int l, int h, int v) {
if (l > h) {
return t.length;
} else {
int mid = l + (h - l) / 2;

if (t[mid] >= v) {
return Math.min(mid, binarySearch(t, l, mid - 1, v));
} else {
// Go right
return binarySearch(t, mid + 1, h, v);
}
}
}

private static int solve(int type, BSTNode priceTimeTree, int[] maxPriceFromIndex, int[] t, int[] p, int v) {
if (type == 1) {
return priceTimeTree.search(v);
} else {
// Binary search in array t for first t[i] with t[i] >= v
int i = binarySearch(t, 0, t.length - 1, v);
if (i < t.length) {
return maxPriceFromIndex[i];
} else {
return -1;
}
}
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int q = in.nextInt();
int[] t = new int[n];
for (int t_i = 0; t_i < n; t_i++) {
t[t_i] = in.nextInt();
}

int[] p = new int[n];
for (int p_i = 0; p_i < n; p_i++) {
p[p_i] = in.nextInt();
}

BSTNode priceTimeTree = priceTimeTree(t, p);

int[] maxPriceFromIndex = new int[n]; // maxPriceFromIndex[i] contains maximum price starting from index i till index n-1
maxPriceFromIndex[n - 1] = p[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxPriceFromIndex[i] = Math.max(p[i], maxPriceFromIndex[i + 1]);
}

for (int a0 = 0; a0 < q; a0++) {
int type = in.nextInt();
int v = in.nextInt();

System.out.println(solve(type, priceTimeTree, maxPriceFromIndex, t, p, v));
}

in.close();
}
}
```