Kiểm tra mảng có thể sắp xếp bằng phép xoay vòng không (Python)

Bài toán: Cho mảng nums, kiểm tra có thể sắp xếp tăng dần bằng cách xoay vòng (lấy đoạn cuối đưa lên đầu) không.

Quan sát

Mảng có thể sắp xếp bằng xoay vòng ⟺ mảng là một cyclic shift của mảng đã sắp xếp.
Tức là: mảng có tối đa một cặp nums[i] > nums[i+1] (điểm "gãy"), và phần tử cuối ≤ phần tử đầu.

Triển khai Python

def solve(nums):
    n = len(nums)
    # Đã sắp xếp?
    if all(nums[i] <= nums[i + 1] for i in range(n - 1)):
        return True
    
    # Tìm điểm gãy
    status = True
    for i in range(n - 1):
        if nums[i] > nums[i + 1]:
            break
    i += 1  # i là index bắt đầu phần đã sắp xếp thứ 2
    
    # Kiểm tra phần còn lại đã sắp xếp chưa
    for k in range(i, n - 1):
        if nums[k] > nums[k + 1]:
            status = False
            break
    
    if not status:
        return False
    
    # Kiểm tra điều kiện xoay vòng: last <= first
    return nums[n - 1] <= nums[0]

# Test
print(solve([4, 5, 6, 1, 2, 3]))  # True: xoay [1,2,3,4,5,6]
print(solve([1, 2, 3, 4]))        # True: đã sắp xếp
print(solve([3, 1, 2]))           # True: xoay [1,2,3]
print(solve([2, 1, 3]))           # False: 2 điểm gãy (2>1, 1<3 but 3>2?)

Kết quả

True

Giải thích

• Kiểm tra đã sắp xếp trước (O(n)).
• Tìm index i đầu tiên mà nums[i] > nums[i+1].
• Kiểm tra từ i đến cuối có sắp xếp không.
• Kiểm tra nums[-1] <= nums[0] để đảm bảo nối đuôi với đầu đúng.
• Độ phức tạp: O(n) time, O(1) space.