Moving items with the next lower value

Question

Given an array of a positive integer, we need to exchange each element with the first element that is smaller than it (the current element) when moving from left to right.

Example

{ 3 , 5 , 12, 2 ,11 } { 2 , 3 , 5 , 11, 12 } 

Brute force simulation for a better understanding of the problem

 { 5, 11, 2, 7, 2 } After first exchange { 2, 11, 5, 7, 2} After second exchange { 2, 5, 11, 7, 2} After third exchange { 2, 5, 7, 11, 2} After fourth exchange { 2, 5, 7, 2, 11} 

Can anyone think of a solution that is better than O (n ^ 2). At first I thought about maintaining a double-ended queue, and when we travel from the first element to the right, we can try to keep the next smallest element of the other between them.

As in the first case, I will do something like this

while i am finding next element of 3, I will maintain a curr_next to 5. If before encountering the next small element for 3, i encounter one of 5, then I will enqueue it but it hardly improve the performance and still O(n^2)

EDIT: we need to move from left to right. Modeling the first example -

 { _3_ , 5 , 12, 2 ,11 } { 2, _5- , 12, 3, 11 } { 2, 3, _12_ , 5, 11 } { 2, 3, 5, _12_, 11 } { 2, 3, 5, 11 , 12 } 

Answer 1

I can offer a solution with O(n*logn) complexity based on using Segment trees .

Algorithm:

• Build an array of pairs (value, index), which is formed from the values ​​and corresponding indices of the elements of the original array. Let me call it array_2

• Sort the resulting array by value.

• Build the Segment Tree in this array, which allows us to find the element with the minimum index for a given interval. Let me call him SegmentTree

• Go through the array of values ​​sequentially (the one that was originally set). For each element of array[ i ] click the element that you want to change as follows:

  4.1. Find the value of the current element in array_2 using a binary search. Let him be in some position k . After that, all elements in array_2 below position k are elements in the original array that are smaller than the current one. As you will see later, they all also have a larger index than the current one (because after the i-th step, we will delete the element with index i from array_2 ).

  4.2. Now we need to find the element with the minimum index in array_2 on the interval [0, k-1] . This can be done by SegmentTree built in step 2. After we get the element with the minimum index, we will perform the corresponding swap in the original array, change the indices of these elements in array_2 (because they were changed to the original array).

  4.3. Perform two update operations in SegmentTree - delete the element with the index being processed in the source array and update the index value of the element that has been replaced by the current index being processed.

After performing steps 4.1 - 4.3 n times we get the target array.

Complexity:

We go through the original array - n iterations. For each iteration, we perform a binary search, a SegmentTree request, and two SegmentTree updates, each of which takes logn time to execute. Summary O(n*logn) .

Answer 2

The problem is not very simple. After we exchange two elements, do we continue from the same position and move to the right when a smaller element is not found? Or do we move immediately after the exchange? In the first case, we get a sorted array.

In the second case, I would keep a balanced tree of searching for elements and indexes. Start with the leftmost element, repeat the following steps:

• Set i = 0, N = length A
• Loop until i <n
  • Add current item to tree with its index
  • Set L = -1
  • Repeat these steps
    • Find the smallest element greater than A [I] in the tree.
    • If such an element is A [K] and K> L
      • swapping A [I] and A [K] in the array
      • remove A [K] from the tree (it will no longer change)
      • update index of new A [I] in the tree
      • set L = K
    • If there is no such element, finish and increment I

The complexity of this is probably O (n log n) or something else. This is unverified and unproven, use at your own risk.