Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerRank Almost Sorted problem solution

YASH PAL, 31 July 2024

In this HackerRank Almost Sorted problem, you have Given an array of integers, determine whether the array can be sorted in ascending order using either swap two elements or reverse one sub-segment.

HackerRank Almost Sorted problem solution

Problem solution in Python programming.

def getJumps(ar):
    jumps = []
    for i in range(len(ar)-1):
        if ar[i] > ar[i+1]:
            jumps.append(i)
    return jumps

def isSortedWithSwap(ar, i, j):
    ar[i], ar[j] = ar[j], ar[i]
    jumps = getJumps(ar)
    ar[i], ar[j] = ar[j], ar[i] # repair list
    return len(jumps) == 0

def isSortedWithReverse(ar, i, j):
    ar[i:j] = ar[j-1:i+1:-1]
    jumps = getJumps(ar)
    ar[i:j] = ar[j-1:i+1:-1] # repair list
    return len(jumps) == 0

def magic(ar):
    jumps = getJumps(ar)
    if len(jumps) == 0:
        print('yes')
    elif len(jumps) == 1:
        i = jumps[0]
        j = i+1
        while j+1 < len(ar) and ar[i+1] == ar[j+1]: #move point to last same element
            j+=1
        if isSortedWithSwap(ar, i, j):
            print('yes')
            print('swap', i+1, j+1)
        else:
            print('no')
    elif len(jumps) == 2:
        i = jumps[0]
        j = jumps[1] + 1
        if isSortedWithSwap(ar, i, j):
            print('yes')
            print('swap', i+1, j+1)
        else:
            print('no')
    else:
        i = jumps[0]
        j = jumps[-1] + 2
        if isSortedWithReverse(ar,i,j):
            print('yes')
            print('reverse', i+1, j)
        else:
            print('no')

n = int(input())
ar = list(map(int, input().split()))
magic(ar)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        Scanner sc = new Scanner(System.in);
        int start = -1;int count = 0;int end = -1;
        int prev_i = -1;
        int size = sc.nextInt();
        int arr[] = new int [size];
        int i;
         for(int j = 0;j<size;j++){
            arr[j] = sc.nextInt();
         }
        if(findSwap(arr)==-1){
            findReverse(arr);
        }
    }
    
   static int findReverse(int [] arr){
      int start =-1;int end = -1;
       for(int i = 0;i<arr.length-1;i++){
          if(arr[i]>arr[i+1]){
               if(start==-1){
                      start = i;
                  }
                  else{
                      System.out.println("no");
                      return -1;
                  }
              while(arr[i]>arr[i+1]){                 
                  end = i+1;
                  i++;                  
              }
              if((start==0||arr[start-1]<arr[end])&&(end==arr.length-1||arr[start]<arr[end+1])){                
                      continue;
                  }
               else{
                   System.out.println("no");
                   return -1;
               }
              }
          }
        System.out.println("yes");
        System.out.println("reverse "+(start+1)+" "+(end+1));
       
       return 1;
      }
   
    
   static int findSwap(int [] arr){
        int count =0;int start = -1;int end =-1;
        for(int i = 0;i<arr.length-1;i++){
         
                   if(arr[i]>arr[i+1]){
                       count++;
                       if(count==1){
                           start = i;
                           end = i+1;
                       }
                       else{
                         if(count==2){
                             end=i+1;
                         }else{
                            return -1;
                         }
                       }
                   }                        
        }
       if((end!=arr.length-1)&&(arr[start]<arr[end+1]))
         {  
          System.out.println("yes");
          System.out.println("swap "+(start+1)+" "+(end+1));       
          return 1;
         }
       else{
           if((end==arr.length-1)&&(start==(end-1))){
                System.out.println("yes");
                System.out.println("swap "+(start+1)+" "+(end+1));       
                return 1;
           }
       }
        return -1;
    }
}


Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    vector<int> B(A);
    sort(B.begin(), B.end());
    int start = -1, end = -1;
    int count = 0;
    for (int  i = 0; i < n; i++) {
        if (A[i] != B[i]) {
            count++;
            if (start == -1) {
                start = i;
            }
            end = i;            
        }
    }
    if (count == 2) {
        cout << "yes"<<endl;
        cout << "swap ";
        cout << start + 1<<" "<<end + 1<<endl;
        return 0;
    }
  
    for (int i = 0; i < count / 2; i++) {
        if (A[end - i] != B[start + i]) {
            cout << "no" <<endl;
            return 0;
        }
        
    }
    cout << "yes"<<endl;
    cout << "reverse "<<start + 1<<" "<<end + 1<<endl;
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int *a, ar;
    int pos1 = -1, pos2 = -1, reverse = 0, swap = 0;
    int reverse_possible = 1;
    
    // get size of array and add elements to array
    scanf("%d", &ar);
    a = (int*)malloc(sizeof(int) * ar);
    for (int i = 0; i < ar; i++) {
        scanf("%d", a + i);
    }
    
    // work goes here
    for (int i = 0; i < ar; i++) {
        // we note that all numbers in the array are distinct
        if (i < ar - 1) {
            if (a[i] > a[i + 1]) {
            	if (swap || reverse) {
            		swap = reverse = 0;
            		break;
            	}
            	
                if (pos1 == -1) {
                    pos1 = i;
                    pos2 = i;
                } else if (reverse_possible && !reverse) {
                    pos2++;
                }
            } else if (pos2 != -1 && !swap && !reverse) {
                // potentially a reverse operation
                if (pos2 - pos1 >= 2) {
                    reverse = 1;
                    continue;
                // continue finding reverse
                } else {
                    pos2 = -1;
                    reverse_possible = 0;
                }
            }
        }
        
        // note that a[pos1] >= a[i]
        if (pos1 != -1 && a[pos1] > a[i] &&  
            ((i+1<ar && a[pos1] <= a[i+1]) || i+1>=ar) &&
            ((i-1>=0 && a[i-1] <= a[pos1]) || i-1<0) &&
            ((pos1+1<ar && a[i] <= a[pos1+1]) || pos1+1>=ar) &&
            ((pos1-1>=0 && a[pos1-1] <= a[i]) || pos1-1<0)) {
            if (swap || reverse) {
                swap = 0;
                reverse = 0; 
                break;
            }
            
            pos2 = i;
            swap = 1;
        }
    }
    
    //printf("%d %dn", swap, reverse);
    
    if (reverse) {
        printf("yesn");
        printf("reverse %d %d", pos1 + 1, pos2 + 2);
    } else if (swap) {
        printf("yesn");
        printf("swap %d %d", pos1 + 1, pos2 + 1);
    } else {
        printf("non");
    }
    
    return 0;
}


Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split("n");
    lines.shift();
    var array = lines[0].split(" ").map(function (v) {
        return parseInt(v);
    });
    solve(array);
}

function countDownMarks(array) {
    var downMarks = [];

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i + 1] < array[i]) {
            downMarks.push(i);
        }
    }

    return downMarks;
}

function solve(array) {
    var downMarks = countDownMarks(array);
    var newArray, newDownMarks, start, end;

    // try swap
    if (downMarks.length == 1 ||
        downMarks.length == 2) {

        newArray = array.slice(0);

        start = downMarks.shift();
        end = (downMarks.length) ? downMarks.shift() + 1 : start + 1;

        swap(newArray, start, end);
        newDownMarks = countDownMarks(newArray);
        if (!newDownMarks.length) {
            outputResult("yes");
            output("swap", start + 1, end + 1);
            return;
        }
    }

    // try reverse
    if (downMarks.length > 2 &&
        downMarks.length == downMarks[downMarks.length - 1] - downMarks[0] + 1) {

        start = downMarks.shift();
        end = downMarks.pop() + 1;
        newArray = reverse(array, start, end);
        newDownMarks = countDownMarks(newArray);
        if (!newDownMarks.length) {
            outputResult("yes");
            output("reverse", start + 1, end + 1);
            return;
        }
    }

    outputResult("no");
}

function swap(array, idx1, idx2) {
    var tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;
}

function reverse(array, idx1, idx2) {
    return array.slice(0, idx1).concat(array.slice(idx1, idx2 + 1).reverse()).concat(array.slice(idx2 + 1));
}

function output(op, start, end) {
    process.stdout.write([op, start, end].join(" "));
}

function outputResult(str) {
    process.stdout.write(str+"n");
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Algorithms coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes