class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        // intervals = [[1, 3], [2, 5], [6, 9]]
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if(n == 0) return {newInterval};

        // Binary Search 尋找要插入的區間
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid][0] < newInterval[0]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 插入區間
        intervals.insert(intervals.begin() + left, newInterval);

        // 處理重疊區間
        vector<vector<int>> res;
        for (auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        vector<vector<int>> res;

        sort(intervals.begin(), intervals.end());

        res.push_back(intervals[0]);

        if (intervals.size() == 1) return res;

        for(int i = 1; i < intervals.size(); i++)
        {

            if (intervals[i][0] <= res.back()[1])
            {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        // Initialize goal as the last index of the array

        // Iterate backwards from the second last element to the first element
        for ()
        {
            // Check if the current index can reach the goal or beyond
            if ()
            {
                // Update the goal to the current index
            }
        }
        // If the goal is 0, it means the start index can reach the end
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int goal = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            if (nums[i] + i >= goal)
            {
                goal = i;
            }
        }
        return goal == 0;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int n = nums.size();
        int maxReach = 0;
        for (int i = 0; i < n; ++i)
        {
            if (i > maxReach) return false;
            maxReach = max(maxReach, nums[i] + i);
        }
        return maxReach >= n - 1;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        int up = 0, down = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        vector<int> res;
        int direction = 0;

        while (true)
        {
            if (direction == 0)
            {
                for (int i = left; i <= right; ++i)
                {
                    res.push_back(matrix[up][i]);
                }
                ++up;
            }
            else if (direction == 1)
            {
                for (int i = up; i <= down; ++i)
                {
                    res.push_back(matrix[i][right]);
                }
                --right;
            }
            else if (direction == 2)
            {
                for(int i = right; i >= left; i--)
                {
                    res.push_back(matrix[down][i]);
                }
                --down;
            }
            else {
                for(int i = down; i >= up; i--)
                {
                    res.push_back(matrix[i][left]);
                }
                ++left;
            }

            if (up > down || left > right) break;
            direction = (direction + 1) % 4;
        }
        return res;
    }
};

/*
 * @lc app=leetcode id=53 lang=cpp
 *
 * [53] Maximum Subarray
 *
 * https://leetcode.com/problems/maximum-subarray/description/
 *
 * algorithms
 * Medium (51.36%)
 * Likes:    34861
 * Dislikes: 1476
 * Total Accepted:    4.5M
 * Total Submissions: 8.7M
 * Testcase Example:  '[-2,1,-3,4,-1,2,1,-5,4]'
 *
 * Given an integer array nums, find the subarray with the largest sum, and
 * return its sum.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * Output: 6
 * Explanation: The subarray [4,-1,2,1] has the largest sum 6.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1]
 * Output: 1
 * Explanation: The subarray [1] has the largest sum 1.
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [5,4,-1,7,8]
 * Output: 23
 * Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 10^5
 * -10^4 <= nums[i] <= 10^4
 *
 *
 *
 * Follow up: If you have figured out the O(n) solution, try coding another
 * solution using the divide and conquer approach, which is more subtle.
 *
 */

// @lc code=start
class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int curSum = 0;
        int maxSum = INT_MIN;
        for (int num : nums)
        {
            curSum = max(num, curSum + num);
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};
// @lc code=end

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1;
        double half = myPow(x, n / 2);
        if(n % 2 == 0) return half * half;
        // 如果不是偶數的話
        return n > 0 ? half * half * x : half * half / x;
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> m;

        for(auto& s : strs)
        {
            vector<int> freq(26);
            for(auto& c : s) ++freq[c - 'a'];

            string t;
            for(int i = 0; i < 26; ++i)
            {
                if (!freq[i]) continue;
                t += string(1, i + 'a');
                t += to_string(freq[i]);
            }
            m[t].push_back(s);
        }

        vector<vector<string>> res;
        for(auto& a : m) res.push_back(a.second);
        return res;
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        for(int i = 0; i < n; ++i)
        {
            for(int j = i; j < n; ++j)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i = 0; i < n; i++)
        {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int start)
    {
        if (start == nums.size())
        {
            res.push_back(nums); return;
        }

        for (int i = start; i < nums.size(); ++i)
        {
            swap(nums[i], nums[start]);
            backtracking(nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
};