/*
 * @lc app=leetcode id=221 lang=cpp
 *
 * [221] Maximal Square
 *
 * https://leetcode.com/problems/maximal-square/description/
 *
 * algorithms
 * Medium (47.66%)
 * Likes:    10401
 * Dislikes: 237
 * Total Accepted:    759.3K
 * Total Submissions: 1.6M
 * Testcase Example:  '[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]'
 *
 * Given an m x n binary matrix filled with 0's and 1's, find the largest
 * square containing only 1's and return its area.
 *
 *
 * Example 1:
 *
 *
 * Input: matrix =
 * [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * Output: 4
 *
 *
 * Example 2:
 *
 *
 * Input: matrix = [["0","1"],["1","0"]]
 * Output: 1
 *
 *
 * Example 3:
 *
 *
 * Input: matrix = [["0"]]
 * Output: 0
 *
 *
 *
 * Constraints:
 *
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 300
 * matrix[i][j] is '0' or '1'.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int d = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                } else if (matrix[i][j] == '1') {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
                d = max(d, dp[i][j]);
            }
        }
        return d * d;
    }
};
// @lc code=end

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i > k && m[nums[i - k - 1]] < i - k + 1)
            {
                m.erase(nums[i - k - 1]);
            }

            if (m.count(nums[i])) return true;
            m[nums[i]] = i;
        }
        return false;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int, int> freq;
        for (auto num : nums) ++freq[num];
        for (auto [k, v] : freq)
        {
            if (v > 1) return true;
        }
        return false;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;

        for(auto& num : nums) pq.push(num);

        for(int i = 1; i < k; i++) {
            pq.pop();
        }
        return pq.top();
    }
};

/*
 * @lc app=leetcode id=213 lang=cpp
 *
 * [213] House Robber II
 *
 * https://leetcode.com/problems/house-robber-ii/description/
 *
 * algorithms
 * Medium (42.73%)
 * Likes:    10281
 * Dislikes: 169
 * Total Accepted:    937.1K
 * Total Submissions: 2.2M
 * Testcase Example:  '[2,3,2]'
 *
 * You are a professional robber planning to rob houses along a street. Each
 * house has a certain amount of money stashed. All houses at this place are
 * arranged in a circle. That means the first house is the neighbor of the last
 * one. Meanwhile, adjacent houses have a security system connected, and it
 * will automatically contact the police if two adjacent houses were broken
 * into on the same night.
 *
 * Given an integer array nums representing the amount of money of each house,
 * return the maximum amount of money you can rob tonight without alerting the
 * police.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [2,3,2]
 * Output: 3
 * Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money
 * = 2), because they are adjacent houses.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,2,3,1]
 * Output: 4
 * Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
 * Total amount you can rob = 1 + 3 = 4.
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [1,2,3]
 * Output: 3
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 1000
 *
 *
 */

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

        int excludeLast = robRange(nums, 0, n - 1);
        int excludeFirst = robRange(nums, 1, n);
        return max(excludeLast, excludeFirst);
    }
    int robRange(vector<int>& nums, int left, int right)
    {
        int robbed = 0, notRobbed = 0;
        for (int i = left; i < right; ++i)
        {
            int prevRobbed = robbed;
            robbed = max(robbed, nums[i] + notRobbed);
            notRobbed = prevRobbed;
        }
        return robbed;
    }
};
// @lc code=end

class TrieNode {
public:
    TrieNode* child[26];
    string str;
    TrieNode()
    {
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
        str = "";
    }
};

class Trie {
public:
    TrieNode* root;
    Trie()
    {
        root = new TrieNode();
    }

    void insert(const string& word)
    {
        TrieNode* node = root;
        for (char w : word)
        {
            if (!node->child[w - 'a'])
            {
                node->child[w - 'a'] = new TrieNode();
            }
            node = node->child[w - 'a'];
        }
        node->str = word;
    }
};

class Solution {
private:
    vector<string> res;

public:
    void backtracking(vector<vector<char>>& board, TrieNode* node, int i, int j)
    {
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] == '#' || !node->child[board[i][j] - 'a'])
        {
            return;
        }

        node = node->child[board[i][j] - 'a'];
        if (!node->str.empty())
        {
            res.push_back(node->str);
            node->str = "";
        }

        char temp = board[i][j];
        board[i][j] = '#';

        backtracking(board, node, i + 1, j);
        backtracking(board, node, i - 1, j);
        backtracking(board, node, i, j + 1);
        backtracking(board, node, i, j - 1);

        board[i][j] = temp;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words)
    {
        if (board.empty() || board[0].empty()) return {};

        Trie t;
        for (const string& word : words) t.insert(word);

        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                backtracking(board, t.root, i, j);
            }
        }
        return res;
    }
};

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord = false;
    TrieNode()
    {
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;
public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(string word)
    {
        TrieNode* node = root;
        for (auto w : word)
        {
            if (!node->child[w - 'a'])
            {
                node->child[w - 'a'] = new TrieNode();
            }
            node = node->child[w - 'a'];
        }
        node->isWord = true;
    }

    bool search(string word)
    {
        TrieNode* node = root;
        for (auto w : word)
        {
            if (!node->child[w - 'a']) return false;
            node = node->child[w - 'a'];
        }
        return node->isWord;
    }

    bool startsWith(string prefix)
    {
        TrieNode* node = root;
        for (auto p : prefix)
        {
            if (!node->child[p - 'a']) return false;
            node = node->child[p - 'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

/**
 * 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* reverseList(ListNode* head)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(cur)
        {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};

/**
 * 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* reverseList(ListNode* head)
    {
        if(!head || !head->next) return head;

        ListNode* prev = reverseList(head->next);
        // 1 -> 2 <- 3 <- 4 <- 5
        // ^ head

        head->next->next = head;
        head->next = NULL;
        return prev;
    }
};

class Solution {
public:
    bool isIsomorphic(string s, string t)
    {
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;

        int n = t.size();

        for (int i = 0; i < n; i++)
        {
            if (m1[s[i]] != m2[t[i]])
            {
                return false;
            }
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};