Sort 309 Discussions, By:

2 months ago+ 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";
}

2 months ago+ 0 comments

Tried a different algo, got time limit exceeded. Then realised its just a simple swap count and solved it. Nice question!

2 months ago+ 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");
}

2 months ago+ 1 comment

Larry's Array hackerrank solution with explanation

https://www.javaspot.in/2023/01/larrys-array-hackerrank-solution.html

3 months ago+ 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

for the recursive helper

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
1. 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