Check if array is sorted and rotated
Tue Feb 08 2022 04:33:48 GMT+0000 (Coordinated Universal Time)
Saved by @Uttam #java #gfg #geeksforgeeks #arrays #sorted #rotated
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
Comments