Sort Array by Moving Items to Empty Space

Sort Array by Moving Items to Empty Space - Problem

You are given an integer array nums of size n containing each element from 0 to n - 1 (inclusive). Each of the elements from 1 to n - 1 represents an item, and the element 0 represents an empty space.

In one operation, you can move any item to the empty space.

nums is considered to be sorted if the numbers of all the items are in ascending order and the empty space is either at the beginning or at the end of the array.

For example, if n = 4, nums is sorted if:

nums = [0,1,2,3] or nums = [1,2,3,0]

...and considered to be unsorted otherwise.

Return the minimum number of operations needed to sort nums.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,0]

› Output: 2

💡 Note: Target [1,2,3,0]: positions 2 and 3 are correct (3 and 0). So 4-2=2 moves needed.

Example 2 — Already Sorted

$ Input: nums = [0,1,2,3]

› Output: 0

💡 Note: Array is already in sorted form [0,1,2,3], so no moves needed.

Example 3 — Alternative Sort

$ Input: nums = [1,2,3,0]

› Output: 0

💡 Note: Array is already in alternative sorted form [1,2,3,0], so no moves needed.

Constraints

2 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] < nums.length
All the values of nums are unique.

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements 0 to n-1, where 0 is empty space

Two Targets

Check both [0,1,2,3...] and [1,2,3...0] configurations

Minimum Moves

Choose target requiring fewer operations

Key Takeaway

🎯 Key Insight: There are exactly two valid sorted states - count elements already correct in each and minimize moves

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is recognizing there are exactly two valid sorted configurations: [0,1,2,3,...] or [1,2,3,...,0]. Count elements already in correct positions for both targets and choose the configuration requiring fewer moves. Best approach uses greedy counting in O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force BFS	O(n! × n)	O(n! × n)	Try all possible move sequences using breadth-first search
Greedy Cycle Detection	O(n)	O(1)	Count items in wrong positions and handle cycles optimally

Brute Force BFS — Algorithm Steps

Start with initial array state
Generate all possible moves (swap any item with 0)
Use BFS to find minimum moves to reach sorted state

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with given array configuration

Generate Moves

Try swapping 0 with each other element

BFS Search

Use queue to find minimum moves to sorted state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 100000

typedef struct {
    int arr[10];
    int moves;
    int n;
} State;

int arraysEqual(int* a, int* b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) return 0;
    }
    return 1;
}

int solution(int* nums, int n) {
    int target1[10], target2[10];
    
    for (int i = 0; i < n; i++) {
        target1[i] = i;
        target2[i] = (i == n-1) ? 0 : i+1;
    }
    
    if (arraysEqual(nums, target1, n) || arraysEqual(nums, target2, n)) {
        return 0;
    }
    
    State queue[MAX_STATES];
    int visited[MAX_STATES][10];
    int visitedCount = 0;
    int front = 0, rear = 1;
    
    for (int i = 0; i < n; i++) {
        queue[0].arr[i] = nums[i];
        visited[0][i] = nums[i];
    }
    queue[0].moves = 0;
    queue[0].n = n;
    visitedCount = 1;
    
    while (front < rear && rear < MAX_STATES) {
        State current = queue[front++];
        
        int zeroPos = -1;
        for (int i = 0; i < n; i++) {
            if (current.arr[i] == 0) {
                zeroPos = i;
                break;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i != zeroPos) {
                int newArr[10];
                for (int j = 0; j < n; j++) {
                    newArr[j] = current.arr[j];
                }
                
                int temp = newArr[i];
                newArr[i] = newArr[zeroPos];
                newArr[zeroPos] = temp;
                
                if (arraysEqual(newArr, target1, n) || arraysEqual(newArr, target2, n)) {
                    return current.moves + 1;
                }
                
                int isVisited = 0;
                for (int v = 0; v < visitedCount; v++) {
                    if (arraysEqual(newArr, visited[v], n)) {
                        isVisited = 1;
                        break;
                    }
                }
                
                if (!isVisited && rear < MAX_STATES && visitedCount < MAX_STATES) {
                    for (int j = 0; j < n; j++) {
                        queue[rear].arr[j] = newArr[j];
                        visited[visitedCount][j] = newArr[j];
                    }
                    queue[rear].moves = current.moves + 1;
                    queue[rear].n = n;
                    rear++;
                    visitedCount++;
                }
            }
        }
    }
    
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10];
    int n = 0;
    char* token = strtok(line, "[,]\n");
    while (token != NULL && n < 10) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! possible permutations, each requiring O(n) time to process

⚠ Quadratic Growth

Space Complexity

O(n! × n)

Queue stores up to n! states, each state is array of size n

⚠ Quadratic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler