💡 Problem Formulation: Given an array of integers, we want to determine if the array has been sorted in non-decreasing order and then rotated about a pivot. A rotated array means that it may start from the middle of a sorted array and continue until the end, wrapping around to the beginning of the array. For example, given the array [3, 4, 5, 1, 2], we want our program to return True because the sorted version of this array, [1, 2, 3, 4, 5], can be rotated 3 places to match our input.
Method 1: Sequential Check
Using a sequential check, we iterate through the array to verify two conditions: that there is only one place where the sequence decreases and that the last element is less than the first element. This method is intuitive and directly reflects the problem description.
Here’s an example:
def is_sorted_and_rotated(arr):
decrease_count = 0
arr_len = len(arr)
for i in range(1, arr_len):
if arr[i - 1] > arr[i]:
decrease_count += 1
if arr_len > 1 and arr[-1] > arr[0]:
decrease_count += 1
return decrease_count == 1
print(is_sorted_and_rotated([3, 4, 5, 1, 2]))Output: True
This code snippet defines a function is_sorted_and_rotated() that takes an array as its input. It traverses the array, counting decreases between consecutive elements. If there is more than one decrease or if the last element is greater than the first, it returns False. It only returns True when there is exactly one such decrease, indicating that the array has been correctly sorted and then rotated.
Method 2: Using Python’s Built-in Functions
Python gives us the ability to sort arrays and work with slices efficiently. We can check for sorted and rotated status by sorting the array, then checking if a rotation of this sorted array matches the original. Here, we use min() to find the pivot, around which we’ll assume the rotation happened.
Here’s an example:
def is_sorted_and_rotated_v2(arr):
sorted_arr = sorted(arr)
min_index = arr.index(min(arr))
rotated = arr[min_index:] + arr[:min_index]
return rotated == sorted_arr
print(is_sorted_and_rotated_v2([3, 4, 5, 1, 2]))Output: True
This function, is_sorted_and_rotated_v2(), sorts the input array and then attempts to find a rotation that might equal the sorted array. It does this by using min() to find the pivot, then concatenates the two resulting slices to simulate the rotation. The function ultimately checks this potentially rotated array against the sorted array to identify a match.
Method 3: Two-Pointer Check
The two-pointer technique involves initiating pointers at the start and end of the array, then moving them towards each other as they validate the sorting and rotation requirements. This method is more efficient as it often requires less than a full traversal of the array.
Here’s an example:
def is_sorted_and_rotated_v3(arr):
if len(arr) < 3:
return True
left, right = 0, len(arr) - 1
while left < right and arr[left] 0 and arr[right] >= arr[right - 1]:
right -= 1
return right - left = arr[right] and (left == 0 or arr[0] >= arr[right])
print(is_sorted_and_rotated_v3([3, 4, 5, 1, 2]))Output: True
The function is_sorted_and_rotated_v3() uses two pointers that move towards the center from both ends of the array. Once they have either overlapped or are adjacent while maintaining non-decreasing order and the rotation condition, the function concludes that the array is sorted and rotated.
Method 4: Optimized Sequential Check
This method improves upon the first one by immediately returning False once a second decrease is found or if the last element is greater than the first. This early return prevents unnecessary checks and makes the function more efficient.
Here’s an example:
def is_sorted_and_rotated_v4(arr):
decrease_count = 0
for i in range(1, len(arr)):
if arr[i - 1] > arr[i]:
decrease_count += 1
if decrease_count > 1 or arr[-1] > arr[0]:
return False
return decrease_count == 1
print(is_sorted_and_rotated_v4([3, 4, 5, 1, 2]))Output: True
The function is_sorted_and_rotated_v4() is an optimized version of the sequential check that includes early exit conditions to enhance performance. Similar to Method 1, it keeps track of decreases but adds a quick check to bail out early if necessary conditions fail.
Bonus One-Liner Method 5: Comprehension and All()
A Python one-liner can utilize list comprehensions and the all() function to create a condensed version of the check, although at the cost of readability. This approach is not as efficient but demonstrates Python’s ability to perform tasks in a succinct manner.
Here’s an example:
is_sorted_and_rotated_v5 = lambda arr: all(arr[i] arr[0] print(is_sorted_and_rotated_v5([3, 4, 5, 1, 2]))
Output: False
This one-liner function, is_sorted_and_rotated_v5(), uses a list comprehension wrapped in all() to enforce that each element is less than or equal to the next, considering the wrap-around using the modulo operator. It then checks that the last element is greater than the first, indicating a rotation. The result in this case is False because the last check fails for a properly sorted and rotated array.
Summary/Discussion
- Method 1: Sequential Check. Simple and intuitive. Iterates over the whole array, which could be inefficient for large arrays.
- Method 2: Built-in Functions. Utilizes Python’s powerful built-in functions. Might not be the most efficient due to sorting and might be less intuitive.
- Method 3: Two-Pointer Check. Typically more efficient by potentially requiring less than a full array traversal. However, it can be trickier to get right and understand.
- Method 4: Optimized Sequential Check. Enhances the first method by including early exits for better performance. Straightforward but can still iterate over the entire array.
- Bonus One-Liner Method 5: Comprehension and All(). Demonstrates Python’s compact coding abilities, but lacks efficiency and readability.