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

As a complement to the other answers: if you can only have the array, then you cannot indeed guarantee the operation will be constant-time; but because the array is sorted, you can find the end of a run of identical numbers in log n operations, not in n operations. This is simply a binary search.

If we expect most runs of numbers to be short, we should use galloping search, which is a variant where we first find the bounds by looking at positions +1, +2, +4, +8, +16, etc. and then doing binary search inside. You would get a time that is often constant (and extremely fast if the item is unique) but can grow up to log n. Unless for some reason long runs of identical numbers remain common even after many updates, this might outperform any solution that requires keeping additional data.

Answer 2

I think that it is possible without using a hashtable. I have an implementation here:

#include <cstdio>
#include <vector>
#include <cassert>

// This code is a solution for http://stackoverflow.com/questions/19957753/maintain-a-sorted-array-in-o1
//
// """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)?"""


// The obvious implementation, which has O(n) worst case increment.
class LinearIncrementor
{
public:
    LinearIncrementor(int numElems);
    int valueAt(int index) const;
    void incrementAt(int index);
private:
    std::vector<int> m_values;
};

// Free list to store runs of same values
class RunList
{
public:
    struct Run
    {
        int m_end;   // end index of run, inclusive, or next object in free list
        int m_value; // value at this run
    };

    RunList();
    int allocateRun(int endIndex, int value);
    void freeRun(int index);
    Run& runAt(int index);
    const Run& runAt(int index) const;
private:
    std::vector<Run> m_runs;
    int m_firstFree;
};

// More optimal implementation, which increments in O(1) time
class ConstantIncrementor
{
public:
    ConstantIncrementor(int numElems);
    int valueAt(int index) const;
    void incrementAt(int index);
private:
    std::vector<int> m_runIndices;
    RunList m_runs;
};

LinearIncrementor::LinearIncrementor(int numElems)
    : m_values(numElems, 0)
{
}

int LinearIncrementor::valueAt(int index) const
{
    return m_values[index];
}

void LinearIncrementor::incrementAt(int index)
{
    const int n = static_cast<int>(m_values.size());
    const int value = m_values[index];
    while (index+1 < n && value == m_values[index+1])
        ++index;
    ++m_values[index];
}

RunList::RunList() : m_firstFree(-1)
{
}

int RunList::allocateRun(int endIndex, int value)
{
    int runIndex = -1;
    if (m_firstFree == -1)
    {
        runIndex = static_cast<int>(m_runs.size());
        m_runs.resize(runIndex + 1);
    }
    else
    {
        runIndex = m_firstFree;
        m_firstFree = m_runs[runIndex].m_end;
    }
    Run& run = m_runs[runIndex];
    run.m_end = endIndex;
    run.m_value = value;
    return runIndex;
}

void RunList::freeRun(int index)
{
    m_runs[index].m_end = m_firstFree;
    m_firstFree = index;
}

RunList::Run& RunList::runAt(int index)
{
    return m_runs[index];
}

const RunList::Run& RunList::runAt(int index) const
{
    return m_runs[index];
}

ConstantIncrementor::ConstantIncrementor(int numElems) : m_runIndices(numElems, 0)
{
    const int runIndex = m_runs.allocateRun(numElems-1, 0);
    assert(runIndex == 0);
}

int ConstantIncrementor::valueAt(int index) const
{
    return m_runs.runAt(m_runIndices[index]).m_value;
}

void ConstantIncrementor::incrementAt(int index)
{
    const int numElems = static_cast<int>(m_runIndices.size());

    const int curRunIndex = m_runIndices[index];
    RunList::Run& curRun = m_runs.runAt(curRunIndex);
    index = curRun.m_end;
    const bool freeCurRun = index == 0 || m_runIndices[index-1] != curRunIndex;

    RunList::Run* runToMerge = NULL;
    int runToMergeIndex = -1;
    if (curRun.m_end+1 < numElems)
    {
        const int nextRunIndex = m_runIndices[curRun.m_end+1];
        RunList::Run& nextRun = m_runs.runAt(nextRunIndex);
        if (curRun.m_value+1 == nextRun.m_value)
        {
            runToMerge = &nextRun;
            runToMergeIndex = nextRunIndex;
        }
    }

    if (freeCurRun && !runToMerge) // then free and allocate at the same time
    {
        ++curRun.m_value;
    }
    else
    {
        if (freeCurRun)
        {
            m_runs.freeRun(curRunIndex);
        }
        else
        {
            --curRun.m_end;
        }

        if (runToMerge)
        {
            m_runIndices[index] = runToMergeIndex;
        }
        else
        {
            m_runIndices[index] = m_runs.allocateRun(index, curRun.m_value+1);
        }
    }
}

int main(int argc, char* argv[])
{
    const int numElems = 100;
    const int numInc = 1000000;

    LinearIncrementor linearInc(numElems);
    ConstantIncrementor constInc(numElems);
    srand(1);
    for (int i = 0; i < numInc; ++i)
    {
        const int index = rand() % numElems;
        linearInc.incrementAt(index);
        constInc.incrementAt(index);
        for (int j = 0; j < numElems; ++j)
        {
            if (linearInc.valueAt(j) != constInc.valueAt(j))
            {
                printf("Error: differing values at increment step %d, value at index %d\n", i, j);
            }
        }
    }
    return 0;
}

Answer 3

just iterate along the array from the modified element until you find the correct place, then swap. Average case complexity is O(N) where N is the average number of duplicates. Worst case is O(n) where n is the length of the array. As long as N isn't large and doesn't scale badly with n, you're fine and can probably pretend it's O(1) for practical purposes.

If duplicates are the norm and/or scale strongly with n, then there are better solutions, see other responses.

Answer 4

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 5

It's important to be very clear about the requirements; the simplest way is to express the problem as an ADT (Abstract Datatype), listing the required operations and complexities.

Here's what I think you are looking for: a datatype which provides the following operations:

• Construct(n): Create a new object of size n all of whose values are 0.

• Value(i): Return the value at index i.

• Increment(i): Increment the value at index i.

• Least(): Return the index of the element with least value (or one such element if there are several).

• Next(i): Return the index of the next element after element i in a sorted traversal starting at Least(), such that the traversal will return every element.

Aside from the Constructor, we want every one of the above operations to have complexity O(1). We also want the object to occupy O(n) space.

The implementation uses a list of buckets; each bucket has a value and a list of elements. Each element has an index, a pointer to the bucket it is part of. Finally, we have an array of pointers to elements. (In C++, I'd probably use iterators rather than pointers; in another language, I'd probably use intrusive lists.) The invariants are that no bucket is ever empty, and the value of the buckets are strictly monotonically increasing.

We start with a single bucket with value 0 which has a list of n elements.

Value(i) is implemented by returning the value of the bucket of the element referenced by the iterator at element i of the array. Least() is the index of the first element in the first bucket. Next(i) is the index of the next element after the one referenced by the iterator at element i, unless that iterator is already pointing at the end of the the list in which case it is the first element in the next bucket, unless the element's bucket is the last bucket, in which case we're at the end of the element list.

The only interface of interest is Increment(i), which is as follows:

• If element i is the only element in its bucket (i.e. there is no next element in the bucket list, and element i is the first element in the bucket list):

  • Increment the value of the associated bucket.
  • If the next bucket has the same value, append the next bucket's element list to this bucket's element list (this is O(1), regardless of the list's size, because it is just a pointer swap), and then delete the next bucket.

• If element i is not the only element in its bucket, then:

  • Remove it from its bucket list.
  • If the next bucket has the next sequential value, then push element i onto the next bucket's list.
  • Otherwise, the next bucket's value is larger, then create a new bucket with the next sequential value and only element i and insert it between this bucket and the next one.

Answer 6

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;
}

Answer 7

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.

Answer 8

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.

Answer 9

Yes and no.

Yes if the list contains only unique integers, as that means you only need to check the next value. No in any other situation. If the values are not unique, incrementing the first of N duplicate values means that it must move N positions. If the values are floating-point, you may have thousands of values between x and x+1

Answer 10

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.