# Finding a subarray of time series data in which all values are less than X for specified time Y?

The idea is to find an anomalous value (i.e. it's less than X) in time series data (sorted by time), and check if this behavior continues during specified time (Y=2 hours).

If all values in sub-array (which represents 2 hours period) are X, the subarray is returned as a result, and we do not continue further.

Else search continues until such sub-array is found or we have no more data.

Is there an algorithm or family of algorithms that are suited for this task?

Example:

X = 10

Y = 2 hours

Data:

(time=00:00, value=4)

(time=01:00, value=4)

(time=02:00, value=11)

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

Result:

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

...during these 2 hours all values were consistently than X=4.

On the other hand, 00:00 - 02:00 range has X=11 at the end, so it isn't included in result.

Update:

There are approx. 1440 data points in the array (1 point per minute x 24 hours).

This shouldn't be a streaming algorithm, all needed data points are already available.

Data points are immutable, values (or time) don't change.

It's important that we use as little memory during the search as possible.

Search is run once a day, so the data is different and does not depend on previous searches.

• How frequently are you doing this kind of search? How large is Y? How many data points are there? What kind of, and how much, preprocessing is acceptable? Does the data structure need to be updatable? We can't give a solid answer without a solid understanding of what you're trying to acheive. – Veedrac Apr 19 '17 at 0:48
You don't need a clever or sophisticated algorithm. It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$.
At time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$. At time $t+1$, when you see the next value, update this length (it either increases by 1, if the new value is less than $X$, or resets to 0, if the new value is at least $X$). Keep track of the longest such window that you saw during the entire scan. If it is longer than $Y$, output it.
This requires very little memory (only an integer to keep track of the length of the window of consecutive values $< X$, and an integer to keep track of the current position in the array). The algorithm should be extremely fast.