Knowledge Base | Daily Notes

Array is sorted and rotated

Aug 30, 20242 min read

Intuition

  • Find the minimum element of the array, find the max as well since it can be done in same iteration.
  • Once above is found rotate across whole array from that point verifying left is smaller than right.

Code

class Solution:
    ##Complete this function
    #Function to check if array is sorted and rotated.
    def checkRotatedAndSorted(self,arr,n):
        max_num, min_num = max(arr), min(arr)
    
        for i in range(n):
            # Check ascension pattern and rotation clause.
            if (arr[i] == max_num) and i+1 < n and (
                (arr[i+1] == min_num) and (arr[0] >= arr[-1])):
                return True
            # Check descent pattern and rotation clause.
            if (arr[i] == min_num) and i+1 < n and (
                (arr[i+1] == max_num) and (arr[-1] >= arr[0])):
                return False
        
        return False

Attempt 1

  • gyan_pelo So the condition needs to be found where the elements are swapping the order that is where left is greater than right element, after that is found make sure no other element has this condition as true and all right element are greater than left element. I’m enjoying coding in Javascript more.
  • pseudo_code
var nums = [4, 6, 1, 2, 3]
Var defaults = 0
For (var i=0; i < nums.length; i++) {
  if (num[i] > num[i+1]) {
   Defaults+= 1;
  }
  If (defaults > 1) {
   Return false
  }
}

Attempt 2

  • gyan_pelo
  • There can be a couple of ways to do it, one is to find the minimum element and then verify all elements before and after it follow ascendant descend pattern. Other is too keep track to places where left is greater than right and if the number of defaulter is more than one then array is not sorted and rotated.
var nums = [4, 6, 1, 2, 3]
Var defaults = 0;
// find minimum
let min = Number.MIN_NUMBER;
let minIndex = 0;
for (let i = 0; i < minIndex; i++) {
	const curr = nums[i];
	if (num < min) {
		min = num;
		minIndex = i;
	}
}
 
const isSortedRotated = true;
// check for values before min and after min, two loops should be fine
for (var i=0; i < minIndex; i++) {
  let cur = nums[i];
  if (cur > cur[i+1]) {
	  isSortedRotated = false;
  }
}
 
for (let j = minIndex; j < nums.length; j++) {
  let cur = nums[i];
	if (cur > cur[i+1]) {
	  isSortedRotated = false;
  }
 
}

Graph View

Backlinks