Kiểm tra sắp xếp mảng được với điều kiện hoán đổi liền kề chênh lệch 1 (Python)

Bài toán: Cho mảng nums chứa các số 0 đến n-1. Cho phép hoán đổi hai phần tử liền kề chỉ khi chênh lệch tuyệt đối = 1. Kiểm tra có thể sắp xếp mảng không.

Quan sát

Chỉ được swap cặp (x, x+1) hoặc (x+1, x). Nghĩa là: thứ tự tương đối của các số chênh lệch ≥ 2 không thể thay đổi.
→ Mảng có thể sắp xếp ⟺ không tồn tại cặp nghịch thế (inversion) với chênh lệch > 1.

Triển khai Python (Greedy)

def solve(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            # Phát hiện nghịch thế
            if nums[i] - nums[i + 1] == 1:
                # Chênh lệch 1 → được swap
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
            else:
                # Chênh lệch > 1 → không thể swap → impossible
                return False
    return True

# Test
print(solve([1, 0, 3, 2, 5, 4]))  # True: swap (1,0), (3,2), (5,4) → [0,1,2,3,4,5]
print(solve([2, 0, 1]))           # False: 2>0 chênh 2, không swap được
print(solve([0, 2, 1]))           # True: swap (2,1) → [0,1,2]

Kết quả

True

Giải thích

• Duyệt mảng trái→phải, gặp cặp nghịch thế (giảm) thì kiểm tra chênh lệch.
• Chênh lệch = 1: swap ngay (greedy). Chênh lệch > 1: trả về False.
• Đúng vì: swap chỉ đổi chỗ hai số liên tiếp, không thể "nhảy qua" số khác.
• Độ phức tạp: O(n) time, O(1) space (sửa in-place).