How to continuous check if array is sorted after removes/adds/updates of elements

Question

Supposing that a list of n integers is given (The list don't need to be already sorted). How to check if the list is sorted (NON-INCREASING OR NON-DECREASING) after remove ,update or insert values ?

The only thing i can think to solve this problem is keeping a linked list of the numbers with the operations of remove[O(n)],insert[O(n)] and update [O(n)] and a linear check to see if its sorted NON-DECREASING OR NON-INCREASING. Is possible to solve this problem faster ?

Remove,insert and update means that the user will give a position to remove/insert/update and the value with will be inserted, removed or added on the given position.

There will be a query at any moment on the input to ask which state the list is (NON-INCREASING or NON-DECREASING)

Answer 1

Here's the logic of nondecreasing (duplicate it with a twist for nonincreasing).

Keep track of the number of adjacent pairs x, y such that x > y, i.e., decreasing pairs. The list is nondecreasing if and only if this number is zero.

To insert b between a and c (a, c => a, b, c):

num_decreasing_pairs -= a > c
num_decreasing_pairs += a > b
num_decreasing_pairs += b > c

To remove b between a and c (a, b, c => a, c):

num_decreasing_pairs -= a > b
num_decreasing_pairs -= b > c
num_decreasing_pairs += a > c

To update b1 to b2 between a and c (a, b1, c => a, b2, c):

num_decreasing_pairs -= a > b1
num_decreasing_pairs -= b1 > c
num_decreasing_pairs += a > b2
num_decreasing_pairs += b2 > c

All of these statements should be guarded by ifs that check that the examined elements are present (edge cases).

Answer 2

If you maintain a list of linked lists of the values where each sub-linked list is in ascending order you know you have a sorted list when there is only one sub-linked-list.

Now the operations are:-

• remove - if removing from the start or end of a sublist, check if you can now join two sublists into one.
• add - if this breaks a sublist order, split the sublist into two new ones
• update - same as a remove and an add.

[omitting lots of details about linked lists, access to head / tail, count values to get to the correct sub-linked-list quickly, ...]