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?

Solution 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] + ")";
        }
    }
}

Solution 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.

Solution 3

If the values are small, counting sort will work. Represent the array [0,0,0,0] as {4}. Incrementing any zero gives {3,1} : 3 zeroes and a one. In general, to increment any value x, deduct one from the count of x and increment the count of {x+1}. The space efficiency is O(N), though, where N is the highest value.

Solution 4

It depends on how many items can have the same value. If more items can have the same value, then it is not possible to have O(1) with ordinary arrays.

Let's do an example: suppose array[5] = 21, and you want to do array[5]++:

• Increment the item:

  array[5]++
  

  (which is O(1) because it is an array).

  So, now array[5] = 22.

• Check the next item (i.e., array[6]):

  If array[6] == 21, then you have to keep checking new items (i.e., array[7] and so on) until you find a value higher than 21. At that point you can swap the values. This search is not O(1) because potentially you have to scan the whole array.

Instead, if items cannot have the same value, then you have:

• Increment the item:

  array[5]++
  

  (which is O(1) because it is an array).

  So, now array[5] = 22.

• The next item cannot be 21 (because two items cannot have the same value), so it must have a value > 21 and the array is already sorted.

Solution 5

So you take sorted array and hashtable. You go over array to figure out 'flat' areas - where elements are of the same value. For every flat area you have to figure out three things 1) where it starts (index of first element) 2) what is it's value 3) what is the value of next element (the next bigger). Then put this tuple into the hashtable, where the key will be element value. This is prerequisite and it's complexity doesn't really matter.

Then when you increase some element (index i) you look up a table for index of next bigger element (call it j), and swap i with i - 1. Then 1) add new entry to hashtable 2) update existing entry for it's previous value.

With perfect hashtable (or limited range of possible values) it will be almost O(1). The downside: it will not be stable.

Here is some code:

#include <iostream>
#include <unordered_map>
#include <vector>

struct Range {
    int start, value, next;
};

void print_ht(std::unordered_map<int, Range>& ht)
{
    for (auto i = ht.begin(); i != ht.end(); i++) {
        Range& r = (*i).second;
        std::cout << '(' << r.start << ", "<< r.value << ", "<< r.next << ") ";
    }
    std::cout << std::endl;
}

void increment_el(int i, std::vector<int>& array, std::unordered_map<int, Range>& ht)
{
    int val = array[i];
    array[i]++;
    //Pick next bigger element
    Range& r = ht[val];
    //Do the swapping, so last element of that range will be first
    std::swap(array[i], array[ht[r.next].start - 1]);
    //Update hashtable
    ht[r.next].start--;
}

int main(int argc, const char * argv[])
{
    std::vector<int> array = {1, 1, 1, 2, 2, 3};
    std::unordered_map<int, Range> ht;

    int start = 0;
    int value = array[0];

    //Build indexing hashtable
    for (int i = 0; i <= array.size(); i++) {
        int cur_value = i < array.size() ? array[i] : -1;
        if (cur_value > value || i == array.size()) {
            ht[value] = {start, value, cur_value};
            start = i;
            value = cur_value;
        }
    }

    print_ht(ht);

    //Now let's increment first element
    increment_el(0, array, ht);
    print_ht(ht);
    increment_el(3, array, ht);
    print_ht(ht);

    for (auto i = array.begin(); i != array.end(); i++)
        std::cout << *i << " ";


    return 0;
}

View more solutions