Maintain a sorted array in O(1)?

Question

We have a sorted array and we would like to increase the value of one index by only 1 unit (array[i]++), such that the resulting array is still sorted. Is this possible in O(1)? It is fine to use any data structure possible in STL and C++.

In a more specific case, if the array is initialised by all 0 values, and it is always incrementally constructed only by increasing a value of an index by one, is there an O(1) solution?

Answer 1

I haven't worked this out completely, but I think the general idea might help for integers at least. At the cost of more memory, you can maintain a separate data-structure that maintains the ending index of a run of repeated values (since you want to swap your incremented value with the ending index of the repeated value). This is because it's with repeated values that you run into the worst case O(n) runtime: let's say you have [0, 0, 0, 0] and you increment the value at location 0. Then it is O(n) to find out the last location (3).

But let's say that you maintain the data-structure I mentioned (a map would works because it has O(1) lookup). In that case you would have something like this:

0 -> 3 

So you have a run of 0 values that end at location 3. When you increment a value, let's say at location i, you check to see if the new value is greater than the value at i + 1. If it is not, you are fine. But if it is, you look to see if there is an entry for this value in the secondary data-structure. If there isn't, you can simply swap. If there is an entry, you look up the ending-index and then swap with the value at that location. You then make any changes you need to the secondary data-structure to reflect the new state of the array.

A more thorough example:

[0, 2, 3, 3, 3, 4, 4, 5, 5, 5, 7] 

The secondary data-structure is:

3 -> 4 4 -> 6 5 -> 9 

Let's say you increment the value at location 2. So you have incremented 3, to 4. The array now looks like this:

[0, 2, 4, 3, 3, 4, 4, 5, 5, 5, 7] 

You look at the next element, which is 3. You then look up the entry for that element in the secondary data-structure. The entry is 4, which means that there is a run of 3's that end at 4. This means that you can swap the value from the current location with the value at index 4:

[0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 7] 

Now you will also need to update the secondary data-structure. Specifically, there the run of 3's ends one index early, so you need to decrement that value:

3 -> 3 4 -> 6 5 -> 9 

Another check you will need to do is to see if the value is repeated anymore. You can check that by looking at the i - 1th and the i + 1th locations to see if they are the same as the value in question. If neither are equal, then you can remove the entry for this value from the map.

Again, this is just a general idea. I will have to code it out to see if it works out the way I thought about it.

Please feel free to poke holes.

UPDATE

I have an implementation of this algorithm here in JavaScript. I used JavaScript just so I could do it quickly. Also, because I coded it up pretty quickly it can probably be cleaned up. I do have comments though. I'm not doing anything esoteric either, so this should be easily portable to C++.

There are essentially two parts to the algorithm: the incrementing and swapping (if necessary), and book-keeping done on the map that keeps track of our ending indices for runs of repeated values.

The code contains a testing harness that starts with an array of zeroes and increments random locations. At the end of every iteration, there is a test to ensure that the array is sorted.

var array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; var endingIndices = {0: 9};  var increments = 10000;  for(var i = 0; i < increments; i++) {     var index = Math.floor(Math.random() * array.length);          var oldValue = array[index];     var newValue = ++array[index];      if(index == (array.length - 1)) {         //Incremented element is the last element.         //We don't need to swap, but we need to see if we modified a run (if one exists)         if(endingIndices[oldValue]) {             endingIndices[oldValue]--;         }     } else if(index >= 0) {         //Incremented element is not the last element; it is in the middle of         //the array, possibly even the first element          var nextIndexValue = array[index + 1];         if(newValue === nextIndexValue) {             //If the new value is the same as the next value, we don't need to swap anything. But             //we are doing some book-keeping later with the endingIndices map. That code requires             //the ending index (i.e., where we moved the incremented value to). Since we didn't             //move it anywhere, the endingIndex is simply the index of the incremented element.             endingIndex = index;         } else if(newValue > nextIndexValue) {             //If the new value is greater than the next value, we will have to swap it              var swapIndex = -1;             if(!endingIndices[nextIndexValue]) {                 //If the next value doesn't have a run, then location we have to swap with                 //is just the next index                 swapIndex = index + 1;             } else {                 //If the next value has a run, we get the swap index from the map                 swapIndex = endingIndices[nextIndexValue];             }              array[index] = nextIndexValue;             array[swapIndex] = newValue;              endingIndex = swapIndex;          } else {         //If the next value is already greater, there is nothing we need to swap but we do         //need to do some book-keeping with the endingIndices map later, because it is         //possible that we modified a run (the value might be the same as the value that         //came before it). Since we don't have anything to swap, the endingIndex is          //effectively the index that we are incrementing.             endingIndex = index;         }          //Moving the new value to its new position may have created a new run, so we need to         //check for that. This will only happen if the new position is not at the end of         //the array, and the new value does not have an entry in the map, and the value         //at the position after the new position is the same as the new value         if(endingIndex < (array.length - 1) &&            !endingIndices[newValue] &&            array[endingIndex + 1] == newValue) {             endingIndices[newValue] = endingIndex + 1;         }          //We also need to check to see if the old value had an entry in the         //map because now that run has been shortened by one.         if(endingIndices[oldValue]) {             var newEndingIndex = --endingIndices[oldValue];              if(newEndingIndex == 0 ||                (newEndingIndex > 0 && array[newEndingIndex - 1] != oldValue)) {                 //In this case we check to see if the old value only has one entry, in                 //which case there is no run of values and so we will need to remove                 //its entry from the map. This happens when the new ending-index for this                 //value is the first location (0) or if the location before the new                 //ending-index doesn't contain the old value.                 delete endingIndices[oldValue];             }         }     }      //Make sure that the array is sorted        for(var j = 0; j < array.length - 1; j++) {         if(array[j] > array[j + 1]) {                     throw "Array not sorted; Value at location " + j + "(" + array[j] + ") is greater than value at location " + (j + 1) + "(" + array[j + 1] + ")";         }     } } 

Answer 2

In a more specific case, if the array is initialised by all 0 values, and it is always incrementally constructed only by increasing a value of an index by one, is there an O(1) solution?

No. Given an array of all 0's: [0, 0, 0, 0, 0]. If you increment the first value, giving [1, 0, 0, 0, 0], then you will have to make 4 swaps to ensure that it remains sorted.

Given a sorted array with no duplicates, then the answer is yes. But after the first operation (i.e. the first time you increment), then you could potentially have duplicates. The more increments you do, the higher the likelihood is that you'll have duplicates, and the more likely it'll take O(n) to keep that array sorted.

If all you have is the array, it's impossible to guarantee less than O(n) time per increment. If what you're looking for is a data structure that supports sorted order and lookup by index, then you probably want an order stastic tree.