# Can you simulate the following process in $O(N.log N)$

Given an array $$A[]$$ of N integers.

pseudocode:

• Traverse from left to right of this array.
• Let's say you are standing at index $$j$$.
• For each index i=1 to i=j-1, increment all $$A[i]$$ by $$1$$ if and only if $$A[i] \ge A[j]$$.
• Once done for all $$i move over to the next $$j$$ ie $$j=j+1$$

For example lets start with: $$7, 5, 2, 1, 8$$(1-indexed)

at $$j=2 -> 8, 5, 2, 1, 8 (A[1] >= A[2])$$

at $$j=3 -> 9, 6, 2, 1, 8 (A[1], A[2] >= A[3])$$

at $$j=4 -> 10, 7, 3, 1, 8 (A[1], A[2], A[3] >= A[4])$$

at $$j=5 -> 11, 7, 3, 1, 8 (A[1] >= A[5])$$

$$11, 7, 3, 1, 8$$ is the answer

Python code $$O(N^2)$$. (Note: python list is 0-indexed so printed $$j+1$$ to match the above 1-indexed example):

A = [7, 5, 2, 1, 8]
N = len(A)

for j in range(1, N):
for i in range(j):
if A[i] >= A[j]:
A[i] += 1
print("at j = ", j + 1, "->", A)


• Could you clarify the process? Perhaps give quadratic pseudocode? Commented Apr 26, 2023 at 6:02
• Sorry, but your clarification is more obscuring than the opposite.
– user16034
Commented Apr 26, 2023 at 9:38
• it is still not clear what order the A[i] are incremented and the A[i]>=A[j] comparison is made (in the case of there being many such i positions). It should also probably be mentioned whether you are working with a 0-indexed array or starting at 1. It is also not clear what "All A[i]" means. Do you mean all A[k] where k!=j? You have already used 'i' to mean the specific index which is being compared
– JimN
Commented Apr 26, 2023 at 15:06
• @sibillalazzerini The code was not available when I added the comment. Just the very poor plain-language description
– JimN
Commented Apr 27, 2023 at 3:03
• @sibillalazzerini, I think the the tone of your comment is a little inappropriate. This might be the reason for the downvotes. If this continues this can lead for this question to be closed. Clarification is often times needed by those who want to help you. So please be patient. Commented Apr 27, 2023 at 3:15

Since the operation "add 1 to all values greater than or equal to i" preserves order, you can augment a self balancing BST with this operation. While the particulars are dependent on how the balancing is done, the idea is to keep in each node how much you need to add to its subtree, and push it to its children when you touch it.

Once you have such a tree, you can maintain all values up to the current index in it, and implement the algorithm in $$O(\log n)$$ per step.

In pseudocode:

1. Initialize $$T$$ to be an empty self balancing BST.
2. For $$j = 1 \to n$$:
1. Apply to $$T$$ the operation "add 1 to all values greater than or equal to $$A[j]$$"
2. Insert $$A[j]$$ to $$T$$, with metadata $$j$$.
3. For every node $$v$$ in the tree
1. Set $$A[v.\text{metadata}] = v.\text{value}$$
4. Return A
• @Russel The indices in the original array are saved as metadata (so we can recover the correct order in the end), but they don't affect the ordering in the BST Commented Apr 27, 2023 at 2:27
• But isn't it needed to update only those indices $i \lt j$ if $A[i] \geq A[j]$? If elements are used as keys then wouldn't it be difficult to do the update in $O(\log n)$ since non-contiguous elements in the original array might be on the same subtree? That is, some values in the subtree should not be updated since their index in the original array is greater than $j$, even if their values are greater than or equal to $A[j]$. Commented Apr 27, 2023 at 2:53
• It would be great if you could add a small working code, it would clear all these doubts. Commented Apr 27, 2023 at 3:03
• @sibillalazzerini I've added pseudocode. Commented Apr 27, 2023 at 3:57
• @CommandMaster I haven't done BST update with lazy propagation. I have done similar stuff for segment trees only but should be possible for BST as well. Commented Apr 27, 2023 at 4:21