5 Best Ways to Check if an Array is Sorted and Rotated in Python

by

💡 Problem Formulation: Determining if an array is both sorted and rotated is a common problem in computer science. A sorted and rotated array means that the array could be considered sorted if one of the rotations brings it to a non-descending order. For example, an input array [3, 4, 5, 1, 2] is both sorted and rotated since the sorted form [1, 2, 3, 4, 5] can be achieved by rotating the original array 3 times to the right.

Method 1: Find Rotation Point

This method involves finding the rotation point, which is the index where the sorted order breaks. Once found, we can check if the segments before and after the rotation point are individually sorted. To verify if the array is sorted and rotated, we make sure there’s only one such breaking point, and the minimum element immediately follows it.

Here’s an example:

def is_sorted_and_rotated(arr):
    rotation_count = 0
    n = len(arr)
    for i in range(n):
        if arr[i] > arr[(i + 1) % n]:
            rotation_count += 1
            rotation_point = i

    return rotation_count == 1 and arr[0] >= arr[rotation_point]

print(is_sorted_and_rotated([3, 4, 5, 1, 2]))

Output: True

This code snippet defines a function is_sorted_and_rotated() that loops through the given array to find the number of rotation points (where the next element is less than the current). It ensures that there’s only one such point and checks if the first element of the array is greater than or equal to the element at the rotation point.

Method 2: Concatenated String Matching

Another approach is creating a string representation of twice the array (simulating two rotations) and checking if the sorted array as a string is a substring. This method leverages string manipulation to bypass direct array comparison.

Here’s an example:

def is_sorted_and_rotated_str(arr):
    sorted_arr = sorted(arr)
    doubled_str = ''.join(map(str, arr + arr))
    sorted_str = ''.join(map(str, sorted_arr))
    return sorted_str in doubled_str

print(is_sorted_and_rotated_str([3, 4, 5, 1, 2]))

Output: True

The function is_sorted_and_rotated_str() sorts the array and then constructs string copies of both the sorted and the doubled input array. The inclusion check verifies if we can obtain the sorted order from the rotated array.

Method 3: Enhanced Brute Force

This method finds all the rotations of the initial array and checks if any of them are sorted. Essentially, for each possible rotated version, we validate if the array is in non-descending order.

Here’s an example:

def is_sorted_and_rotated_brute_force(arr):
    for i in range(len(arr)):
        if arr[i:] + arr[:i] == sorted(arr):
            return True
    return False

print(is_sorted_and_rotated_brute_force([3, 4, 5, 1, 2]))

Output: True

The is_sorted_and_rotated_brute_force() function exhaustively checks each rotation to see if it equals the sorted version of the original array, effectively handling the ‘sorted and rotated’ validation.

Method 4: Optimization Using Set

Instead of performing expensive sorting, we can optimize by comparing the uniqueness of elements in the array and their expected sorted positions using a set. If the set from the array equals the set from a range, and there’s only one rotation point, the array is sorted and rotated.

Here’s an example:

def is_sorted_and_rotated_optimized(arr):
    unique = set(arr)
    expected = set(range(min(arr), max(arr) + 1))
    return len(unique) == len(expected) and len(arr) == len(expected) and is_sorted_and_rotated(arr)

print(is_sorted_and_rotated_optimized([3, 4, 5, 1, 2]))

Output: True

The is_sorted_and_rotated_optimized() function compares the set of unique elements in the array with the expected set range. By doing so, it ensures all elements are present without the need to sort, followed by a call to is_sorted_and_rotated() to validate the rotation.

Bonus One-Liner Method 5: Using min() and count()

Exploiting Python’s list methods, this one-liner checks for the number of occurrences of the minimum element to be one and the sorted sequence to be in two parts within the array.

Here’s an example:

is_sorted_and_rotated_oneliner = lambda arr: arr.count(min(arr)) == 1 and sorted(arr) == arr[arr.index(min(arr)):] + arr[:arr.index(min(arr))]

print(is_sorted_and_rotated_oneliner([3, 4, 5, 1, 2]))

Output: True

This one-liner lambda function first checks if the minimum element doesn’t repeat (which is necessary for a unique pivot). Then it asserts the sequence following this minimum element until the end joined with the start up to this index results in a sorted array.

Summary/Discussion

  • Method 1: Find Rotation Point. Efficient and to the point. It assumes that there’s exactly one point where the order is broken.
  • Method 2: Concatenated String Matching. Interesting use of string methods but not the most intuitive or robust method, especially with large arrays or non-integer values.
  • Method 3: Enhanced Brute Force. Easy to understand but not the most efficient. It could be overkill for a large size array due to its computational complexity.
  • Method 4: Optimization Using Set. This method adds a pre-check optimization to the rotation check, reducing chances of unnecessary computation but making it slightly more complex.
  • Method 5: Bonus One-Liner. Clever and concise, but one-liner solutions can be less readable for those unfamiliar with Python’s syntactic sugar.