HackerRank Almost Sorted Problem Solution
In this post, we will solve HackerRank Almost Sorted Problem Solution.
Given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations one time.
- Swap two elements.
- Reverse one sub-segment.
Determine whether one, both or neither of the operations will complete the task. Output is as follows.
- If the array is already sorted, output yes on the first line. You do not need to output anything else.
- If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
- If elements can only be swapped, d[?] and d[r], output swap I r in the second line. and r are the indices of the elements to be swapped, assuming that the array is indexed from 1 to n.
- If elements can only be reversed, for the segment d[l…r], output reverse I r in the second line. I and r are the indices of the first and last elements of the subarray to be reversed, assuming that the array is indexed from 1 to n. Here d[l…r] represents the subarray that begins at index Ɩ and ends at index, both inclusive.
If an array can be sorted both ways, by using either swap or reverse, choose swap.
- If the array cannot be sorted either way, output no on the first line.
Example
arr = [2, 3, 5, 4]
Either swap the 4 and 5 at indices 3 and 4, or reverse them to sort the array. As mentioned above, swap is preferred over reverse. Choose swap. On the first line, print yes. On the second line, print swap 3 4.
Function Description
Complete the almostSorted function in the editor below.
almostSorted has the following parameter(s):
- int arr[n]: an array of integers
Prints
- Print the results as described and return nothing.
Input Format
The first line contains a single integer n, the size of arr.
The next line contains n space-separated integers arr[i] where 1 ≤ i ≤ n.
Output Format
- If the array is already sorted, output yes on the first line. You do not need to output anything else.
- If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
a. If elements can be swapped, d[l] and d[r], output swap Ir in the second line. I and r are the indices of the elements to be swapped, assuming that the array is indexed from
1 to n.
b. Otherwise, when reversing the segment d[l…r], output reverse I r in the second line. I and rare the indices of the first and last elements of the subsequence to be reversed, assuming that the array is indexed from 1 to n.
d[l…r] represents the sub-sequence of the array, beginning at index l and ending at index r, both inclusive.
If an array can be sorted by either swapping or reversing, choose swap. - If you cannot sort the array either way, output no on the first line.
Sample Input 1
STDIN Function ----- -------- 2 arr[] size n = 2 4 2 arr = [4, 2]
Sample Output 1
yes
swap 1 2
Explanation 1
You can either swap(1, 2) or reverse(1, 2). You prefer swap.
Sample Input 2
3
3 1 2
Sample Output 2
no
Explanation 2
It is impossible to sort by one single operation.
Sample Input 3
6
1 5 4 3 2 6
Sample Output 3
yes
reverse 2 5
Explanation 3
You can reverse the sub-array d[2…5] = “5 4 3 2”, then the array becomes sorted.
Almost Sorted C Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#undef DEBUG
typedef struct _unsorted_ar {
size_t size;
long *ar;
} unsorted_ar;
int main(int argc, char *argv[]) {
long n;
scanf("%ld", &n);
long *ar = (long *)malloc(sizeof(long) * n);
for (long i = 0; i < n; i++) {
scanf("%ld ", ar+i);
}
unsorted_ar *unsorted_ar_ar = NULL;
size_t unsorted_ar_ar_size = 0;
for (long i = 1; i < n; i++) {
if (unsorted_ar_ar_size > 2) {
printf("no\n");
goto end;
}
if (ar[i-1] > ar[i]) {
unsorted_ar *tmp_ar = (unsorted_ar *)malloc(sizeof(unsorted_ar));
tmp_ar->size = 0;
tmp_ar->ar = (long *)malloc(sizeof(long) * 2);
tmp_ar->ar[tmp_ar->size++] = i - 1;
tmp_ar->ar[tmp_ar->size++] = i;
for (; i < n - 1 ; i++) {
if (ar[i] > ar[i+1]) {
tmp_ar->ar = (long *)realloc(tmp_ar->ar,
sizeof(long) * (tmp_ar->size + 1));
tmp_ar->ar[tmp_ar->size++] = i+1;
} else if (ar[i] < ar[i+1]) {
break;
}
}
#ifdef DEBUG
for (long k = 0; k < tmp_ar->size; k++) {
printf("i[%ld] %ld ", i, tmp_ar->ar[k]);
}
printf("\n");
#endif
unsorted_ar_ar = (unsorted_ar *)realloc(unsorted_ar_ar,
sizeof(unsorted_ar) * (unsorted_ar_ar_size + 1));
memmove(&unsorted_ar_ar[unsorted_ar_ar_size++], tmp_ar, sizeof(unsorted_ar));
}
}
#ifdef DEBUG
for (long i = 0; i < unsorted_ar_ar_size; i++) {
unsorted_ar *tmp_ar = &unsorted_ar_ar[i];
printf("tmp_ar index [%ld, %zu] ", i, tmp_ar->size);
for (long j = 0; j < tmp_ar->size; j++) {
printf("%ld ", tmp_ar->ar[j]);
}
printf("\n");
}
#endif
if (unsorted_ar_ar == NULL) {
printf("yes\n");
} else {
if (unsorted_ar_ar_size == 1) {
unsorted_ar *tmp_ar = &unsorted_ar_ar[0];
if (tmp_ar->size == 2) {
for (long i = (tmp_ar->ar[1] + 1); i < n; i++) {
if (ar[tmp_ar->ar[0]] > ar[i]) {
printf("no\n");
goto end;
}
}
printf("yes\n");
printf("swap %ld %ld\n", tmp_ar->ar[0] + 1,
tmp_ar->ar[1] +1);
} else if (tmp_ar->size > 2) {
for (long i = (tmp_ar->ar[tmp_ar->size - 1] + 1); i < n; i++) {
#ifdef DEBUG
printf("ar[%ld] = %ld, ar[%ld] = %ld\n", tmp_ar->ar[0], ar[tmp_ar->ar[0]], i, ar[i]);
#endif
if (ar[tmp_ar->ar[0]] > ar[i]) {
printf("no\n");
goto end;
}
}
printf("yes\n");
printf("reverse %ld %ld\n", tmp_ar->ar[0] + 1,
tmp_ar->ar[tmp_ar->size - 1] +1);
} else {
printf("no\n");
}
} else if (unsorted_ar_ar_size == 2) {
unsorted_ar *tmp_ar1 = &unsorted_ar_ar[0];
unsorted_ar *tmp_ar2 = &unsorted_ar_ar[1];
if (tmp_ar1->size == 2 && tmp_ar2->size == 2) {
long idx2 = tmp_ar2->ar[1];
long idx1 = tmp_ar1->ar[0];
if (ar[idx1 - 1] < ar[idx2] &&
ar[idx2] < ar[idx1 + 1] &&
ar[idx2 - 1] < ar [idx1] &&
ar[idx1] < ar[idx2 + 1]) {
printf("yes\n");
printf("swap %ld %ld\n", idx1 + 1, idx2 + 1);
} else {
printf("no\n");
}
} else {
printf("no\n");
}
} else {
printf("no\n");
}
}
end:
return 0;
}Almost Sorted C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, s1 = -1, e1 = -1, s2 = -1, e2 = -1;
cin >> n;
if (n <= 1) {
cout << "yes";
return 0;
}
int a[n];
cin >> a[0];
for (int i = 1; i < n; i++) {
cin >> a[i];
// started neither
if (s1 == -1) {
if (a[i] < a[i - 1]) {
// start 1
s1 = i - 1;
}
}
// started 1
else if (s1 >= 0 && e1 == -1) {
if (a[i] > a[i - 1]) {
// end 1
e1 = i - 1;
}
}
// ended 1
else if (s2 == -1) {
if (a[i] < a[i - 1]) {
// start 2
s2 = i - 1;
}
}
// started 2
else if (s2 >= 0 && e2 == -1) {
if (a[i] > a[i - 1]) {
// end 2
e2 = i - 1;
}
}
// ended 2
else {
if (a[i] < a[i - 1]) {
cout << "no";
return 0;
}
}
}
if (s1 >= 0 && e1 == -1) {
e1 = n - 1;
}
else if (s2 >= 0 && e2 == -1) {
e2 = n - 1;
}
// already sorted
if (e1 == s1 && e2 == s2) {
cout << "yes";
return 0;
}
// swappable
else if (e1 - s1 <= 1 && s2 != -1 && e2 - s2 <= 1) {
if ((s1 == 0 || a[e2] >= a[s1 - 1]) &&
a[e2] < a[e1]) {
cout << "yes" << endl << "swap " << (s1 + 1) << " " << (e2 + 1);
return 0;
}
}
// swappable adjacent
else if (e1 - s1 <= 1 && s2 == -1) {
if ((s1 == 0 || a[e1] >= a[s1 - 1]) &&
(s2 == n - 1 || a[s1] <= a[e1 + 1])) {
cout << "yes" << endl << "swap " << (s1 + 1) << " " << (e1 + 1);
return 0;
}
}
// reversable
else if (e1 - s1 > 1 && s2 == -1 && e2 == -1) {
if ((s1 == 0 || a[e1] >= a[s1 - 1]) &&
(e1 == n - 1 || a[s1] <= a[e1 + 1])) {
cout << "yes" << endl << "reverse " << (s1 + 1) << " " << (e1 + 1);
return 0;
}
}
// unsortable
cout << "no";
return 0;
}Almost Sorted C Sharp Solution
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
Console.ReadLine();
int[] values=Console.ReadLine().Split(' ').Select(_p => Convert.ToInt32(_p)).ToArray();
bool reversing=false;
bool swapping=false;
int? firstElement=null,secondElement=null;
for(int i=1;i<values.Length;i++)
{
//Check that value is increasing
if(values[i]<values[i-1])
{
//Check if next value is still decreasing
if(!swapping && (reversing || (i+1<values.Length && values[i]>values[i+1])))
{
//Then we are in reversing mode
firstElement=firstElement??i-1;
if(secondElement==null || secondElement==i-1)
{
reversing=true;
secondElement=i;
continue;
}
else
{
Console.WriteLine("no");
return;
}
}
else if(!reversing)
{
//Try a swap
swapping=true;
//Ignore error if current value swapped
if(firstElement==i || secondElement==i)
{continue;}
if(firstElement==null && secondElement==null)
{
//Find a spot for me
//Either a bigger than the previous in previous elements
for(int j=0;j<i;j++)
{
//Console.WriteLine("prev "+values[j]+">"+values[i]+" => "+(values[j]>values[i]));
if(values[j]>values[i] && meetSwapCriteria(values,j,i))
{
firstElement=j;
secondElement=i;
break;
}
}
//Or a lower than the next element in next elements
if(firstElement==null && secondElement==null)
{
for(int j=i;j<values.Length;j++)
{
//Console.WriteLine("next "+values[j]+"<"+values[i]+" => "+(values[j]<values[i]));
if(values[j]<values[i] && meetSwapCriteria(values,i-1,j))
{
firstElement=i-1;
secondElement=j;
break;
}
}
}
if(firstElement==null && secondElement==null)
{
Console.WriteLine("no");
return;
}
//Make sure the value actually fits in that space, uses <= because it can actually compares with itself
else if(meetSwapCriteria(values,firstElement,secondElement))
{ }
else
{
Console.WriteLine("firstElement = "+firstElement+" [ "+values[firstElement.Value-1]+" "+values[firstElement.Value]+" "+values[firstElement.Value+1]+" ]");
Console.WriteLine("secondElement = "+secondElement+" [ "+values[secondElement.Value-1]+" "+values[secondElement.Value]+" "+values[secondElement.Value+1]+" ]");
//Console.WriteLine((firstElement.Value-1<=0 || values[firstElement.Value-1]<=values[secondElement.Value]));
//Console.WriteLine((firstElement.Value+1>=values.Length || values[secondElement.Value]<=values[firstElement.Value+1]));
//Console.WriteLine((secondElement.Value-1<=0 || values[secondElement.Value-1]<=values[firstElement.Value]));
//Console.WriteLine((secondElement.Value+1>=values.Length || values[firstElement.Value]<=values[secondElement.Value+1]));
Console.WriteLine("no");
return;
}
}
else
{
Console.WriteLine("no");
return;
}
}
else
{
//Console.WriteLine(values[i]+">"+values[i+1]);
Console.WriteLine("no");
return;
}
}
}
Console.WriteLine("yes");
if(firstElement!=null)
{
if(reversing && secondElement-firstElement>=2)
{Console.WriteLine("reverse "+(firstElement+1)+" "+(secondElement+1));}
else
{Console.WriteLine("swap "+(firstElement+1)+" "+(secondElement+1));}
}
}
private static bool meetSwapCriteria(int[] values,int? firstElement,int? secondElement)
{
return (firstElement.Value-1<=0 || values[firstElement.Value-1]<=values[secondElement.Value]) && (firstElement.Value+1>=values.Length || values[secondElement.Value]<=values[firstElement.Value+1]) &&
(secondElement.Value-1<=0 || values[secondElement.Value-1]<=values[firstElement.Value]) && (secondElement.Value+1>=values.Length || values[firstElement.Value]<=values[secondElement.Value+1]);
}
}Almost Sorted Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'almostSorted' function below.
*
* The function accepts INTEGER_ARRAY arr as parameter.
*/
public static void almostSorted(List<Integer> arr) {
if (!sortBySwitch(arr)) {
if (!sortByReverse(arr)) {
System.out.println("no");
}
}
}
private static boolean sortByReverse(List<Integer> arr) {
Integer reverseStart = null;
Integer reverseEnd = null;
for (int i = arr.size() - 2; i >= 0; i--) {
int nextNumber = arr.get(i + 1);
int currentNumber = arr.get(i);
if (reverseEnd == null && currentNumber > nextNumber) {
reverseEnd = i + 1;
} else if (reverseEnd != null && reverseStart == null) {
if (currentNumber < nextNumber) {
if (currentNumber <= arr.get(reverseEnd)) {
reverseStart = i + 1;
} else {
return false;
}
}
} else if (reverseEnd != null && reverseStart != null && currentNumber > nextNumber) {
return false;
}
}
if (reverseStart == null && reverseEnd == null) {
System.out.println("yes");
return true;
} else if (reverseStart != null && reverseEnd != null) {
System.out.println("yes");
System.out.println("reverse " + (reverseStart + 1) + " " + (reverseEnd + 1));
return true;
} else {
return false;
}
}
public static boolean sortBySwitch(List<Integer> arr) {
Integer firstSwitchNumberIndex = null;
Integer secondSwitchNumberIndex = null;
int countOfDescOrder = 0;
for (int i = arr.size() - 2; i >= 0; i--) {
int nextNumber = arr.get(i + 1);
int currentNumber = arr.get(i);
if (firstSwitchNumberIndex != null && secondSwitchNumberIndex != null
&& currentNumber > nextNumber) {
return false;
}
if (firstSwitchNumberIndex == null && currentNumber > nextNumber) {
firstSwitchNumberIndex = i + 1;
}
if (firstSwitchNumberIndex != null && secondSwitchNumberIndex == null) {
if (currentNumber > nextNumber) {
countOfDescOrder++;
if (countOfDescOrder > 2) {
return false;
}
}
if ((i==0 || arr.get(i-1) < currentNumber) // switch is really required since predecessor of current number is <
&& (i == 0 || arr.get(i - 1) <= arr.get(firstSwitchNumberIndex)) // new predecessor of first switch index needs to be <=
&& arr.get(firstSwitchNumberIndex) <= nextNumber // new successor of first switch index news to be >=
&& arr.get(firstSwitchNumberIndex - 1) <= currentNumber // new predecessor of second switch index needs to be <=
&& (firstSwitchNumberIndex == arr.size() - 1 || currentNumber <= arr.get(firstSwitchNumberIndex + 1))) { // new successor of second switch index needs to be >=
secondSwitchNumberIndex = i;
}
}
}
if (firstSwitchNumberIndex == null && secondSwitchNumberIndex == null) {
System.out.println("yes");
return true;
} else if (firstSwitchNumberIndex != null && secondSwitchNumberIndex != null) {
System.out.println("yes");
System.out.println(
"swap " + (secondSwitchNumberIndex + 1) + " " + (firstSwitchNumberIndex + 1));
return true;
} else {
return false;
}
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
Result.almostSorted(arr);
bufferedReader.close();
}
}Almost Sorted JavaScript Solution
function processData(input) {
var success = false;
var successType = '';
var firstPos = -1;
var secondPos = -1;
//Enter your code here
var inputArr = input.split('\n');
var arrLength = inputArr[0];
var arrNums = inputArr[1].split(' ');
//var arrNums = [1,2,4,3,5,6]
if (isArraySorted(arrNums)) {
success = true;
}
else {
var arrResult = [];
var reverseBlockRange = checkForReverseBlock(arrNums);
if (reverseBlockRange.length > 0) {
var reverseFrom = reverseBlockRange[0];
var reverseTo = reverseBlockRange[1] + 1;
var reverseBlock = arrNums.slice(reverseFrom, reverseTo);
if (reverseBlock.length != arrNums.length) {
arrResult = arrNums.slice(0, reverseFrom).concat(reverseBlock.reverse()).concat(arrNums.slice(reverseTo));
}
else {
arrResult = arrNums;
arrResult.reverse();
}
if (isArraySorted(arrResult)) {
success = true;
successType = (reverseBlock.length === 2 ? 'swap' : 'reverse');
firstPos = reverseFrom+1;
secondPos = reverseTo;
}
var swapPositions = checkForSwapPositions(arrNums);
if (swapPositions.length == 2) {
var firstPosVal = arrNums[swapPositions[0]];
var secondPosVal = arrNums[swapPositions[1]];
arrNums[swapPositions[0]] = secondPosVal;
arrNums[swapPositions[1]] = firstPosVal;
success = true;
successType = 'swap';
firstPos = swapPositions[0]+1;
secondPos = swapPositions[1]+1;
}
}
}
console.log(success ? 'yes' : 'no');
if (success) {
console.log(successType + ' ' + firstPos + ' ' + secondPos);
}
}
function checkForSwapPositions(arr) {
var count = 0;
var swapFirst = -1;
var swapSecond = -1;
while (arr.length > 1 && count < arr.length-1) {
if (parseInt(arr[count]) > parseInt(arr[count+1])) {
if (swapFirst == -1) {
swapFirst = count;
}
else if (swapFirst != -1 && swapSecond == -1) {
swapSecond = count+1;
}
else if (swapFirst != -1 && swapSecond != -1){
return [];
}
}
count++;
}
if (swapFirst != -1 && swapSecond != -1) {
return [swapFirst, swapSecond];
}
else {
return [];
}
}
function checkForReverseBlock(arr) {
var count = 0;
var reverseFrom = -1;
var reverseTo = -1;
while (arr.length > 1 && count < arr.length-1) {
if (parseInt(arr[count]) > parseInt(arr[count+1])) {
reverseFrom = count;
break;
}
count++;
}
count = arr.length-1;
while (arr.length > 1 && count >= 0) {
if (parseInt(arr[count]) < parseInt(arr[count-1])) {
reverseTo = count;
break;
}
count--;
}
if (reverseFrom >= 0 && reverseTo >= 0 && reverseFrom != reverseTo) {
return [reverseFrom, reverseTo];
}
return [];
}
function isArraySorted(arr) {
for (var count = 0; count < arr.length; count++) {
if (count < (arr.length-1) && parseInt(arr[count]) > parseInt(arr[count+1])) return false;
}
return true;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Almost Sorted Python Solution
n=int(input())
li=input().split()
a=[]
li[0]=int(li[0])
l,r,swap,rev=-1,-1,True,True
for i in range(1,n):
li[i]=int(li[i])
if(li[i]<li[i-1]):
a.append(i)
else:
a.append(0)
if(a.count(0)>=len(a)-2):
if(a.count(0)==len(a)-1)and (len(li)==2):
print("yes")
print("swap",max(a),max(a)+1)
elif(a.count(0)==len(a)-1)and (len(li)>2):
if(max(a)>1):
if(li[max(a)]>li[max(a)-2])and (li[max(a)-1]<=li[max(a)+1]):
print("yes")
print("swap",max(a),max(a)+1)
else:
print("no")
if (max(a)==1):
if(li[max(a)-1]<=li[max(a)+1]):
print("yes")
print("swap",max(a),max(a)+1)
else:
print("no")
elif(a.count(0)==len(a)-2):
print("yes")
temp=[]
temp.append(max(a))
a.remove(max(a))
temp.append(max(a))
print("swap",min(temp),max(temp)+1)
else:
print("no")
else:
#print(a,a.index(max(a)),len(a),a.count(0))
temp1=a.index(max(a))-(len(a)-a.count(0))
temp2=a.index(max(a))
for i in range(temp1,temp2):
#print(i)
if(a[i+1]==0):
rev=False
if(rev==True):
print("yes")
print("reverse",temp1+2,temp2+2)
else:
print("no")Other Solutions
An impressive share! I have just forwarded this onto a co-worker who has been doing a little homework on this. And he in fact ordered me dinner because I found it for him… lol. So allow me to reword this…. Thanks for the meal!! But yeah, thanks for spending some time to talk about this subject here on your web page.