1752. Check if Array Is Sorted and Rotated - Detailed Explanation

Problem Statement

Description:
You are given an array of distinct integers. An array is considered sorted and rotated if it is obtained by taking an array that was originally sorted in non-decreasing order and then performing a non-zero number of rotations. In other words, the array must be both sorted (in non-decreasing order) and rotated at least once.

Task:
Return true if the array is sorted and rotated, and false otherwise.

Important Note:

• If the array is completely sorted in non-decreasing order (i.e. not rotated at all), it should return false.

Example 1:

• Input: nums = [3, 4, 5, 1, 2]
• Output: true
• Explanation:
  The original sorted array [1, 2, 3, 4, 5] was rotated to get [3, 4, 5, 1, 2].

Example 2:

• Input: nums = [1, 2, 3]
• Output: false
• Explanation:
  The array is sorted in non-decreasing order but not rotated.

Example 3:

• Input: nums = [2, 1, 3, 4]
• Output: false
• Explanation:
  The array is not sorted and rotated from a non-decreasing array.

Constraints:

• The array contains distinct integers.
• The length of the array is at least 1.

Hints to Approach the Problem

1. Count the “Drop Points”:
   If an array is obtained by rotating a sorted array, then it will have exactly one "drop" (a point where an element is greater than its next element) when you consider the array in a circular fashion.

2. Circular Check:
   Remember to compare the last element with the first element since the array is a rotated version of a sorted array.

3. Edge Case – No Rotation:
   If there is no drop (i.e. the array is fully sorted in non-decreasing order), then the array has not been rotated and you should return false.

Approach

Core Idea:

• Iterate through the array and count the number of times a drop occurs (i.e., nums[i] > nums[(i+1) % n] where n is the length of the array).
• Key observations:
  • Exactly one drop: Indicates the array is a rotated version of a sorted array.
  • Zero drops: Means the array is completely sorted (i.e., no rotation was performed).
  • More than one drop: Means the array is not a rotated sorted array.

Step-by-Step Walkthrough:

1. Initialization:
   Set a counter count to 0. This counter will keep track of the number of drop points.

2. Iterate Over the Array:
   For each index i from 0 to n-1, compare nums[i] with nums[(i+1) % n] (using modulo to wrap around the end of the array).

   • If nums[i] > nums[(i+1) % n], increment the count.

3. Determine the Result:

   • If count is exactly 1, return true.
   • Otherwise (if count is 0 or more than 1), return false.

4. Edge Case – Single Element:
   For an array with a single element, since no rotation can really change the order, it is not considered rotated, so return false.

Complexity Analysis

• Time Complexity: O(n)
  We make one pass through the array to count the drop points.

• Space Complexity: O(1)
  Only a few extra variables are used, independent of the input size.

Code Implementation

Python Code