class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        // 計算子數列能不能被 k 整除
        // sum[i : j] 能被 k 整除的條件就是
        // prefixSum[i] 和 prefixSum[j - 1] 除以 k 的餘數相同

     int res = 0, sum = 0;

        // 保存 prefixSum 除以 k 的餘數出現多少次
        unordered_map<int, int> m{{0, 1}};

        for (int num : nums)
        {
            // 累加 sum
            // 加上 k 的原因是確保結果為正整數
            // 沒有加上 k，有可能出現負數的情況
         sum = (sum + num % k + k) % k;

            // 加上相同餘數對應的頻率
         res += m[sum];

            // 餘數出現的頻率 + 1
         ++m[sum];
        }
        return res;
    }
};

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums)
    {
        int moves = 0;

        int n = nums.size();

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

        // nums = [1, 1, 2, 2, 3, 7]
        for (int i = 1; i < n; ++i)
        {
            // 如果發現目前的數字小於等於前一個數字
            if (nums[i - 1] >= nums[i])
            {

                // 要加的數字等於兩者之差 + 1
                int increment = nums[i - 1] - nums[i] + 1;
                moves += increment;
                // 更新目前的數字
                nums[i] = nums[i - 1] + 1;
            }
        }
        return moves;
    }
};

/*
 * @lc app=leetcode id=944 lang=cpp
 *
 * [944] Delete Columns to Make Sorted
 *
 * https://leetcode.com/problems/delete-columns-to-make-sorted/description/
 *
 * algorithms
 * Easy (74.65%)
 * Likes:    1740
 * Dislikes: 2898
 * Total Accepted:    205.4K
 * Total Submissions: 274.8K
 * Testcase Example:  '["cba","daf","ghi"]'
 *
 * You are given an array of n strings strs, all of the same length.
 *
 * The strings can be arranged such that there is one on each line, making a
 * grid.
 *
 *
 * For example, strs = ["abc", "bce", "cae"] can be arranged as follows:
 *
 *
 *
 * abc
 * bce
 * cae
 *
 *
 * You want to delete the columns that are not sorted lexicographically. In the
 * above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e')
 * are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete
 * column 1.
 *
 * Return the number of columns that you will delete.
 *
 *
 * Example 1:
 *
 *
 * Input: strs = ["cba","daf","ghi"]
 * Output: 1
 * Explanation: The grid looks as follows:
 * ⁠ cba
 * ⁠ daf
 * ⁠ ghi
 * Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete
 * 1 column.
 *
 *
 * Example 2:
 *
 *
 * Input: strs = ["a","b"]
 * Output: 0
 * Explanation: The grid looks as follows:
 * ⁠ a
 * ⁠ b
 * Column 0 is the only column and is sorted, so you will not delete any
 * columns.
 *
 *
 * Example 3:
 *
 *
 * Input: strs = ["zyx","wvu","tsr"]
 * Output: 3
 * Explanation: The grid looks as follows:
 * ⁠ zyx
 * ⁠ wvu
 * ⁠ tsr
 * All 3 columns are not sorted, so you will delete all 3.
 *
 *
 *
 * Constraints:
 *
 *
 * n == strs.length
 * 1 <= n <= 100
 * 1 <= strs[i].length <= 1000
 * strs[i] consists of lowercase English letters.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int m = strs.size(), n = strs[0].size();
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    cnt++; break;
                }
            }
        }
        return cnt;
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=931 lang=cpp
 *
 * [931] Minimum Falling Path Sum
 *
 * https://leetcode.com/problems/minimum-falling-path-sum/description/
 *
 * algorithms
 * Medium (62.52%)
 * Likes:    6578
 * Dislikes: 165
 * Total Accepted:    521.8K
 * Total Submissions: 841.4K
 * Testcase Example:  '[[2,1,3],[6,5,4],[7,8,9]]'
 *
 * Given an n x n array of integers matrix, return the minimum sum of any
 * falling path through matrix.
 *
 * A falling path starts at any element in the first row and chooses the
 * element in the next row that is either directly below or diagonally
 * left/right. Specifically, the next element from position (row, col) will be
 * (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
 *
 *
 * Example 1:
 *
 *
 * Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
 * Output: 13
 * Explanation: There are two falling paths with a minimum sum as shown.
 *
 *
 * Example 2:
 *
 *
 * Input: matrix = [[-19,57],[-40,-5]]
 * Output: -59
 * Explanation: The falling path with a minimum sum is shown.
 *
 *
 *
 * Constraints:
 *
 *
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 100
 * -100 <= matrix[i][j] <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        if (n == 1) return matrix[0][0];

        int res = INT_MAX;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int previous = matrix[i - 1][j];
                if (j > 0)
                {
                    previous = min(previous, matrix[i - 1][j - 1]);
                }
                if (j < n - 1)
                {
                    previous = min(previous, matrix[i - 1][j + 1]);
                }
                matrix[i][j] += previous;
                if (i == n - 1)
                {
                    res = min(res, matrix[i][j]);
                }
            }
        }
        return res;
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=918 lang=cpp
 *
 * [918] Maximum Sum Circular Subarray
 *
 * https://leetcode.com/problems/maximum-sum-circular-subarray/description/
 *
 * algorithms
 * Medium (46.01%)
 * Likes:    6878
 * Dislikes: 320
 * Total Accepted:    319.7K
 * Total Submissions: 682K
 * Testcase Example:  '[1,-2,3,-2]'
 *
 * Given a circular integer array nums of length n, return the maximum possible
 * sum of a non-empty subarray of nums.
 *
 * A circular array means the end of the array connects to the beginning of the
 * array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the
 * previous element of nums[i] is nums[(i - 1 + n) % n].
 *
 * A subarray may only include each element of the fixed buffer nums at most
 * once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there
 * does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,-2,3,-2]
 * Output: 3
 * Explanation: Subarray [3] has maximum sum 3.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [5,-3,5]
 * Output: 10
 * Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [-3,-2,-3]
 * Output: -2
 * Explanation: Subarray [-2] has maximum sum -2.
 *
 *
 *
 * Constraints:
 *
 *
 * n == nums.length
 * 1 <= n <= 3 * 10^4
 * -3 * 10^4 <= nums[i] <= 3 * 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int curMax = 0, curMin = 0;
        int maxSum = nums[0], minSum = nums[0];
        int totalSum = 0;

        for(int num : nums) {
            curMax = max(curMax + num, num);
            maxSum = max(maxSum, curMax);

            curMin = min(curMin + num, num);
            minSum = min(minSum, curMin);

            totalSum += num;
        }
        if(totalSum == minSum) {
            return maxSum;
        }
        return max(maxSum, totalSum - minSum);
    }
};
// @lc code=end

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void merge(vector<int> &nums, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> l1(n1), l2(n2);
        for (int i = 0; i < n1; ++i) l1[i] = nums[left + i];

        for (int i = 0; i < n2; ++i) l2[i] = nums[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (l1[i] <= l2[j])
            {
                nums[k] = l1[i++];
            }
            else
            {
                nums[k] = l2[j++];
            }
            ++k;
        }

        while (i < n1)
        {
            nums[k] = l1[i];
            ++i; ++k;
        }

        while (j < n2)
        {
            nums[k] = l2[j];
            ++j; ++k;
        }
    }

    void mergeSort(vector<int> &nums, int left, int right)
    {
     if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
};

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return

        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int pointer = left;
        for (int i = left; i < right; ++i)
        {
            if (nums[i] <= pivot)
            {
                swap(nums[pointer++], nums[i]);
            }
        }
        swap(nums[pointer], nums[right]);
        return pointer;
    }
};

/**
 * 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:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills)
    {
        int coin5 = 0;
        int coin10 = 0;

        for (const auto& b : bills)
        {
            if (b == 5)
            {
                coin5++;
            }
            else if (b == 10)
            {
                if (coin5 > 0)
                {
                    coin5--;
                    coin10++;
                }
                else return false;
            }
            else if (b == 20)
            {
                if (coin10 > 0 && coin5 > 0)
                {
                    coin5--;
                    coin10--;
                }
                else if (coin5 >= 3)
                {
                    coin5 -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};