Modified counting sort algorithm?

Question

So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have sorted the array with counting sort.

The question is: how can I now sort the modified array in $O(k)$?

So far: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C[j+1] - C[j]$ you have the number of elements in the respective interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array.

How can I understand which element from $A$ is reduced only by looking at $C$?

Example:

Sorted $A[4] = \{1,3,4,4\}$, reduce let`s say $j = 2$ with $A[2] = 4$ by $x \in \{1, \dots , 4\}$. Let $x = 4$ then we have $A[4] = \{1,3,0,4\}$. How can I sort it now in $O(k)$ like $A[4] = \{0,1,3,4\}$?

Answer 1

How can I understand which element from A is reduced only by looking at C?

I guess you can make $C$ array two-dimensional $C[2][n]$ and in the second array you will initially (and after the counting step) store 0-es only. (This means when counting you will fill only the $C[0][n])

After, the counting step, your $C$ array should look like (taking the example above):

0 1 0 0 2  <- count of the elements with value i (i >= 0)
0 0 0 0 0  <- flag if the i-th element has been reduced.

When you reduce an element with value $j$, you will do:

1. $C[0][j]$--; // decrease the count of $j$

2. $C[0][j - x]++$; // increase the count of $(j - x)$

3. $C[1][j]$ = 1; // set $j$ as decreased

This way, when you want to check if a value $j$ was reduced, you can just get the value of $C[1][j]$ and check if it is $1$. The complexity of this will be $O(1)$.

How can I sort it now in $O(k)$?

For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, shift the decreased element to the left or to the right.

Answer 2

Here is an example. Suppose that the sorted array looks like this:

$$ 0000111222233444. $$

Now we reduce one of the $3$ entries to $1$. The new sorted array is

$$ 0000111122223444. $$

Let's put them side by side:

$$ 0000111222233444 \\ 0000111\mathbf{1}222\mathbf{2}3444 $$

The number of changes is bounded by the number of distinct elements (presumably, your $k$). Moreover, you can find the indices of the changes using your array $C$. This allows you to update the sorted array in time $O(k)$. I'm leaving the details to you.