class Solution {
public:
    int minBitFlips(int start, int goal)
    {
        int n = start ^ goal;
        int cnt = 0;
        while (n)
        {
            n &= (n - 1);
            cnt++;
        }
        return cnt;
    }
};

/**
 * 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:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions)
    {
        // Map to store TreeNode pointers by their values
        // Set to keep track of all child nodes

        // Iterate over each description in the input
        for ()
        {
            // Parent node value
            // Child node value
            // Indicates if the child is a left child

            // If parent node is not already created, create it and store in nodeMap

            // If child node is not already created, create it and store in nodeMap

            // Attach the child to the appropriate side of the parent

            // Add the child value to the set of children
        }

        // Find and return the root node (a node that is not anyone's child)
        for ()
        {
            // If the value is not found in children set, it's the root
        }
        // If no root is found (though the problem guarantees there will be one), return nullptr
    }
};

/**
 * 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:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions)
    {
        // Map to store TreeNode pointers by their values
        unordered_map<int, TreeNode*> nodeMap;

        // Set to keep track of all child nodes
        unordered_set<int> children;

        // Iterate over each description in the input
        for (const auto& description : descriptions)
        {
            // Parent node value
            int parentValue = description[0];

            // Child node value
            int childValue = description[1];

            // Indicates if the child is a left child
            bool isLeft = description[2];

            // If parent node is not already created, create it and store in nodeMap
            if (!nodeMap.count(parentValue))
            {
                nodeMap[parentValue] = new TreeNode(parentValue);
            }

            // If child node is not already created, create it and store in nodeMap
            if (!nodeMap.count(childValue))
            {
                nodeMap[childValue] = new TreeNode(childValue);
            }

            // Attach the child to the appropriate side of the parent
            if (isLeft)
            {
                nodeMap[parentValue]->left = nodeMap[childValue];
            }
            else
            {
                nodeMap[parentValue]->right = nodeMap[childValue];
            }

            // Add the child value to the set of children
            children.insert(childValue);
        }

        // Find and return the root node (a node that is not anyone's child)
        for (auto& entry : nodeMap)
        {
            auto& value = entry.first;
            auto& node = entry.second;

            // If the value is not found in children set, it's the root
            if (!children.count(value))
            {
                return node;
            }
        }

        // If no root is found (though the problem guarantees there will be one), return nullptr
        return nullptr;
    }
};

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums)
    {
        vector<pair<int, int>> m;

        for (int i = 0; i < nums.size(); ++i)
        {
            string number = to_string(nums[i]);
            string formed = "";
            for (int j = 0; j < number.size(); ++j)
            {
                formed = formed + (to_string(mapping[number[j] - '0']));
            }
            int mappedValue = stoi(formed);
            m.push_back({mappedValue, i});
        }

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

        vector<int> res;

        for (auto pair : m)
        {
            res.push_back(nums[pair.second]);
        }
        return res;
    }
};

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        unordered_set<int> rowSet, colSet;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (rowSet.count(matrix[i][j]))
                {
                    return false;
                }
                else
                {
                    rowSet.insert(matrix[i][j]);
                }
                if (colSet.count(matrix[j][i]))
                {
                    return false;
                }
                else
                {
                    colSet.insert(matrix[j][i]);
                }
            }
            rowSet.clear();
            colSet.clear();
        }
        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:
    string getDirections(TreeNode* root, int startValue, int destValue)
    {
        // Strings to store paths from root to startValue and destValue
        // Find paths from root to startValue and destValue

        // Initialize directions string
        // Length of common path

        // Find the length of the common path prefix
        while ()
        {
        }

        // Append 'U' (up) moves to go from startValue to the common ancestor
        for ()
        {
        }

        // Append moves to go from the common ancestor to destValue
        for ()
        {
        }
        // Return the directions
    }

    // Function to find the path from root to target value and update the path string
    bool findPath()
    {
        // Base case: If root is null, return false
        // If the current node's value matches the target, return true indicating target found

        // Append 'L' (left) and recursively search in the left subtree
        // Backtrack by removing the last character

        // Append 'R' (right) and recursively search in the right subtree
        // Backtrack by removing the last character

        // Return false if target is not found in the subtree
    }
};

/**
 * 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:
    string getDirections(TreeNode* root, int startValue, int destValue)
    {
        string startPath, destPath;
        findPath(root, startValue, startPath);
        findPath(root, destValue, destPath);

        string directions;
        int commonPath = 0;

        while (commonPath < startPath.size() && commonPath < destPath.size() && startPath[commonPath] == destPath[commonPath])
        {
            commonPath++;
        }

        for (int i = commonPath; i < startPath.size(); ++i)
        {
            directions += "U";
        }

        for (int i = commonPath; i < destPath.size(); ++i)
        {
            directions += destPath[i];
        }
        return directions;
    }

    bool findPath(TreeNode* root, int target, string& path)
    {
        if (!root) return false;
        if (root->val == target) return true;

        path += 'L';
        if (findPath(root->left, target, path)) return true;
        path.pop_back();

        path += 'R';
        if (findPath(root->right, target, path)) return true;
        path.pop_back();

        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head)
    {
        vector<int> res = {-1, -1};
        int minDist = INT_MAX;

        ListNode* prev = head;
        ListNode* cur = head->next;

        int i = 1;
        int last = 0;
        int first = 0;

        while (cur->next)
        {
            // if (localMinimum || localMaximum)
            if ((cur->val < prev->val && cur->val < cur->next->val) || (cur->val > prev->val && cur->val > cur->next->val))
            {
                // 如果這是第一個 critial point，則將 last 和 first 都設為當前的 index i。
                if (last == 0)
                {
                    last = i;
                    first = i;
                }
                else
                {
                    minDist = min(minDist, i - last);
                    // 更新 last critial point
                    last = i;
                }
            }
            i++;
            // update the pointer
            prev = cur;
            cur = cur->next;
        }

        if (minDist != INT_MAX)
        {
            // maxDist 即為 last - first
            int maxDist = last - first;
            res = {minDist, maxDist};
        }
        return res;
    }
};

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k)
    {
        unordered_map<string, int> m;
        for (const auto& str : arr) m[str]++;
        for (const auto& num : arr)
        {
            if (m[num] == 1 && !--k) return num;
        }
        return "";
    }
};

class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students)
    {
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());

        int n = seats.size();
        int moves = 0;
        for (int i = 0; i < n; ++i)
        {
            moves += abs(seats[i] - students[i]);
        }
        return moves;
    }
};

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