Efficiently find elements which are out of place in an otherwise sorted list

Question

I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the value in Col B breaks chronology in the column.

Structure

    *    Col A    *    Col B    *
    *    Opened   *    Moved    *
Row * --------------------------*
 1  * 06/20 10:00 * 06/22 08:10 *
 2  * 06/20 10:30 * 06/22 08:40 *
 3  * 06/21 10:00 * 06/22 08:30 *
 4  * 06/21 11:00 * 06/22 08:50 *

The table is sorted on Col A, from smallest to largest.

The rule is that the oldest open item should be moved first.
Thus, moving some arbitrary item that isn't the oldest open item is illegal.

Example

The item in row 3 was moved at 08:30, but at that time there was an older item (row 2) that should have been moved first. That means that row 3 represents an illegal operation and should be marked or returned.

My case

My data set is in the range of millions of rows. I need an accurate method for finding these illegal operations, but I am a little stuck on how to approach the problem.

The most workable idea I've had so far, I think, is to build a helper column where the data from Col B is sorted lowest to highest, compare this step by step with the original column, and shift the data downwards every time the data doesn't match. This will leave the helper column with blanks indicating illegal operations in the corresponding row in the original dataset.

Another idea was to compare the current, preceeding and following dates - but this has seemingly expensive weaknesses. Although rare it's conceptually possible that several illegal operations can immediately follow each other, meaning that I have to compare some arbitrary higher number of dates (let's say 15 instead of 2 (the preceeding + following)) for each step in a loop.

While one of these sub-optimal ideas probably will do the work, in the sense that the job gets done eventually, I struggle with the thought that there isn't a better way to solve this.

Answer 1

If I'm understanding the problem correctly, you have a list that's supposed to be monotonically increasing (aka sorted), and need to discard any items that break this rule. The trick being, an item that's greater than its predecessor might still be invalid, if its predecessor was invalid.

I'm going to make one additional assumption: the first row is always correct. (Because I don't see any way it could be wrong, and if there is, you can check that by hand in $O(1)$ before running.)

If this is correct, then here's how I would solve it.

define FlagBadItems(timestamps[0..n]):
    last_good = timestamps[0]
    for item in timestamps[1..n]:
        if item < last_good:
            flag item as bad
        else:
            last_good = item

In other words, we keep a variable called last_good which is the last timestamp we know to be correct. Each row is considered bad if it's lower than last_good. If it's bad, last_good remains the same, otherwise, last_good is updated.

This runs in $O(n)$, since there's a single run through the data set, with constant work per iteration. The space complexity is $O(1)$ for overhead plus $O(n)$ for your input list.

Answer 2

Each date represents an event: either something was opened, or something was moved. Thus, if you have $n$ rows in your table, there are $2n$ events.

Sort the events, and scan through them in linear order. Keep track of the set of open items as you go. Each time you hit a "moved" event, you can calculate which was the oldest open item (using that set), and check whether that was the one that was moved or not. In this way, you can find invalid "moved" events.