You are viewing a single comment's thread. Return to all comments →
For those who don't accept the inversion solution, this one might be more intuitive.
string larrysArray(vector<int> A) { unordered_map<int, int> locs; for(int i = 0; i < A.size(); i++){ locs[A[i]] = i; } for(int i = 0; i < A.size(); i++){ if(A[i] == i+1){ continue; } // find next index and perform appropriate rotation int next_index = locs[i+1]; while(A[i] != i+1){ if(next_index - i >= 2){ // perform swaps swap(A[next_index-1], A[next_index-2]); swap(A[next_index-1], A[next_index]); // update locs locs[A[next_index]] = next_index; locs[A[next_index-1]] = next_index - 1; locs[A[next_index-2]] = next_index - 2; }else if(next_index+1 < A.size() & next_index-1 >= 0){ // perform swaps swap(A[next_index], A[next_index-1]); swap(A[next_index], A[next_index+1]); // update locs locs[A[next_index]] = next_index; locs[A[next_index-1]] = next_index - 1; locs[A[next_index+1]] = next_index + 1; }else{ return "NO"; } next_index = locs[i+1]; } } return "YES"; }
Seems like cookies are disabled on this browser, please enable them to open this website
Larry's Array
You are viewing a single comment's thread. Return to all comments →
For those who don't accept the inversion solution, this one might be more intuitive.