Time series queries challenge
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 historical records where the stock at time had a price . You have to answer types of queries of the form :
 For type , given a value , when was the first time that the price of the stock was at least ?

For type , given a value , what’s the maximum price of the stock at a time greater or equal to ?
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 .
Input Format
In the first line, there are two spaceseparated integers and denoting the number of historical records and the number of queries, respectively.
The second line contains spaceseparated integers denoting the timestamps . The next line contains spaceseparated integers denoting the price of stock , where value corresponds to the timestamp.
Next, lines follow and each of them describes a single query. Each query is given as two spaceseparated integers. The first of them is either or and denotes the type of the query followed by a single integer denoting the value to be queried.
Constraints
Output Format
For each of the queries, print the answer on a new line. If the answer is not defined, print .
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 data records and queries to answer. At time the price was , at time the price was , at time the price was , at time the price was , and finally, at time the price was .
In the first query, we are asked for the minimum time at which the price was at least . The answer is because at this time the price was and there is no earlier time with a price at least .
In the second query, we are asked for the minimum time at which the price was at least . The answer is because the price at this time was which is greater than .
In the third query, we are asked for the maximum price at time or greater. The answer is because there are two data records with time at least and the highest price among them is .
In the fourth query, we are asked for the maximum price at time or greater. The answer here is .
In the last query, we are asked for the minimum time at which the price was at least . Since there is no data record with price or greater, the answer is .
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 { return this.left.add(key, value); } } else { if (this.right == null) { this.right = new BSTNode(key, value); return this.right; } else { return this.right.add(key, value); } } } 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++) { root.add(p[i], t[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 n1
:
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 { return this.left.add(key, value); } } else { if (this.right == null) { this.right = new BSTNode(key, value); return this.right; } else { return this.right.add(key, value); } } } 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++) { root.add(p[i], t[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 n1 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(); } }