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:
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:
1
Why n - maxLen?
Suppose:
n = 5
and the longest sequence we can keep is:
2, 3, 4
Length:
3
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:
4
Therefore:
5 - 4 = 1
We move 5 to the end:
[1, 2, 3, 5, 4]
↓
[1, 2, 3, 4, 5]
Answer:
1
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.