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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Larry's Array
  5. Discussions

Larry's Array

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 309 Discussions, By:

recency

Please Login in order to post a comment

  • zaplatarivan
    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";
    }
    
    0|
    Permalink
  • Astroflexx
    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!

    0|
    Permalink
  • tangjch15
    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");
    }
    
    0|
    Permalink
  • himanshu81199
    2 months ago+ 1 comment

    Larry's Array hackerrank solution with explanation

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

    1|
    Permalink
  • kibirigejohn005
    3 months ago+ 0 comments

    Here is the Javascript solution

    pseudo code

    1. define a helper for detecting if an array is sorted
    2. 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;
    };
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy