Minimum Moves to Sort a Permutation

Problem Statement

Given an array arr[] containing every integer from 1 to n exactly once, we need to sort the array in ascending order.

In one operation, we can:

Pick any element.
Move it to the beginning, or
Move it to the end.

We need to find the minimum number of operations required to sort the array.

Example

Input:
[2, 1, 3]

Output:
1

Move 1 to the beginning:

[2, 1, 3]
     ↓
[1, 2, 3]

So the answer is 1.

Key Observation

The most important part of this problem is understanding which elements do not need to be moved.

The final sorted array must be:

[1, 2, 3, 4, 5, ..., n]

Suppose some elements are already in the correct relative order:

1, 2, 3

If we leave these elements untouched, we can move all the other elements to the beginning or end.

Therefore, instead of directly finding the elements to move, we find:

The maximum number of elements that can remain untouched.

Then:

Minimum moves = n - maximum elements we can keep

What Sequence Can Be Kept?

The elements we keep must be:

In increasing order.
Consecutive values.

For example:

2, 3, 4, 5

is valid.

But:

1, 3, 4

is not valid because 2 is missing.

Similarly:

2, 4, 5

is not valid.

So we are looking for the longest sequence:

x, x+1, x+2, x+3, ...

where these values already appear in the correct order in the array.

Example

Consider:

arr = [4, 3, 1, 2]

The positions of each value are:

Value    Position
  1         2
  2         3
  3         1
  4         0

Now check consecutive values.

For 1 and 2:

position[1] < position[2]

2 < 3

This is true.

So:

1, 2

can remain untouched.

Now check 2 and 3:

position[2] < position[3]

3 < 1

This is false.

So the longest sequence is:

1, 2

Length = 2.

There are 4 elements total.

Therefore:

Minimum moves = 4 - 2
              = 2

Why Do We Need a Position Array?

We need to quickly determine where each value occurs.

Create:

int[] pos = new int[n + 1];

For every element:

pos[arr[i]] = i;

For:

arr = [4, 3, 1, 2]

we get:

pos[1] = 2
pos[2] = 3
pos[3] = 1
pos[4] = 0

Now checking whether x comes before x + 1 is very easy:

pos[x] < pos[x + 1]

This takes O(1) time.

Java Code

class Solution {
    public int minMoves(int[] arr) {
        int n = arr.length;

        // Store the position of every value
        int[] pos = new int[n + 1];

        for (int i = 0; i < n; i++) {
            pos[arr[i]] = i;
        }

        int maxLen = 1;
        int currentLen = 1;

        // Find the longest consecutive sequence
        // that already appears in the correct order
        for (int value = 1; value < n; value++) {

            if (pos[value] < pos[value + 1]) {
                currentLen++;
            } else {
                currentLen = 1;
            }

            maxLen = Math.max(maxLen, currentLen);
        }

        // All other elements need to be moved
        return n - maxLen;
    }
}

Code Explanation

Step 1: Get the array size

int n = arr.length;

For example:

arr = [4, 3, 1, 2]

then:

n = 4

Step 2: Create the position array

int[] pos = new int[n + 1];

Why n + 1?

Because the values range from:

1 to n

We want to directly access:

pos[1]
pos[2]
...
pos[n]

Step 3: Store each value's position

for (int i = 0; i < n; i++) {
    pos[arr[i]] = i;
}

For:

arr = [4, 3, 1, 2]

the loop creates:

pos[4] = 0
pos[3] = 1
pos[1] = 2
pos[2] = 3

So:

pos = [unused, 2, 3, 1, 0]

Step 4: Find the Longest Valid Sequence

We start with:

int maxLen = 1;
int currentLen = 1;

currentLen represents the length of the current consecutive sequence.

maxLen stores the longest sequence found so far.

Step 5: Compare Consecutive Values

for (int value = 1; value < n; value++) {

We check:

1 with 2
2 with 3
3 with 4
...

The important condition is:

if (pos[value] < pos[value + 1])

This means:

Does value appear before value + 1 in the original array?

If yes, they can be part of the same sequence.

Example Walkthrough

Take:

arr = [2, 1, 3]

Positions:

pos[1] = 1
pos[2] = 0
pos[3] = 2

Check 1 and 2

pos[1] < pos[2]

1 < 0

False.

So:

currentLen = 1;

Check 2 and 3

pos[2] < pos[3]

0 < 2

True.

So:

currentLen++;

Now:

currentLen = 2

Therefore:

maxLen = 2

Finally:

return n - maxLen;

3 - 2 = 1

Answer:

Why `n - maxLen`?

Suppose:

n = 5

and the longest sequence we can keep is:

2, 3, 4

Length:

We can leave these three elements where they are.

The remaining:

1, 5

need to be moved.

Therefore:

5 - 3 = 2

moves are required.

Another Example

arr = [1, 2, 3, 5, 4]

Positions:

1 -> 0
2 -> 1
3 -> 2
4 -> 4
5 -> 3

Check:

1 → 2  ✅
2 → 3  ✅
3 → 4  ✅
4 → 5  ❌

So the longest sequence is:

1, 2, 3, 4

Length:

Therefore:

5 - 4 = 1

We move 5 to the end:

[1, 2, 3, 5, 4]
           ↓
[1, 2, 3, 4, 5]

Answer:

Important Intuition

Think of the problem this way:

Instead of asking:

Which elements should I move?

Ask:

Which elements can I leave untouched?

The elements left untouched must form a consecutive sequence in the sorted array.

So:

Find longest consecutive sequence
                ↓
     Leave those elements
                ↓
Move every other element
                ↓
       n - longest length

Complexity

Time Complexity

Building the position array:

O(n)

Finding the longest sequence:

O(n)

Total:

O(n)

Space Complexity

The pos[] array requires:

O(n)

Therefore:

Time  : O(n)
Space : O(n)

This satisfies the given constraints of:

n ≤ 100000

Final Takeaway

The core formula is:

Minimum Moves = n - Longest Consecutive Increasing Sequence

And the easiest way to find that sequence is to store the position of every value and check:

pos[value] < pos[value + 1]

If true, the consecutive sequence continues. Otherwise, we start a new sequence.

This converts what looks like a complicated array-movement problem into a simple position + longest consecutive sequence problem.

Problem Statement

Example

Key Observation

What Sequence Can Be Kept?

Example

Why Do We Need a Position Array?

Java Code

Code Explanation

Step 1: Get the array size

Step 2: Create the position array

Step 3: Store each value's position

Step 4: Find the Longest Valid Sequence

Step 5: Compare Consecutive Values

Example Walkthrough

Check 1 and 2

Check 2 and 3

Why n - maxLen?

Another Example

Important Intuition

Instead of asking:

Complexity

Time Complexity

Space Complexity

Final Takeaway

Why `n - maxLen`?