Given an array with n distinct elements. An array is said to be almost sorted (non-decreasing) if any of its elements can occur at a maximum of 1 distance away from their original places in the sorted array. We need to find whether the given array is almost sorted or not.
Examples:
Input : arr[] = {1, 3, 2, 4}
Output : Yes
Explanation : All elements are either
at original place or at most a unit away.
Input : arr[] = {1, 4, 2, 3}
Output : No
Explanation : 4 is 2 unit away from
its original place.
Sorting Approach : With the help of sorting we can predict whether our given array is almost sorted or not. The idea behind that is first sort the input array say A[]and then if array will be almost sorted then each element Ai of the given array must be equal to any of Bi-1, Bi or Bi+1 of sorted array B[].
Time Complexity : O(nlogn)
// suppose B[] is copy of A[]
sort(B, B+n);
// check first element
if ((A[0]!=B[0]) && (A[0]!=B[1]) )
return 0;
// iterate over array
for(int i=1; i<n-1; i++)
{
if (A[i]!=B[i-1]) && (A[i]!=B[i]) && (A[i]!=B[i+1]) )
return false;
}
// check for last element
if ((A[i]!=B[i-1]) && (A[i]!=B[i]) )
return 0;
// finally return true
return true;
Algorithm:
- Sort the copy of input array A to get the sorted array B.
- Check if the first element of A is either the first or second element of B. If not, return false
- Iterate through the array A from the second element to the second-to-last element
- For each element A[i] of A, check if it is equal to A[i-1], A[i], or A[i+1] in B. If not, return false
- Check if the last element of A is either the second-to-last or last element of B. If not, return false
- If all checks pass, return true.
Below is the implementation of the approach:
C++
// CPP program to find whether given array// almost sorted or not#include <bits/stdc++.h>using namespace std;// function for checking almost sortbool isAlmostSorted(int A[], int n) { // Make a copy of A int B[n]; for (int i = 0; i < n; i++) { B[i] = A[i]; } // Sort the copy sort(B, B+n); // Check the first element if ((A[0] != B[0]) && (A[0] != B[1])) { return false; } // Iterate over the array for (int i = 1; i < n-1; i++) { if ((A[i] != B[i-1]) && (A[i] != B[i]) && (A[i] != B[i+1])) { return false; } } // Check the last element if ((A[n-1] != B[n-1]) && (A[n-1] != B[n-2])) { return false; } // Return true if the array is almost sorted return true;}int main() { // Input array int A[] = { 1, 3, 2, 4, 6, 5 }; int n = sizeof(A)/sizeof(A[0]); if (isAlmostSorted(A, n)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Javascript
// function for checking almost sortfunction isAlmostSorted(A, n) { // Make a copy of A let B = [...A]; // Sort the copy B.sort((a, b) => a - b); // Check the first element if ((A[0] != B[0]) && (A[0] != B[1])) { return false; } // Iterate over the array for (let i = 1; i < n-1; i++) { if ((A[i] != B[i-1]) && (A[i] != B[i]) && (A[i] != B[i+1])) { return false; } } // Check the last element if ((A[n-1] != B[n-1]) && (A[n-1] != B[n-2])) { return false; } // Return true if the array is almost sorted return true;}// Input arraylet A = [1, 3, 2, 4, 6, 5];let n = A.length;if (isAlmostSorted(A, n)) { console.log("Yes");} else { console.log("No");} |
Output
Yes
Time complexity: O(n Log n)
Auxiliary Space: O(n) as an array B has been created to store copy of input array A. Here, n is size of the input array.
Efficient Approach: The idea is based on Bubble Sort. Like Bubble Sort, we compare adjacent elements and swap them if they are not in order. Here after swapping we move the index one position extra so that bubbling is limited to one place. So after one iteration if the resultant array is sorted then we can say that our input array was almost sorted otherwise not almost sorted.
// perform bubble sort tech once
for (int i=0; i<n-1; i++)
if (A[i+1]<A[i])
swap(A[i], A[i+1]);
i++;
// check whether resultant is sorted or not
for (int i=0; i<n-1; i++)
if (A[i+1]<A[i])
return false;
// If resultant is sorted return true
return true;
C++
// CPP program to find whether given array// almost sorted or not#include <bits/stdc++.h>using namespace std;// function for checking almost sortbool almostSort(int A[], int n){ // One by one compare adjacents. for (int i = 0; i < n - 1; i++) { if (A[i] > A[i + 1]) { swap(A[i], A[i + 1]); i++; } } // check whether resultant is sorted or not for (int i = 0; i < n - 1; i++) if (A[i] > A[i + 1]) return false; // is resultant is sorted return true return true;}// driver functionint main(){ int A[] = { 1, 3, 2, 4, 6, 5 }; int n = sizeof(A) / sizeof(A[0]); if (almostSort(A, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// JAVA Code to check if given array is almost// sorted or notimport java.util.*;class GFG { // function for checking almost sort public static boolean almostSort(int A[], int n) { // One by one compare adjacents. for (int i = 0; i < n - 1; i++) { if (A[i] > A[i + 1]) { int temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; i++; } } // check whether resultant is sorted or not for (int i = 0; i < n - 1; i++) if (A[i] > A[i + 1]) return false; // is resultant is sorted return true return true; } /* Driver program to test above function */ public static void main(String[] args) { int A[] = { 1, 3, 2, 4, 6, 5 }; int n = A.length; if (almostSort(A, n)) System.out.print("Yes"); else System.out.print("No"); }} // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find whether given # array almost sorted or not # Function for checking almost sort def almostSort(A, n): # One by one compare adjacents. i = 0 while i < n - 1: if A[i] > A[i + 1]: A[i], A[i + 1] = A[i + 1], A[i] i += 1 i += 1 # check whether resultant is sorted or not for i in range(0, n - 1): if A[i] > A[i + 1]: return False # Is resultant is sorted return true return True# Driver Codeif __name__ == "__main__": A = [1, 3, 2, 4, 6, 5] n = len(A) if almostSort(A, n): print("Yes") else: print("No") # This code is contributed# by Rituraj Jain |
C#
// C# Code to check if given array// is almost sorted or notusing System;class GFG { // function for checking almost sort public static bool almostSort(int []A, int n) { // One by one compare adjacents. for (int i = 0; i < n - 1; i++) { if (A[i] > A[i + 1]) { int temp = A[i]; A[i] = A[i + 1]; A[i + 1] = temp; i++; } } // Check whether resultant is // sorted or not for (int i = 0; i < n - 1; i++) if (A[i] > A[i + 1]) return false; // is resultant is sorted return true return true; } // Driver Code public static void Main() { int []A = {1, 3, 2, 4, 6, 5}; int n = A.Length; if (almostSort(A, n)) Console.Write("Yes"); else Console.Write("No"); }} // This code is contributed by Nitin Mittal. |
PHP
<?php// PHP program to find // whether given array// almost sorted or not// function for checking// almost sortfunction almostSort($A, $n){ // One by one compare adjacents. for ($i = 0; $i < $n - 1; $i++) { if ($A[$i] > $A[$i + 1]) { list($A[$i], $A[$i + 1]) = array($A[$i + 1], $A[$i] ); $i++; } } // check whether resultant // is sorted or not for ($i = 0; $i <$n - 1; $i++) if ($A[$i] > $A[$i + 1]) return false; // is resultant is // sorted return true return true;}// Driver Code$A = array (1, 3, 2, 4, 6, 5);$n = sizeof($A) ;if (almostSort($A, $n)) echo "Yes", "\n";else echo "Yes", "\n"; // This code is contributed by ajit?> |
Javascript
<script> // Javascript Code to check if given array // is almost sorted or not // function for checking almost sort function almostSort(A, n) { // One by one compare adjacents. for (let i = 0; i < n - 1; i++) { if (A[i] > A[i + 1]) { let temp = A[i]; A[i] = A[i + 1]; A[i + 1] = temp; i++; } } // Check whether resultant is // sorted or not for (let i = 0; i < n - 1; i++) if (A[i] > A[i + 1]) return false; // is resultant is sorted return true return true; } let A = [1, 3, 2, 4, 6, 5]; let n = A.length; if (almostSort(A, n)) document.write("Yes"); else document.write("No"); </script> |
Output:
Yes
Time Complexity: O(N), as we are using any loops for traversing.
Auxiliary Space: O(1), as we are not using any extra space.
This article is contributed by Shivam Pradhan (anuj_charm). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
