Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true;
            if (tx > ty) {
                tx -= ty;
            } else {
                ty -= tx;
            }
        }
        return false;
    }
};

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

class Solution {
public:
    bool binarySearch(vector<vector<int>>& matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].size() - 1 : matrix.size() - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) {
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else {
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int shorterDim = min(matrix.size(), matrix[0].size());
        for (int i = 0; i < shorterDim; i++) {
            if (binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
};

Input: prices = [7,1,5,3,6,4] Output: 7
Explanation:
Купить на 2-й день (цена = 1), продать на 3-й (цена = 5), прибыль = 4
Купить на 4-й день (цена = 3), продать на 5-й (цена = 6), прибыль = 3
Итоговая прибыль = 4 + 3 = 7

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;

        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
            valley = prices[i];

            while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
            peak = prices[i];

            maxprofit += peak - valley;
        }

        return maxprofit;
    }
};

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

class Solution {
public:
    bool winnerSquareGame(int n) {
        unordered_map<int, bool> cache;
        cache[0] = false;
        return dfs(cache, n);
    }

    bool dfs(unordered_map<int, bool>& cache, int remain) {
        if (cache.find(remain) != cache.end()) {
            return cache[remain];
        }
        int sqrt_root = (int) sqrt(remain);
        for (int i = 1; i <= sqrt_root; ++i) {
            if (!dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
};

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        int end = -1, end2 = 0, res = 0;
        for (const auto& clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
};

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, result = 0;
        vector<int> modGroups(k);
        modGroups[0] = 1;

        for (int num : nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
};

Input: nums = [1,-2,3,-2]
Output: 3

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int kadane(vector<int>& arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.size(); ++i) {
                currentSum = max(arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        for (int& num : nums) num = -num;
        int minKadane = kadane(nums);

        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
};

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int deepestSum = 0, depth = 0, currDepth;
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 0});

        while (!stack.empty()) {
            auto [node, currDepth] = stack.top();
            stack.pop();

            if (!node->left && !node->right) {
                if (depth < currDepth) {
                    deepestSum = node->val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node->val;
                }
            } else {
                if (node->right) {
                    stack.push({node->right, currDepth + 1});
                }
                if (node->left) {
                    stack.push({node->left, currDepth + 1});
                }
            }
        }
        return deepestSum;
    }
};

Input: s = "hello"
Output: "holle"

class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            if (vowels.find(s[left]) == vowels.end()) {
                left++;
            } else if (vowels.find(s[right]) == vowels.end()) {
                right--;
            } else {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

Input: arr = [1,2]
Output: 2

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

private:
    int atMost(vector<int>& nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
};

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

class Solution {
private:
    static constexpr int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    int longestIncreasingPath(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        vector<vector<int>> matrix(m + 2, vector<int>(n + 2));
        vector<vector<int>> outdegree(m + 2, vector<int>(n + 2));

        for (int i = 0; i < m; ++i) {
            copy(grid[i].begin(), grid[i].end(), matrix[i + 1].begin() + 1);
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (auto& d : dir) {
                    if (matrix[i][j] < matrix[i + d[0]][j + d[1]]) {
                        outdegree[i][j]++;
                    }
                }
            }
        }

        vector<pair<int, int>> leaves;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (outdegree[i][j] == 0) leaves.emplace_back(i, j);
            }
        }

        int height = 0;
        while (!leaves.empty()) {
            ++height;
            vector<pair<int, int>> newLeaves;
            for (auto& node : leaves) {
                for (auto& d : dir) {
                    int x = node.first + d[0], y = node.second + d[1];
                    if (matrix[node.first][node.second] > matrix[x][y]) {
                        if (--outdegree[x][y] == 0) {
                            newLeaves.emplace_back(x, y);
                        }
                    }
                }
            }
            leaves.swap(newLeaves);
        }

        return height;
    }
};

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxNum = nums[0];
        for (int num : nums) maxNum = max(maxNum, num);
        int L = 32 - __builtin_clz(maxNum);

        int maxXor = 0, currXor;
        unordered_set<int> prefixes;
        for (int i = L - 1; i >= 0; --i) {
            maxXor <<= 1;
            currXor = maxXor | 1;
            prefixes.clear();
            for (int num : nums) prefixes.insert(num >> i);
            for (int p : prefixes) {
                if (prefixes.count(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
};

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

class Solution {
public:
    string getSmallestString(int n, int k) {
        vector<char> result(n, 'a');
        
        for (int position = 0; position < n; ++position) {
            int positionsLeft = (n - position - 1);
            if (k > positionsLeft * 26) {
                int add = k - (positionsLeft * 26);
                result[position] = 'a' + add - 1;
                k -= add;
            } else {
                k -= 1;
            }
        }
        
        return string(result.begin(), result.end());
    }
};

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        long ans = LONG_MAX;
        int minval = INT_MAX;
        int maxval = INT_MIN;
        for (int num : nums) {
            minval = min(minval, num);
            maxval = max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            for (int num : nums) {
                sum += abs(num - i);
            }
            ans = min(ans, sum);
        }
        return (int) ans;
    }
};

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]

class Solution {
private:
    vector<string> answer;
    string digits;
    long long target;

    void recurse(int index, long long prevOperand, long long currentOperand, long long value, vector<string>& ops) {
        if (index == digits.size()) {
            if (value == target && currentOperand == 0) {
                string expression = accumulate(ops.begin(), ops.end(), string(""));
                answer.push_back(expression);
            }
            return;
        }

        currentOperand = currentOperand * 10 + (digits[index] - '0');
        string currentValRep = to_string(currentOperand);

        if (currentOperand > 0) {
            recurse(index + 1, prevOperand, currentOperand, value, ops);
        }

        // +
        ops.push_back("+");
        ops.push_back(currentValRep);
        recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.pop_back(); ops.pop_back();

        if (!ops.empty()) {
            // -
            ops.push_back("-");
            ops.push_back(currentValRep);
            recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
            ops.pop_back(); ops.pop_back();

            // *
            ops.push_back("*");
            ops.push_back(currentValRep);
            recurse(index + 1, prevOperand * currentOperand, 0, value - prevOperand + (prevOperand * currentOperand), ops);
            ops.pop_back(); ops.pop_back();
        }
    }

public:
    vector<string> addOperators(string num, int target) {
        if (num.empty()) return {};
        this->digits = num;
        this->target = target;
        vector<string> ops;
        recurse(0, 0, 0, 0, ops);
        return answer;
    }
};

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        if (!root) return nullptr;

        TreeNode* vineHead = new TreeNode(0);
        vineHead->right = root;
        TreeNode* current = vineHead;

        while (current->right) {
            if (current->right->left) {
                rightRotate(current, current->right);
            } else {
                current = current->right;
            }
        }

        int nodeCount = 0;
        current = vineHead->right;
        while (current) {
            ++nodeCount;
            current = current->right;
        }

        int m = pow(2, floor(log2(nodeCount + 1))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode* balancedRoot = vineHead->right;
        delete vineHead;
        return balancedRoot;
    }

private:
    void rightRotate(TreeNode* parent, TreeNode* node) {
        TreeNode* tmp = node->left;
        node->left = tmp->right;
        tmp->right = node;
        parent->right = tmp;
    }

    void leftRotate(TreeNode* parent, TreeNode* node) {
        TreeNode* tmp = node->right;
        node->right = tmp->left;
        tmp->left = node;
        parent->right = tmp;
    }

    void makeRotations(TreeNode* vineHead, int count) {
        TreeNode* current = vineHead;
        for (int i = 0; i < count; ++i) {
            TreeNode* tmp = current->right;
            leftRotate(current, tmp);
            current = current->right;
        }
    }
};

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

class Solution {
public:
    int N;
    vector<vector<int>> pairs;

    int minSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs.resize(N, vector<int>(2));
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return min(ans1, ans2);
    }
};