class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string res = "";
        for (auto& a : strs) {
            // 轉成size/字串size/字串size/字串
            // ["Hello","World"] -> 5/Hello5/World
            res.append(to_string(a.size())).append("/").append(a);
        }
        return res;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> res;
        int i = 0;
        while (i < s.size()) {
            // 找到分隔號的位置
            auto found = s.find("/", i);

            // 得到字串長度
            int len = stoi(s.substr(i, found - i));

            // 將字串推到 array
            res.push_back(s.substr(found + 1, len));

            // 下一根指針
            i = found + len + 1;
        }
        return res;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

class Solution {
public:
    int missingNumber(vector<int>& nums)
    {
        int n = nums.size();
        for(int i = 0; i < nums.size(); i++)
        {
            n += i - nums[i];
        }
        return n;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges)
    {
        vector<vector<int>> graph(n, vector<int>());
        for (auto& edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        unordered_set<int> seen;
        return dfs(graph, seen, 0, -1) && seen.size() == n;
    }

    bool dfs(vector<vector<int>>& graph, unordered_set<int>& seen, int node, int parent)
    {
        if (seen.count(node)) return false;

        seen.insert(node);

        for(int nei : graph[node])
        {
            if (parent != nei)
            {
                if (!dfs(graph, seen, nei, node))
                    return false;
            }
        }
        return true;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        dfs(root, "", res);
        return res;
    }

    void dfs(TreeNode* root, string out, vector<string>& res) {
        if(!root->left && !root->right) {
            res.push_back(out + to_string(root->val));
        }
        if(root->left) {
            dfs(root->left, out + to_string(root->val) + "->", res);
        }
        if(root->right) {
            dfs(root->right, out + to_string(root->val) + "->", res);
        }
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        // base case
        if(!root) return res;

        // 如果沒有左右子節點，則返回 root
        if(!root->left && !root->right) {
            return {to_string(root->val)};
        }

        // 找左側
        for(auto s : binaryTreePaths(root->left)) {
            res.push_back(to_string(root->val) + "->" + s);
        }

        // 找右側
        for(auto s : binaryTreePaths(root->right)) {
            res.push_back(to_string(root->val) + "->" + s);
        }

        return res;
    }
};

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();

        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> minHeap;

        // #0: minHeap = [30];
        // #1: minHeap = [10, 30];
        // #2: minHeap = [10, 20];
        for (auto& interval : intervals) {
            if (!minHeap.empty() && interval[0] >= minHeap.top()) {
                minHeap.pop();
            }
            minHeap.push(interval[1]);
        }
        return minHeap.size();
    }
};

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n == 0) return true;
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < n - 1; i++) {
            // 如果目前區間的 endtime 比下一個區間的 start time 大的話
            // 代表有 overlap
            if (intervals[i].back() > intervals[i + 1].front())
                return false;
        }
        return true;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t)
    {
        if (s.size() != t.size()) return false;

        unordered_map<char, int> m;

        for(auto& c : s) ++m[c];

        for (auto& c : t)
        {
            if (m.count(c))
            {
                --m[c];
                if (!m[c]) m.erase(c);
            }
        }
        return !m.size();
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<int> res;
        deque<int> q;

        for (int i = 0; i < n; ++i)
        {
            // 因為滑動視窗會向前移動
            // 當 q.front() 的元素離開視窗的時候
            // 1 [3  -1  -3]
            // ^          ^
            //   <- k ->  i
            if (!q.empty() && q.front() + k == i)
            {
                q.pop_front();
            }

            // 當發現 deque 尾端的元素比目前的 nums[i] 小的時候
            // pop 掉，因為不可能成為最大值
            // 所以 deque 裡面會存有潛力成為最大值數字的 index
            while (!q.empty() && nums[q.back()] < nums[i])
            {
                q.pop_back();
            }

            // 將 index push 到 queue
            q.push_back(i);

            // 當發現 i + 1 >= k 的時候
            // 代表滑動視窗的大小 k 已經形成
            // 則將最大值 nums[q.front()] 推到 res
            if (i + 1 >= k)
            {
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        vector<int> res;

        // 預設由大排到小
        priority_queue<pair<int, int>> q;

        for (int i = 0; i < nums.size(); ++i)
        {
            while (!q.empty() && q.top().second <= i - k)
            {
                q.pop();
            }

            // {存數字, 存 index}
            q.push({nums[i], i});

            // 如果滑動視窗形成
            // 將最大值 push 到 res
            if (i >= k - 1)
            {
                res.push_back(q.top().first);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize a vector to store the products of elements to the left of each index
        // Initialize a vector to store the products of elements to the right of each index
        // Initialize a vector to store the final result

        // Compute the products of all elements to the left of each index
        for ()
        {
            // Each element in arr1[i+1] is the product of all elements before nums[i+1]
        }

        // Compute the products of all elements to the right of each index
        for ()
        {
            // Each element in arr2[i-1] is the product of all elements after nums[i-1]
        }

        // Compute the final result by multiplying the corresponding elements of arr1 and arr2
        for ()
        {
            // The product of all elements except nums[i] is arr1[i] * arr2[i]
        }
        // Return the result vector
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        vector<int> res(n);

        for (int i = 0; i < n - 1; ++i)
        {
            left[i + 1] = left[i] * nums[i];
        }

        for (int i = n - 1; i > 0; --i)
        {
            right[i - 1] = right[i] * nums[i];
        }

        for (int i = 0; i < n; ++i)
        {
            res[i] = left[i] * right[i];
        }
        return res;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize the result array with 1s, as we will be using multiplication.

        // First pass: calculate the product of all elements to the left of each index.
        for ()
        {
            // res[i] will be the product of all elements to the left of i.
        }

        // Variable to store the product of all elements to the right of the current index.
        // Second pass: calculate the product of all elements to the right of each index and
        // multiply it with the product from the first pass.
        for ()
        {
            // Multiply with the product of elements to the right.
            // Update the right product for the next iteration (one index to the left).
        }
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> res(n, 1);

        for (int i = 1; i < n; ++i)
        {
            res[i] = nums[i - 1] * res[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; --i)
        {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};