2459. Sort Array by Moving Items to Empty Space

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.

class Solution {
    int helper(vector<int>& A, unordered_map<int,int>& mp) {
        int res = 0;
        vector<int> vis(A.size());
        for(int i = 0; i < A.size(); i++) {
            int now = mp[i];
            if(A[now] == i) vis[now] = true;
            if(vis[now]) continue;
            res += i ? 1 : -1;
            while(!vis[now]) {
                vis[now] = true;
                now = mp[A[now]];
                res += 1;
            }
        }
        return res;
    }
public:
    int sortArray(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> p,b;
        for(int i = 0; i < n; i++) {
            p[i] = i;
            b[i] = i - 1;
        }
        b[0] = n - 1;
        return min(helper(nums,p),helper(nums,b));
    }
};