Check if an array is sorted and rotated

Prerequisites: None

Question

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Reframing the Question

1. What is a sorted array?
1. A sorted array is an array in which the numbers are arranged in either an ascending or descending order.

2. What is a rotation? Moving the last index to the first
1. One rotation, 6 (5th index comes to 0 )

2. Two Rotation, 5 (5th index comes to 0 )

3. Six(len(array)) rotations, same as where we started.

3. Graphical representation
1. one rotation

2. Second rotation

3. Can you find some patterns here? Every time we rotate we are going to get two separate sorted arrays.
4. Both of this array are sorted in their own right.

5. UPPER HALF(ROTATED)
1. Unlike the upper half discussed previously, the upper half in this case is located on the left side instead of the right. The upper half has been rotated. The maximum element in the rotated upper half will always be the last element. All values in the rotated upper half will be greater than those in the unrotated lower path, and vice versa.

6. LOWER HALF(UN ROTATED)
1. The minimum element in the original will always be the first element in the unrotated part. This is because the array is initially sorted (the first element in the lower half was also the first in the initial array), and all values in the lower half are less than those in the upper half.

7. Discontinuities.
1. No matter how many times you rotate, you will get two sorted arrays, except when you rotate len(array) times, resulting in the same array.
1. nums[i] < nums[i+1] < nums[i+2] < nums[i+3]
2. Rotation 1: nums[i+3] > nums[i] < nums[i+1] < nums[i+2]
3. Rotation 2 : nums[i+2] < nums[i+3] > nums[i] < nums[i+1]
4. Rotation 3 : nums[i+1] < nums[i+2] < nums[i+3] > nums[i]
5. Rotation 4 : nums[i] < nums[i+1] < nums[i+2] < nums[i+3]
2. Rotating a sorted array produces two sorted arrays, with an discontinuity at the edges of both halves.

4. Let's rotate an unsorted array and see what happens.

1. Let's rotate one time

2. How is this different from a rotated sorted array? This array has three sorted arrays, and two inconsistencies in the ascending order pattern (from 7 to 2 and 6 to 4), making it not a properly rotated sorted array.

Intuition

1. We know that if an array is sorted and rotated, there is only one irregularity in the ascending order pattern(Both of these halves are sorted in their own right.). This occurs at the border between two halves of the sorted array, where the minimum and maximum values are located.


2. There may be some edge cases. For example, what if we have an array like this? Our normal algorithm will show only one irregularity from 2 to 1 however there is an other irregularity that conveniently hides in the rotation of the array.
1. Is the array rotated and sorted? Rotated Yes. Sorted maybe?

2. Let's go one step back to see how the array looked before being rotated. The first picture is the original and the second one is with one rotation.

3. There was an inconsistency from 5 to 2 caused by the unsorted in the original array, but it became hidden when we rotated the array. This gave us an idea of only one inconsistency.
1. To be sure we don't miss an inconsistency like this, will compare the first element with the last, in addition to any other inconsistencies.
1. After checking for the edge case in the example above, we will get two inconsistencies: one from 5 to 2, and then from 2 to 1.
2. All other inconsistencies(not at the edges) that arise from not being sorted initially will be detected by our regular algorithm.
4. If we encounter more than one inconsistency, we can be sure that the array was neither sorted nor rotated.
5. Two more things to keep in mind.
1. If the array is sorted but not rotated i.e [1,2,3,4]. Will still return true.
2. There may be duplicates in the array, but they won't affect our logic since we won't count them as a discontinuity in the code.

Code

1. Iterate over the array,
1. from index 1 to len(nums), keeping track of the count of inconsistencies.
1. Starting from index 1 instead of zero allows us to compare adjacent elements without going out of bounds.
Copy

count = 0
for i in range(1,len(nums)):

2. If two adjacent numbers break the ascending order pattern we log an inconsistency.
Copy

discontinuity = nums[i-1] > nums[i]
  if discontinuity:
      count += 1

2. Check for inconsistencies at the edges.
Copy

last = nums[-1]
first = nums[0]
discontinuityAtEdges = last > first

if discontinuityAtEdges:
    count += 1

3. If there are more than 1 inconsistencies return True else return False
Copy

if count > 1:
    return False
else:
    return True

4. Complete code
Copy

class Solution:
    def check(self, nums: List[int]) -> bool:
        count = 0
        
        for i in range(1,len(nums)):
            discontinuity = nums[i-1] > nums[i]
            if discontinuity:
                count += 1

        last = nums[-1]
        first = nums[0]
        discontinuityAtEdges = last > first
        
        if discontinuityAtEdges:
            count += 1

        if count > 1:
            return False
        else:
            return True

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(n)

Space Complexity: O(1)

This question came up in an online assessment for me. I attempted to solve it in O(log n) time. Unfortunately, since there is no guarantee that the underlying structure is sorted, we cannot use a binary algorithm, I was able to get it in the end but spent so much time on finding a binary solution as I was tricked by the word “sorted” in “Check if an array is sorted and rotated”, but you need to focus on the word “check” as that is the key to knowing it can only be done in a linear fashion.