0

I have been practicing problem solving and I cant seem to get anywhere for this one...

Imagine I have an array like: {1, 2, 4 ,3}. The only operation I can perform is moving the value at the 0th index somewhere else in the array. This is not a swap operation, the value simply "squeezes" itself between two other numbers. What is the minimum number of these operations I can make to sort the array. In the given example, the solution would be 3...

  • (1, 2, 3, 4) => (2, 4, 1, 3) => (4, 1, 2, 3) => (1, 2 ,3, 4)

============================================================

It is similar to this problem: https://www.geeksforgeeks.org/count-minimum-number-move-front-moves-sort-array/

But I can only move items from the front instead of bringing them to the front.

I appreciate any help or tips to point me in the right direction. This one has been annoying me for a few days. Thanks!

Improve this question
1
  • 1
    Isn't this from the USACO going on right now.. Commented Jan 21, 2019 at 23:22

2 Answers 2

Reset to default
2

Find the longest properly ordered suffix of the array, i.e. the longest suffix that doesn't contain any inversions. Everything before that suffix will have to be moved exactly once.

Lets say you have w elements before the properly ordered suffix. Element w-1 (0-based) must be larger than element w, so it will definitely have to move, and you will have to move all the w-1 elements that precede it just to get to it. So moving w elements is necessary.

All those w-1 elements can be placed after element w-1 in their proper order, so after element w-1 is moved, the array will be sorted. So moving w elements is sufficient.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I think I am partially seeing what you are saying. Can you use the example I gave, combined with your solution, to help me better understand?
In [1,2,4,3], [3] is the longest properly ordered suffix. Everything before 4 will have to move past the 4 to make [4,1,2,3] and then you move the 4 into the right place to get [1,2,3,4] -- 3 moves. If you start with [1,4,2,3], then [2,3] is the longest properly ordered suffix and you have to move the first 2 elements.
Okay, I understand much better. I have an array of [1, 4, 2, 3, 5, 6], what would the longest properly ordered suffix be here? (for further understanding). Would it be the [5, 6] or the [2, 3, 5, 6]?
2,3,5,6. Those are properly ordered
0

If you look at the problem starting from the end (sorted) to the beginning, right to left in your example, you can see that this is move to front. So, use the same (geeksforgeeks) algorithm as move to front, but the expectedItem is the value original_arr[n] rather than n. Output those moves in reverse order.

Improve this answer

2 Comments

I see how the solution is reverse IS a move to front, exactly like the geeksforgeeks algorithm. I think the difference is that that algorithm is working towards a sorted array, moving to front. But we are moving AWAY from a sorted array moving to front with an end goal that can change. Wouldn't that not allow this to work?
Ok, so you see that the solution in reverse is the same as move-to-front, so it's the same number of moves, right? You can just use the same algorithm as-is.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.