Lily’s Homework

• Time : O(nlogn)
• Space : O(n)

int forward(vector<int> A) {
    int res = 0, n = A.size();
    auto s = A;
    sort(begin(s), end(s));
    unordered_map<int, int> mp;
    for(int i = 0; i < n; i++) mp[A[i]] = i;

    for(int i = 0; i < n; i++) {
        if(s[i] == A[i]) continue;
        int idx = mp[s[i]];
        mp[A[i]] = idx;
        swap(A[i], A[idx]);
        res++;
    }
    return res;
}

int backword(vector<int> A) {
    int res = 0, n = A.size();
    auto s = A;
    sort(rbegin(s), rend(s));
    unordered_map<int, int> mp;
    for(int i = 0; i < n; i++) mp[A[i]] = i;

    for(int i = 0; i < n; i++) {
        if(s[i] == A[i]) continue;
        int idx = mp[s[i]];
        mp[A[i]] = idx;
        swap(A[i], A[idx]);
        res++;
    }
    return res;
}

int lilysHomework(vector<int> arr) {
    return min(forward(arr), backword(arr));
}