Check if array is sorted and rotated

PHOTO EMBED

Tue Feb 08 2022 04:33:48 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #arrays #sorted #rotated

import java.io.*;

class GFG {

	// Function to check if an array is
	// Sorted and rotated clockwise
	static boolean checkIfSortRotated(int arr[], int n)
	{
		// Initializing two variables x,y as zero.
		int x = 0, y = 0;

		// Traversing array 0 to last element.
		// n-1 is taken as we used i+1.
		for (int i = 0; i < n - 1; i++) {
			if (arr[i] < arr[i + 1])
				x++;
			else
				y++;
		}

		// If till now both x,y are greater
		// then 1 means array is not sorted.
		// If both any of x,y is zero means
		// array is not rotated.
		if (x == 1 || y == 1) {
			// Checking for last element with first.
			if (arr[n - 1] < arr[0])
				x++;
			else
				y++;

			// Checking for final result.
			if (x == 1 || y == 1)
				return true;
		}
		// If still not true then definitely false.
		return false;
	}

	// Driver code
	public static void main(String[] args)
	{
		int arr[] = { 5, 1, 2, 3, 4 };

		int n = arr.length;

		// Function Call
		boolean x = checkIfSortRotated(arr, n);
		if (x == true)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}
content_copyCOPY

Check if array is sorted and rotated Given an array arr[] of N distinct integers, check if this array is Sorted (non-increasing or non-decreasing) and Rotated counter-clockwise. Note that input array may be sorted in either increasing or decreasing order, then rotated. A sorted array is not considered as sorted and rotated, i.e., there should be at least one rotation. Example 1: Input: N = 4 arr[] = {3,4,1,2} Output: Yes Explanation: The array is sorted (1, 2, 3, 4) and rotated twice (3, 4, 1, 2). Example 2: Input: N = 3 arr[] = {1,2,3} Output: No Explanation: The array is sorted (1, 2, 3) is not rotated. Your Task: The task is to complete the function checkRotatedAndSorted() which returns true if an array is sorted and rotated clockwise otherwise false. Expected Time Complexity: O(N). Expected Auxiliary Space: O(1). Constraints: 1 <= N <= 10^6 1 <= A[i] <= 10^6 --------------------------------------------------------------------------------------------------------- Approach: Take two variable say x and y, initialized as 0. Now traverse array. If we find previous element is smaller then current, we increase x by one. Else If we find previous element is greater then current we increase y by one. After traversal if any of x and y is not equals to 1, return false. If any of x or y is 1, then compare last element with first element (0th element as current, and last element as previous.) i.e. if last element is greater increase y by one else increase x by one. Again check for x and y if any one is equals to one return true. i.e. Array is sorted and rotated. Else return false. Explanation: The idea is simple. If array is sorted and rotated , element are either increasing or decreasing, but with one exception. So we count how many times the element is greater then its previous element, and how many times the element is smaller then its previous element. The special case is when array is sorted but not rotated. for this check last element with first element specially.

https://practice.geeksforgeeks.org/problems/check-if-array-is-sorted-and-rotated-clockwise-1587115620/1/?track=DSASP-Arrays&batchId=190