Check if an array is rotated sorted order
The problem you're addressing is about determining whether an array is in a rotated sorted order. In this context, a rotated sorted order means an array that was sorted in ascending order but then rotated some number of positions, potentially introducing a circular shift. The task is to identify whether the given array follows this pattern or not.
Problem Statement
Given an array, we need to determine if it is a rotated sorted sequence or not. If the array is sorted in a rotated manner, we output "Yes." If it's sorted but not rotated, we output "No: Array is sorted but not rotated." If it's not a rotated sorted sequence, we output "No: Array is not in the form of a rotated and sorted sequence."
Example
Let's consider a few arrays to illustrate this concept:
-
arr1[] = {1, 2, 3, 4, 5, 6}
- The array is sorted in ascending order.
- It's not rotated.
- Output: "No: Array is sorted but not rotated."
-
arr2[] = {15, 17, 18, 1, 4, 6, 8, 9, 12}
- The array is rotated after the element 18.
- It's still sorted in ascending order after rotation.
- Output: "Yes: Array is in the form of a rotated and sorted order."
-
arr3[] = {6, 7, 8, 1, 3, 9}
- The array is rotated after the element 8.
- The rotation disrupts the ascending order.
- Output: "No: Array is not in the form of a rotated and sorted sequence."
Idea to Solve
We can solve this problem by observing the characteristics of a rotated sorted array. There are two cases to consider:
- If the array is sorted in non-decreasing order after rotation, then it's a rotated sorted sequence.
- If the array is sorted but not rotated, then it's simply sorted, not rotated.
Pseudocode
function is_sorted_rotated(arr, size):
if size <= 1:
return
status = 1
flag = 1
for i from 0 to size - 2 and status == 1:
if flag == 1:
if arr[i] > arr[i+1]:
flag += 1
else if flag == 2:
if arr[0] < arr[i] or arr[0] < arr[i+1] or arr[i] > arr[i+1]:
status = 0
print_data(arr, size)
if flag == 1:
print "No: Array is sorted but not rotated"
else if status == 1:
print "Yes: Array is in the form of a rotated and sorted order"
else:
print "No: Array is not in the form of a rotated and sorted sequence"
function print_data(arr, size):
for i from 0 to size - 1:
print arr[i]
# Test cases
arr1 = [1, 2, 3, 4, 5, 6]
is_sorted_rotated(arr1, size_of(arr1))
arr2 = [15, 17, 18, 1, 4, 6, 8, 9, 12]
is_sorted_rotated(arr2, size_of(arr2))
arr3 = [6, 7, 8, 1, 3, 9]
is_sorted_rotated(arr3, size_of(arr3))
Algorithm Explanation
- The
is_sorted_rotated
function takes an arrayarr
and its sizesize
as input. - It checks if the size is less than or equal to 1 and returns if true.
- It initializes
status
to 1 (assumption that it's a rotated sorted sequence) andflag
to 1 (initial flag to detect the rotation). - It iterates through the array, checking for two conditions based on the value of
flag
. - If
flag
is 1, it checks whether the current element is greater than the next element. If true, it incrementsflag
. - If
flag
is 2, it checks whether the array's first element is less than both the current and next elements, and whether the current element is greater than the next element. If any of these conditions are true, it means the array is not a rotated sorted sequence, andstatus
is set to 0. - After the loop, it prints the array using the
print_data
function. - Based on the values of
flag
andstatus
, it prints the appropriate output message.
Code Solution
//C Program
//Check if an array is rotated sorted sequence
#include <stdio.h>
//Print array elements
void print_data(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
printf("\n");
}
void is_sorted_rotated(int arr[],int size)
{
if(size<=1)
{
return;
}
int status = 1;
int flag = 1;
for (int i = 0; i < size-1 && status==1; ++i)
{
if(flag==1)
{
//Check whether array element is a valid incremented sequence?
if(arr[i] > arr[i+1])
{
//When not
flag++;
}
}
else if(flag==2)
{
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if(arr[0] < arr[i] || arr[0] < arr[i+1] || arr[i] > arr[i+1])
{
//Not rotated and sorted
status = 0;
}
}
}
print_data(arr,size);
//Test Case
if(flag==1)
{
printf(" No : Array is sorted but not rotated\n");
}
else if(status==1)
{
printf(" Yes : Array is form of an rotated and sorted order \n");
}
else
{
printf(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
int main()
{
int arr1[] ={1,2,3,4,5,6};
//Get the size of array
int size=(sizeof(arr1)/sizeof(arr1[0]));
is_sorted_rotated(arr1,size);
int arr2[] ={15,17,18,1,4,6,8,9,12};
//Get the size of array
size=(sizeof(arr2)/sizeof(arr2[0]));
is_sorted_rotated(arr2,size);
int arr3[] ={6,7,8,1,3,9};
//Get the size of array
size=(sizeof(arr3)/sizeof(arr3[0]));
is_sorted_rotated(arr3,size);
return 0;
}
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
/*
C++ Program
Check if an array is rotated sorted sequence
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Print array elements
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
void is_sorted_rotated(int arr[], int size) {
if (size <= 1) {
return;
}
bool status = true;
int flag = 1;
for (int i = 0; i < size - 1 && status == true; ++i) {
if (flag == 1) {
//Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1]) {
//When not
flag++;
}
} else
if (flag == 2) {
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if (arr[0] < arr[i] || arr[0] < arr[i + 1] || arr[i] > arr[i + 1]) {
//Not rotated and sorted
status = false;
flag++;
}
}
}
this->print_data(arr, size);
//Test Case
if (flag == 1) {
cout << " No : Array is sorted but not rotated\n";
} else
if (status == true) {
cout << " Yes : Array is form of an rotated and sorted order \n";
} else {
cout << " No : Array is not the form of a rotated and sorted sequence\n";
}
}
};
int main() {
MyArray obj ;
//Test Case
//Define array elements
int arr1[] = {
1,
2,
3,
4,
5,
6
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.is_sorted_rotated(arr1, size);
int arr2[] = {
15,
17,
18,
1,
4,
6,
8,
9,
12
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
obj.is_sorted_rotated(arr2, size);
int arr3[] = {
6,
7,
8,
1,
3,
9
};
//Get the size of array
size = sizeof(arr3) / sizeof(arr3[0]);
obj.is_sorted_rotated(arr3, size);
return 0;
}
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
/*
Java Program
Check if an array is rotated sorted sequence
*/
public class MyArray {
//Print array elements
public void print_data(int []arr,int size)
{
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
public void is_sorted_rotated(int []arr,int size)
{
if(size<=1)
{
return;
}
boolean status = true;
int flag = 1;
for (int i = 0; i < size-1 && status==true; ++i)
{
if(flag==1)
{
//Check whether array element is a valid incremented sequence?
if(arr[i] > arr[i+1])
{
//When not
flag++;
}
}
else if(flag==2)
{
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if(arr[0] < arr[i] || arr[0] < arr[i+1] || arr[i] > arr[i+1])
{
//Not rotated and sorted
status = false;
flag++;
}
}
}
print_data(arr,size);
//Test Case
if(flag==1)
{
System.out.print(" No : Array is sorted but not rotated\n");
}
else if(status==true)
{
System.out.print(" Yes : Array is form of an rotated and sorted order \n");
}
else
{
System.out.print(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Test Case
//Define array elements
int []arr1 ={1,2,3,4,5,6};
//Get the size of array
int size=arr1.length;
obj.is_sorted_rotated(arr1,size);
int []arr2 ={15,17,18,1,4,6,8,9,12};
//Get the size of array
size=arr2.length;
obj.is_sorted_rotated(arr2,size);
int []arr3 ={6,7,8,1,3,9};
//Get the size of array
size=arr3.length;
obj.is_sorted_rotated(arr3,size);
}
}
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
/*
C# Program
Check if an array is rotated sorted sequence
*/
using System;
public class MyArray {
//Print array elements
public void print_data(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void is_sorted_rotated(int[] arr, int size) {
if (size <= 1) {
return;
}
Boolean status = true;
int flag = 1;
for (int i = 0; i < size - 1 && status == true; ++i) {
if (flag == 1) {
//Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1]) {
//When not
flag++;
}
} else if (flag == 2) {
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if (arr[0] < arr[i] || arr[0] < arr[i + 1] || arr[i] > arr[i + 1]) {
//Not rotated and sorted
status = false;
flag++;
}
}
}
print_data(arr, size);
//Test Case
if (flag == 1) {
Console.Write(" No : Array is sorted but not rotated\n");
} else if (status == true) {
Console.Write(" Yes : Array is form of an rotated and sorted order \n");
} else {
Console.Write(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Test Case
//Define array elements
int[] arr1 = {
1,
2,
3,
4,
5,
6
};
//Get the size of array
int size = arr1.Length;
obj.is_sorted_rotated(arr1, size);
int[] arr2 = {
15,
17,
18,
1,
4,
6,
8,
9,
12
};
//Get the size of array
size = arr2.Length;
obj.is_sorted_rotated(arr2, size);
int[] arr3 = {
6,
7,
8,
1,
3,
9
};
//Get the size of array
size = arr3.Length;
obj.is_sorted_rotated(arr3, size);
}
}
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
# Python 3 Program
# Check if an array is rotated sorted sequence
class MyArray :
# Print array elements
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i],end="")
i += 1
print(end="\n")
def is_sorted_rotated(self, arr, size) :
if (size <= 1) :
return
status = True
flag = 1
i = 0
while (i < size - 1 and status == True) :
if (flag == 1) :
# Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1]) :
# When not
flag += 1
elif (flag == 2) :
# array element
# Also check that first element of array is greater than or equal to next upcoming
if (arr[0] < arr[i] or arr[0] < arr[i + 1] or arr[i] > arr[i + 1]) :
# Not rotated and sorted
status = False
flag += 1
i += 1
self.print_data(arr, size)
# Test Case
if (flag == 1) :
print(" No : Array is sorted but not rotated")
elif (status == True) :
print(" Yes : Array is form of an rotated and sorted order ")
else :
print(" No : Array is not the form of a rotated and sorted sequence")
def main() :
obj = MyArray()
arr1 = [1, 2, 3, 4, 5, 6]
# Get the size of array
size = len(arr1)
obj.is_sorted_rotated(arr1, size)
arr2 = [15, 17, 18, 1, 4, 6, 8, 9, 12]
# Get the size of array
size = len(arr2)
obj.is_sorted_rotated(arr2, size)
arr3 = [6, 7, 8, 1, 3, 9]
# Get the size of array
size = len(arr3)
obj.is_sorted_rotated(arr3, size)
if __name__ == "__main__":
main()
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
# Ruby Program
# Check if an array is rotated sorted sequence
class MyArray
# Print array elements
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
def is_sorted_rotated(arr, size)
if (size <= 1)
return
end
status = true
flag = 1
i = 0
while (i < size - 1 and status == true)
if (flag == 1)
# Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1])
# When not
flag += 1
end
elsif (flag == 2)
# array element
# Also check that first element of array is greater than or equal to next upcoming
if (arr[0] < arr[i] or arr[0] < arr[i + 1] or arr[i] > arr[i + 1])
# Not rotated and sorted
status = false
flag += 1
end
end
i += 1
end
self.print_data(arr, size)
# Test Case
if (flag == 1)
print(" No :Array is sorted but not rotated\n")
elsif (status == true)
print(" Yes :Array is form of an rotated and sorted order \n")
else
print(" No :Array is not the form of a rotated and sorted sequence\n")
end
end
end
def main()
obj = MyArray.new()
arr1 = [1, 2, 3, 4, 5, 6]
# Get the size of array
size = arr1.length
obj.is_sorted_rotated(arr1, size)
arr2 = [15, 17, 18, 1, 4, 6, 8, 9, 12]
# Get the size of array
size = arr2.length
obj.is_sorted_rotated(arr2, size)
arr3 = [6, 7, 8, 1, 3, 9]
# Get the size of array
size = arr3.length
obj.is_sorted_rotated(arr3, size)
end
main()
Output
1 2 3 4 5 6
No :Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes :Array is form of an rotated and sorted order
6 7 8 1 3 9
No :Array is not the form of a rotated and sorted sequence
/*
Scala Program
Check if an array is rotated sorted sequence
*/
class MyArray {
//Print array elements
def print_data(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
def is_sorted_rotated(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var status: Boolean = true;
var flag: Int = 1;
var i: Int = 0;
while (i < size - 1 && status == true) {
if (flag == 1) {
//Check whether array element is a valid incremented sequence?
if (arr(i) > arr(i + 1)) {
//When not
flag += 1;
}
} else
if (flag == 2) {
// array element
// Also check that first element of array is greater than or equal to next upcoming
if (arr(0) < arr(i) || arr(0) < arr(i + 1) || arr(i) > arr(i + 1)) {
//Not rotated and sorted
status = false;
flag += 1;
}
}
i += 1;
}
this.print_data(arr, size);
//Test Case
if (flag == 1) {
print(" No : Array is sorted but not rotated\n");
} else
if (status == true) {
print(" Yes : Array is form of an rotated and sorted order \n");
} else {
print(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr1: Array[Int] = Array(1, 2, 3, 4, 5, 6);
//Get the size of array
var size: Int = arr1.length;
obj.is_sorted_rotated(arr1, size);
var arr2: Array[Int] = Array(15, 17, 18, 1, 4, 6, 8, 9, 12);
//Get the size of array
size = arr2.length;
obj.is_sorted_rotated(arr2, size);
var arr3: Array[Int] = Array(6, 7, 8, 1, 3, 9);
//Get the size of array
size = arr3.length;
obj.is_sorted_rotated(arr3, size);
}
}
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
/*
Swift 4 Program
Check if an array is rotated sorted sequence
*/
class MyArray {
//Print array elements
func print_data(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i],terminator:"");
i += 1;
}
print(terminator:"\n");
}
func is_sorted_rotated(_ arr: [Int], _ size: Int) {
if (size <= 1) {
return;
}
var status: Bool = true;
var flag: Int = 1;
var i: Int = 0;
while (i < size - 1 && status == true) {
if (flag == 1) {
//Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1]) {
//When not
flag += 1;
}
} else
if (flag == 2) {
// array element
// Also check that first element of array is greater than or equal to next upcoming
if (arr[0] < arr[i] || arr[0] < arr[i + 1] || arr[i] > arr[i + 1]) {
//Not rotated and sorted
status = false;
flag += 1;
}
}
i += 1;
}
self.print_data(arr, size);
//Test Case
if (flag == 1) {
print(" No : Array is sorted but not rotated");
} else
if (status == true) {
print(" Yes : Array is form of an rotated and sorted order ");
} else {
print(" No : Array is not the form of a rotated and sorted sequence");
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr1: [Int] = [1, 2, 3, 4, 5, 6];
//Get the size of array
var size: Int = arr1.count;
obj.is_sorted_rotated(arr1, size);
let arr2: [Int] = [15, 17, 18, 1, 4, 6, 8, 9, 12];
//Get the size of array
size = arr2.count;
obj.is_sorted_rotated(arr2, size);
let arr3: [Int] = [6, 7, 8, 1, 3, 9];
//Get the size of array
size = arr3.count;
obj.is_sorted_rotated(arr3, size);
}
main();
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
<?php
/*
Php Program
Check if an array is rotated sorted sequence
*/
class MyArray {
//Print array elements
public function print_data($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
echo("\n");
}
public function is_sorted_rotated($arr, $size) {
if ($size <= 1) {
return;
}
$status = true;
$flag = 1;
for ($i = 0; $i < $size - 1 && $status == true; ++$i) {
if ($flag == 1) {
//Check whether array element is a valid incremented sequence?
if ($arr[$i] > $arr[$i + 1]) {
//When not
$flag++;
}
} else
if ($flag == 2) {
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if ($arr[0] < $arr[$i] || $arr[0] < $arr[$i + 1] || $arr[$i] > $arr[$i + 1]) {
//Not rotated and sorted
$status = false;
$flag++;
}
}
}
$this->print_data($arr, $size);
//Test Case
if ($flag == 1) {
echo(" No : Array is sorted but not rotated\n");
} else
if ($status == true) {
echo(" Yes : Array is form of an rotated and sorted order \n");
} else {
echo(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
};
function main() {
$obj = new MyArray();
//Test Case
//Define array elements
$arr1 = array(1, 2, 3, 4, 5, 6);
//Get the size of array
$size = count($arr1);
$obj->is_sorted_rotated($arr1, $size);
$arr2 = array(15, 17, 18, 1, 4, 6, 8, 9, 12);
//Get the size of array
$size = count($arr2);
$obj->is_sorted_rotated($arr2, $size);
$arr3 = array(6, 7, 8, 1, 3, 9);
//Get the size of array
$size = count($arr3);
$obj->is_sorted_rotated($arr3, $size);
}
main();
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
/*
Node Js Program
Check if an array is rotated sorted sequence
*/
class MyArray {
//Print array elements
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
is_sorted_rotated(arr, size) {
if (size <= 1) {
return;
}
var status = true;
var flag = 1;
for (var i = 0; i < size - 1 && status == true; ++i) {
if (flag == 1) {
//Check whether array element is a valid incremented sequence?
if (arr[i] > arr[i + 1]) {
//When not
flag++;
}
} else
if (flag == 2) {
// Check whether array element is a valid incremented sequence?
// Also check that first element of array is greater than or equal to next upcoming
// array element
if (arr[0] < arr[i] || arr[0] < arr[i + 1] || arr[i] > arr[i + 1]) {
//Not rotated and sorted
status = false;
flag++;
}
}
}
this.print_data(arr, size);
//Test Case
if (flag == 1) {
process.stdout.write(" No : Array is sorted but not rotated\n");
} else
if (status == true) {
process.stdout.write(" Yes : Array is form of an rotated and sorted order \n");
} else {
process.stdout.write(" No : Array is not the form of a rotated and sorted sequence\n");
}
}
}
function main(args) {
var obj = new MyArray();
//Test Case
//Define array elements
var arr1 = [1, 2, 3, 4, 5, 6];
//Get the size of array
var size = arr1.length;
obj.is_sorted_rotated(arr1, size);
var arr2 = [15, 17, 18, 1, 4, 6, 8, 9, 12];
//Get the size of array
size = arr2.length;
obj.is_sorted_rotated(arr2, size);
var arr3 = [6, 7, 8, 1, 3, 9];
//Get the size of array
size = arr3.length;
obj.is_sorted_rotated(arr3, size);
}
main();
Output
1 2 3 4 5 6
No : Array is sorted but not rotated
15 17 18 1 4 6 8 9 12
Yes : Array is form of an rotated and sorted order
6 7 8 1 3 9
No : Array is not the form of a rotated and sorted sequence
Time Complexity
The time complexity of the algorithm is O(n), where n is the size of the input array. This is because we iterate through the array once to determine its characteristics, and the array size directly determines the number of iterations.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment