• + 0 comments

    Solution O(N^3) in C++ with sorting, cause I think it's the purpose of these challenges.

    int rotate(vector<int>& A, int pos) {
        int validPos = std::min(std::max(1, pos), (int)A.size() - 2);
        int tmp = A[validPos - 1];
        A[validPos - 1] = A[validPos];
        A[validPos] = A[validPos + 1];
        A[validPos + 1] = tmp;
        return pos - 1;
    }
    
     void move(vector<int>& A, int currPos, int dstPos) {
         while (currPos != dstPos) {
             currPos = rotate(A, currPos);
         }
     }
    
    string larrysArray(vector<int> A) {
        int base = 1;
        int N = A.size();
        for (int i = 0; i < N - 2; i++) {
            for (int j = i; j < N; j++) {
                if (A[j] == base) {
                    move(A, j, i);
                    break;
                }
            }
            base++;
        }
        if (A[N - 3] <= A[N - 2] && A[N - 2] <= A[N - 1]) {
            return "YES";
        }
        return "NO";
    }