Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!

Hôm nay là mùng 5 Tết, ngày cuối cùng của kỳ nghỉ! Trước khi quay lại guồng quay công việc và học tập, hãy cùng mình “xoay vòng may mắn” với một bài toán thú vị về mảng xoay vòng! 🚀

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] là mảng gốc được sắp xếp.
Bạn có thể xoay mảng 3 lần để bắt đầu từ phần tử 3: [3,4,5,1,2].

Input: nums = [2,1,3,4]
Output: false
Explanation: Không có mảng nào sau khi xoay có thể tạo thành nums.

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] là mảng gốc đã được sắp xếp.
Bạn có thể xoay 0 lần (không xoay) để có nums.

🎯 Problem Visualization

Hãy tưởng tượng bạn đang chơi trò Vòng Xoay May Mắn ngày Tết:

Ban đầu (đã sắp xếp):
1 → 2 → 3 → 4 → 5
⬆️ Tăng dần

Sau khi xoay:
3 → 4 → 5 → 1 → 2
⬇️
Xuất hiện điểm gãy!

🔥 First Thoughts & Intuition

Một mảng được xoay vòng từ mảng đã sắp xếp chỉ được có đúng một điểm gãy – giống như một dây pháo chỉ nổ một lần:

Hợp lệ:
🧨 3 → 🧨 4 → 🧨 5 → 💥 1 → 🧨 2
⬇️
Chỉ 1 điểm gãy!

Không hợp lệ:
🧨 2 → 💥 1 → 🧨 3 → 💥 4
⬇️ ⬇️
Gãy #1 Gãy #2

💡 Approach

1. Xác Định Điểm Gãy 🔍

Một điểm gãy xuất hiện khi:
Số trước > Số sau

Ví dụ minh họa:
5 → 1 (Điểm gãy!)
⬆️ ⬇️
Lớn Nhỏ

2. Circular Harmony Check ⭕

Do mảng bị xoay vòng, cần kiểm tra cả phần tử cuối với phần tử đầu:
[3, 4, 5, 1, 2]
2 → 3 (✅ Hợp lệ)
⬆️ ⬆️
Cuối Đầu

🚀 Implementation

class Solution {
public:
    bool check(vector<int>& nums) {
        int count = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
            if (count > 1) return false;
        }
        
        return true;
    }
};

🎯 Examples Walkthrough

Trường Hợp 1: Xoay Hợp Lệ

Input: [3,4,5,1,2]

Bước kiểm tra:
3 → 4 (✅)
4 → 5 (✅)
5 → 1 (❌ Điểm gãy!)
1 → 2 (✅)
2 → 3 (✅)

Kết quả: true 🎊

Trường Hợp 2: Xoay Không Hợp Lệ

Input: [2,1,3,4]

Bước kiểm tra:
2 → 1 (❌ Điểm gãy #1)
1 → 3 (✅)
3 → 4 (✅)
4 → 2 (❌ Điểm gãy #2)

Kết quả: false ❌

📊 Phân Tích Độ Phức Tạp

• Độ phức tạp thời gian: O(N)
  ✅ Một vòng duy nhất qua mảng
• Độ phức tạp không gian: O(1)
  ✅ Chỉ sử dụng 2 biến (count và n)

🔑 Tổng Kết

1. Chỉ được phép có 1 điểm gãy để mảng hợp lệ.
2. Modulo magic ✨ (i + 1) % n giúp kiểm tra vòng tròn.
3. Early termination 💨 Dừng ngay nếu phát hiện hơn 1 điểm gãy.

✨ Chúc các bạn một năm mới may mắn và thành công! 🎆 Đừng quên theo dõi Learning AI with Losers để tiếp tục chinh phục các thử thách Leetcode nhé! 🚀

CODE EDITOR

#leetcode #leetcodedaily #thuậtoán #lậptrình #learningwithlosers #tet2025 #mùng5tết #codingchallenge