Circularly sorted arrays are arrays that are sorted in ascending or descending order and then rotated by a number of steps.
Let us take an example to know more about circularly sorted arrays:
Consider an array: arr[] = {23, 34, 45, 12, 17, 19}
The elements here, {12, 17, 19, 23, 34, 45} are sorted ‘In-order’ but they are rotated to the left by 3 times.
Ascending circularly sorted array:
- Consider an array sorted in ascending order: arr[] = {12, 17, 19, 23, 34, 45}
- If the above array is rotated by 3 steps to the left, then the resultant array will be ascending circularly sorted array: {23, 34, 45, 12, 17, 19}
Descending circularly sorted array:
- Consider an array sorted in descending order: arr[] = {35, 26, 11, 9, 5, 3}
- If the above array is rotated by 3 steps to the left, then the resultant array will be descending circularly sorted array: {9, 5, 3, 35, 26, 11}
Let us check through the below problem whether the given array is circularly sorted or not:
Problem Statement:
Given an array arr[] of length N, the task is to check whether the given array is circularly sorted or not, we need to check whether the given array is the rotated form of the sorted array.
- In ascending circularly sorted array, there will be at most one case where the element just before the current element will be greater than the current element i.e., arr[ i – 1 ] > arr[ i ]. If there is no such case, then we consider the array as circularly sorted, this is the result of a rotation by N steps. On the other hand, if there is only one such case; we then make sure that the first element of the array is greater than the last one i.e., arr[0] > arr[N-1].
- So we need to count the total existence of arr[ i – 1 ] > arr[ i ] cases and if the count is 1 with arr[ 0 ] < arr[ N-1 ] or if the count is greater than 1 then the result will be false else the result will be true meaning that the array is circularly sorted.
Below is the implementation for the above approach:
C++
// CPP program to check whether// the array is circularly sorted#include <bits/stdc++.h>using namespace std;// Function to check whether// array is circularly sortedbool checkCircularSorted(int arr[], int n){ // cnt variable will store count of // arr[i-1] > arr[i] int cnt = 0; for (int i = 1; i < n; i++) { // increase cnt if arr[i-1] > arr[i] if (arr[i - 1] > arr[i]) { cnt++; } } // if cnt > 1 then false // else true if (cnt == 1) { // check first and last element. return arr[0] > arr[n-1]; } else { return false; }}// Driver codeint main(){ // Given array int arr[] = { 23, 34, 45, 12, 17, 19 }; // size of array int N = sizeof(arr) / sizeof(arr[0]); // Calling function to check // cirularly sorted array bool result = checkCircularSorted(arr, N); // Print result if (result) { cout << "Array is circularly sorted"; } else { cout << "Array is not circularly sorted"; }} |
Java
// Java program to check whether// the array is circularly sortedpublic class Main { // Method to check whether // array is circularly sorted public static boolean checkCircularSorted(int arr[]) { // cnt variable will store // count of arr[i-1] > arr[i] int cnt = 0; for (int i = 1; i < arr.length; i++) { // increase cnt if arr[i-1] > arr[i] if (arr[i - 1] > arr[i]) { cnt++; } } // if cnt > 1 then false // else true if (cnt == 1) { // check first and last element. return arr[0] > arr[arr.length-1]; } else { return false; } } // Driver code public static void main(String args[]) { // Given array int arr[] = { 23, 34, 45, 12, 17, 19 }; // calling method to check // cirularly sorted array boolean result = checkCircularSorted(arr); // print result if (result == true) { System.out.println( "Array is circularly sorted"); } else { System.out.println( "Array is not circularly sorted"); } }} |
Python
# Python program to check whether# the array is circularly sorted# Function to check whether# array is circularly sorteddef checkCircularSorted(arr): # cnt variable will store count of # arr[i-1] > arr[i] cnt = 0 n = len(arr) for i in range(1, n): # increase cnt if arr[i-1] > arr[i] if arr[i - 1] > arr[i]: cnt += 1 # if cnt > 1 then false # else true if cnt == 1: # check first and last element. return arr[0] > arr[n-1]; else: return False# Driver codeif __name__ == '__main__': # Given array arr = [23, 34, 45, 12, 17, 19] # Calling function to check # cirularly sorted array result = checkCircularSorted(arr) # Print result if result == True: print("Array is circularly sorted") else: print("Array is not circularly sorted")# This code has been contributed by Sachin Sahara (sachin801) |
C#
// C# program to check whether// the array is circularly sortedusing System;public class GFG { // Method to check whether // array is circularly sorted public static bool checkCircularSorted(int []arr) { // cnt variable will store // count of arr[i-1] > arr[i] int cnt = 0; for (int i = 1; i < arr.Length; i++) { // increase cnt if arr[i-1] > arr[i] if (arr[i - 1] > arr[i]) { cnt++; } } // if cnt > 1 then false // else true if (cnt == 1) { // check first and last element. return arr[0] > arr[arr.Length-1]; } else { return false; } } // Driver code public static void Main(string []args) { // Given array int []arr = { 23, 34, 45, 12, 17, 19 }; // calling method to check // cirularly sorted array bool result = checkCircularSorted(arr); // print result if (result == true) { Console.WriteLine("Array is circularly sorted"); } else { Console.WriteLine("Array is not circularly sorted"); } }}// This code is contributed by AnkThon |
Javascript
<script>// JavaScript program to check whether// the array is circularly sorted// Function to check whether// array is circularly sortedfunction checkCircularSorted(arr, n){ // cnt variable will store count of // arr[i-1] > arr[i] let cnt = 0; for (let i = 1; i < n; i++) { // increase cnt if arr[i-1] > arr[i] if (arr[i - 1] > arr[i]) { cnt++; } } // if cnt > 1 then false // else true if (cnt == 1) { // check first and last element. return arr[0] > arr[n-1]; } else { return false; }}// Driver code// Given arraylet arr = [ 23, 34, 45, 12, 17, 19 ];// size of arraylet N = arr.length;// Calling function to check// cirularly sorted arraylet result = checkCircularSorted(arr, N);// Print resultif (result) { document.write("Array is circularly sorted","</br>");}else { document.write("Array is not circularly sorted","</br>");}// This code is contributed by shinjanpatra</script> |
Output
Array is circularly sorted
Time Complexity: O(n)
Auxiliary Space: O(1)
Similarly, we can do the above operation for descending circularly sorted array. In this case we need to consider the count of the case where, arr [i-1] < arr[i].
Related articles:
- Check if an array is sorted and rotated
- Find the Rotation Count in Rotated Sorted array
- Search an element in a sorted and rotated array
- Find the minimum element in a sorted and rotated array
- Maximum element in a sorted and rotated array
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!
