We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Implementation
- Larry's Array
- Discussions
Larry's Array
Larry's Array
+ 0 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"; }
+ 0 comments Tried a different algo, got time limit exceeded. Then realised its just a simple swap count and solved it. Nice question!
+ 0 comments simple C++ code:
string larrysArray(vector<int> A) { int rev_count = 0; for (size_t i = 0; i < A.size() - 1; i++) { for (size_t j = i + 1; j < A.size(); j++) { if (A[i] > A[j]) { rev_count += 1; } } } return rev_count % 2 == 0 ? std::string("YES") : std::string("NO"); }
+ 1 comment Larry's Array hackerrank solution with explanation
https://www.javaspot.in/2023/01/larrys-array-hackerrank-solution.html
+ 0 comments Here is the Javascript solution
pseudo code
- define a helper for detecting if an array is sorted
- define another helper to recursively go through the array using the sliding window technique
- check if the array is sorted, and if so return true (base case)
- using the sliding window technique, slide through the array three elements at a time
- if the minimum of these elements is not in the right spot and can be put in the right place by using the options given, then do so and move on to the next slide
- if we reach the last three elements and the slice or segement from the beginning up to that ponint is not not sorted and the minimum of the three elements is not in the right place return false (base case)
- after reaching the end of the array, call recursively the original array that has been modified
if the recursive call returns true, then we return true
- Using the recursive helper and a simple ternary operator returns the desired results
Actual code
function larrysArray(A) { return `${recursive(A) ? 'YES' : 'NO'}`; } const recursive = (arr) => { if (isSorted(arr)) return true; for (let i = 0; i < arr.length - 2; i++) { let a = arr[i], b = arr[i + 1], c = arr[i + 2]; let smallestInRightPlace = a < b && a < c; const segmentSorted = a < b && b < c; const firstSlice = arr.slice(0, i); if ( smallestInRightPlace && i === arr.length - 3 && !segmentSorted && isSorted(firstSlice) ) { return false; } if (b < a && b < c) { // bca arr[i] = b; arr[i + 1] = c; arr[i + 2] = a; } if (c < a && c < b) { // cab arr[i] = c; arr[i + 1] = a; arr[i + 2] = b; } } if (recursive(arr)) { return true; } }; // checks if an array is sorted const isSorted = (arr) => { for (let i = 0; i < arr.length - 1; i++) { if (arr[i + 1]) { if (arr[i + 1] < arr[i]) return false; } } return true; };
Load more conversations
Sort 309 Discussions, By:
Please Login in order to post a comment