## 2966. Divide Array Into Arrays With Max Difference (2024/02/01)

### Topic
Array

### Solution
If we interpret the problem properly, it should be an easy problem. While the _max_ in the title is a bit misleading.
Given a sorted array, if three consecutive number cannot fit in the criteria, then it is not possible to find a better choice.

### Code

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        for (int i = 0; i < nums.size(); i += 3) {
            if (nums[i+2]-nums[i] > k || nums[i+1]-nums[i] > k) {
                return {};
            }
            result.push_back({nums[i], nums[i+1], nums[i+2]});
        }
        return result;
    }
};

## 1291. Sequential Digits (2024/02/02)

### Topic
Enumeration

### Solution
The code below checks where to start. In fact, the number of possible values is quite small. A brute force enumeration and comparison should perform better.

### Code

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        if (high > 123456789) {
            high = 123456789;
        }
        vector<int> result;
        auto num_digits = 2;
        auto div10 = 10;
        while (low % div10 > 9) {
            div10 *= 10;
            num_digits++;
        }
        auto first_digit = low / div10;
        auto seq = 0;
        while (seq <= high) {
            if (first_digit + num_digits - 1 > 9) {
                num_digits++;
                first_digit = 1;
            }
            if (num_digits > 9) {
                return result;
            }
            seq = first_digit;
            for (int i = 1; i < num_digits; i++) {
                seq *= 10;
                seq += (first_digit + i);
            }
            if (seq >= low && seq <= high) {
                result.push_back(seq);
            }
            first_digit++;
        }
        return result;
    }
};

## 1043. Partition Array for Maximum Sum (2024/02/03)

### Topic
Dynamic programming

### Solution
The concept is simple, but it's very easy to get stuck by boundary conditions.
#### Recursive relationship
_A(i)_: the input array
_D(i+1)_: the result given the last element is i (i.e. number of elements from 0 to i)
_D(i+1)_ = MAX(_D(i-j)+j*MAX(A(i),...,A(i-j))_), for j from 1 to k
Calculate _D(n)_

### Code

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        auto len = arr.size();
        vector<int> dp(len+1, 0);
        dp[1] = arr[0];
        for (int i = 1; i <= len; i++) {
            auto local_max = 0;
            auto local_arr_max = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j < 0) {
                    break;
                }
                local_arr_max = max(local_arr_max, arr[i-j]);
                local_max = max(local_max, dp[i-j] + local_arr_max * j);
            }
            dp[i] = local_max;
        }
        return dp[len];

## 387. First Unique Character in a String (2024/02/06)

### Topic
Hash table, Queue

### Solution
1. Iterate through the input string and store the appearance times and queue their order at the same time.
2. Pop the queue and check if the character is unique.

#### Better solution
Actually, the queue is not necessary. We can reiterate the input string again to retain the order.

### Code

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> appear_times;
        queue<char> q;
        for (auto c : s) {
            appear_times[c]++;
            q.push(c);
        }
        auto index = 0;
        while (!q.empty()) {
            auto val = q.front();
            if (appear_times[val] == 1) {
                return index;
            }
            q.pop();
            index++;
        }
        return -1;
    }
};

## 49. Group Anagrams (2024/02/06)

### Topic
Hash table

### Solution
1. Create the hash map for each string in the input array.
2. Compare the hashed map one by one and group the same together.

#### Better solution
Instead of creating the hash maps and comparing, we can first sort the strings and compare whether the strings are equal. The latter method is faster while comparing.

### Code

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<array<int, 26>> hashed(strs.size(), {0});
        vector<bool> remains(strs.size(), true);
        vector<vector<string>> result;
        for (int i = 0; i < strs.size(); i++) {
            for (auto c : strs[i]) {
                hashed[i][c-97]++;
            }
        }
        for (int i = 0; i < strs.size(); i++) {
            if (!remains[i]) {
                continue;   
            }
            remains[i] = false;
            vector<string> collection = {strs[i]};
            result.push_back(collection);
            for (int j = i+1; j < strs.size(); j++) {
                if (!remains[j]) {
                    continue;
                }
                if (hashed[i] == hashed[j]) {
                    remains[j] = false;
                    result.back().push_back(strs[j]);
                }
            }
        }
        return result;
    }
};

## 451. Sort Characters By Frequency (2024/02/07)

### Topic
Hash table, Sorting

### Solution
1. Count the frequency of each character.
2. Sort the frequencies in decreasing order and keep a tag of the corresponding character.

#### Better solution
Increase the array to length 128 to avoid the `if` statements while counting frequencies.

### Code

class Solution {
public:
    string frequencySort(string s) {
        array<pair<int, char>, 62> counter;
        for (int i = 0; i < 62; i++) {
            if (i < 10) {
                counter[i].second = i + 48;
            } else if (i < 36) {
                counter[i].second = i + 55;
            } else {
                counter[i].second = i + 61;
            }
        }
        for (auto c : s) {
            if (c < 58) {
                counter[c-48].first++;
            } else if (c < 91) {
                counter[c-65+10].first++;
            } else {
                counter[c-97+36].first++;
            }
        }
        sort(counter.begin(), counter.end(), [](pair<int, char> a, pair<int, char> b) {
            return a.first > b.first;
        });
        string out = "";
        for (auto ele : counter) {
            if (ele.first == 0) {
                break;
            }
            out += string(ele.first, ele.second);
        }
        return out;
    }
};

## 300. Longest Increasing Subsequence (2024/02/09)

### Topic
Dynamic programming

### Solution
_For a new integer to be eligible to be added to an exisiting divisible subset, that new integer only needs to be divisible by the largest integer in the exisiting divisible subset._

### Code

## 647. Palindromic Substrings (2024/02/10)

### Topic
Dynamic programming

### Solution
1. Every single character is a palindrome.
2. Within range, expand from to the left and right by 1 character at a time. So we need 2 pointers, left, right. When _left=right_ increase the counter by 1. If _left!=right_, break the loop.
3. When you expand to check if a string is palindrome you need to consider two cases based on the amount (even or odd) of the word. For the case of . Ok we need to do the same now but having right initialized as left +1, or putting it in other words, right is initialized to the next char of the string. Repeat the same approach as before adding to the same counter and you will reach 6, the final result.

### Code

class Solution {
public:
    int countSubstrings(string s) {
        auto len = s.length();
        auto result = len;
        for (int i = 0; i < len; i++) {
            auto len_to_extend = min(i, (int)len - i);
            if (len_to_extend == 0) {
                continue;
            }
            for (int j = 1; j <= len_to_extend; j++) {
                if (s[i+j] == s[i-j]) {
                    result++;
                } else {
                    break;
                }
            }
        }
        for (int i = 0; i < len; i++) {
            if (i+1 < len && s[i] != s[i+1]) {
                continue;
            } else if (i+1 < len) {
                result++;
            }
            auto len_to_extend = min(i, (int)len - i - 1);
            if (len_to_extend == 0) {
                continue;
            }
            for (int j = 1; j <= len_to_extend; j++) {
                if (s[i+1+j] == s[i-j]) {
                    result++;
                } else {
                    break;
                }
            }
        }
        return result;
    }
};

## 169. Majority Element (2024/02/12)

### Topic
Array, Algorithm

### Solution

#### Key
_Removing a pair of one major element and one non-major element does not effect the outcome._
[Boyer-Moore voting algorithm](https://www.topcoder.com/thrive/articles/boyer-moore-majority-vote-algorithm)
1. Iterate throught the supplied array and assume the first element is the majority. If the incoming element matches the current majority, upvotes, and vice versa.
2. While the votes decrease to 0, select the current iterated number as majority.
3. (Optional) If majority is not guaranteed existed, loop again to check whether the current majority is the true majority. In this case, we do not need this step.

### Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        int current = nums[0];
        int current_vote = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == current) {
                current_vote++;
            } else {
                current_vote--;
            }
            if (current_vote == 0) {
                current = nums[i];
                current_vote = 1;
            }
        }
        return current;
    }
};

## 2149. Rearrange Array Elements by Sign (2024/02/14)

### Topic
Array

### Solution
1. Sort the input array into a positive number array and a negative number array with the order preserved.
2. Construct the output array by taking a positive number then a negative number repeatedly.

#### Better solution
We do not have to actually split the input array into two subarrays. However, inserting them to odd or even slots of the output array.

### Code

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> positive;
        vector<int> negative;
        vector<int> result;
        for (auto num : nums) {
            if (num > 0) {
                positive.push_back(num);
            } else {
                negative.push_back(num);
            }
        }
        for (int i = 0; i < nums.size()/2; i++) {
            result.push_back(positive[i]);
            result.push_back(negative[i]);
        }
        return result;
    }
};

## 2971. Find Polygon With the Largest Perimeter (2024/02/15)

### Topic
Array, Greedy

### Solution
1. Sort the array.
2. Assume all the edges can be used. Sum the elements from _least_ to _largets-1_, and we can get the _perimeter-longest side_ and _the longest side_.
3. If _2._ forms a polygon, the return their sum. While not, try to use the _largest-1_ side as the longest side, etc.

#### Note
Also can be done in incremental way.

### Code

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        if (nums.size() < 3) {
            return -1;
        }
        sort(nums.begin(), nums.end());
        long long other_sides = 0;
        int greatest_side = nums[nums.size()-1];
        for (int i = 0; i < nums.size() - 1; i++) {
            other_sides += nums[i];
        }
        int index = nums.size() - 2;
        while (other_sides <= greatest_side && index > 0) {
            other_sides -= nums[index];
            greatest_side = nums[index];
            index--;
        }
        if (index > 0) {
            return other_sides + greatest_side;
        }
        return -1;
    }
};

## 1481. Least Number of Unique Integers after K Removals (2024/02/16)

### Topic
Sorting, Hash Table

### Solution
1. Use a hash table to store the frequencies.
2. Transform the hash table into an array an sort it (keeping the frequencies is enough).
3. Remove first _k_ appearance records, and the remaining non-zero records is the answer.

#### Better solution
1. Sort the original array first.
2. Push the fequencies into a heap which is ordered.
3. The same as **3** in the previous section.

### Code

class Solution {

public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> counter;
        for (auto num : arr) {
            counter[num]++;
        }

        vector<int> counter_map(counter.size());
        transform(counter.begin(), counter.end(), counter_map.begin(), [](auto pair){return pair.second;});
        sort(counter_map.begin(), counter_map.end());

        int index = 0;
        auto result = counter_map.size();
        while (k > 0) {
            if (k >= counter_map[index]) {
                k -= counter_map[index];
                counter_map[index] = 0;
                result--;
            } else {
                break;
            }
            index++;
        }
        return result;
    }
};

## 1642. Furthest Building You Can Reach (2024/02/17)

### Topic
Greedy, Heap

### Solution
Let
_r = number of ladders_
_b = number of bricks_
_c = the counts of total jumps_

1. Use a min heap to keep track of the largest r jumps.
2. If the incoming jumps is negative, continue to the next jump and increment _c_.
3. If the incoming jump is larger than the least largest jump in heap, use brick for the popped jump and use ladder for the pushed jump; increment _c_.
4. If the incoming jump is smaller than the least largest jump, use bricks; and increment _c_.
5. When the bricks and ladders are run out, return _c_.

### Code

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, std::vector<int>, std::greater<int>> largest_r;
        int brick_used = 0;
        int curr_building = 0;
        for (curr_building = 1; curr_building < heights.size(); curr_building++) {
            auto diff = heights[curr_building] - heights[curr_building-1];
            if (diff <= 0) {
                continue;
            }
            if (largest_r.size() < ladders) {
                largest_r.push(diff);
            } else if (!largest_r.empty() && largest_r.top() < diff) {
                brick_used += largest_r.top();
                largest_r.pop();
                largest_r.push(diff);
            } else {
                brick_used += diff;
            }
            if (brick_used > bricks) {
                break;
            }
        }
        return --curr_building;
    }
};

## 2402. Meeting Rooms III (2024/02/20)

### Topic
Heap, Sorting

### Solution
1. Prepare empty room min heap.
2. Sort the meetings according to start time.
3. The second heap keeps track of the end times of all the meetings that are happening and the room that they are in.
4. Keep track of the number of times each room is used in an array.
5. With each meeting, check if there are any free rooms (find out free rooms when _new start time > old end times_). If there are, then use the room with the smallest number. Otherwise, assign the meeting to the room whose meeting will end the soonest.
6. If a meeting is postponed, modify its end time when pushing to the heap.

**Note**: the meetings can be postponed so that the start time exceeds the range of _int_.

### Code

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        vector<int> room_used(n, 0);
        priority_queue<int, vector<int>, greater<int>> free_rooms;
        for (int i = 0; i < n; i++) {
            free_rooms.push(i);
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> meeting_ends;
        sort(meetings.begin(), meetings.end(),
           [](const vector<int>& a, const vector<int>& b) {
                return a[0] < b[0];
        });
        for (auto meeting : meetings) {
            if (!meeting_ends.empty()) {
                auto end_top = meeting_ends.top();
                while (!meeting_ends.empty() && end_top.first <= meeting[0]) {
                    meeting_ends.pop();
                    free_rooms.push(end_top.second);
                    end_top = meeting_ends.top();
                }
            }
            if (!free_rooms.empty()) {
                auto room = free_rooms.top();
                free_rooms.pop();
                meeting_ends.push(make_pair(meeting[1], room));
                room_used[room]++;
            } else {
                long long m1 = meeting[1];
                auto end = meeting_ends.top();
                meeting_ends.pop();
                if (end.first > meeting[0]) {
                    auto dur = meeting[1] - meeting[0];
                    m1 = end.first + dur;
                }
                meeting_ends.push(make_pair(m1, end.second));
                room_used[end.second]++;
            }
        }
        int max_used = 0;
        int max_index = 0;
        for (int i = 0; i < n; i++) {
            if (room_used[i] > max_used) {
                max_index = i;
                max_used = room_used[i];
            }
        }
        return max_index;
    }
};

## 231. Power of Two (2024/02/19)

### Topic
Bit manipulation

### Solution
The idea is there should be only one _1_ bit in the positive interger. So we retrieve the population count to check whether it is _1_.

#### Better solution
One-liner bit manipulation is possible.
`return (n > 0 && !(n & (n-1)));`

### Code

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n < 0) {
            return false;
        }
        if (popcount((unsigned int)n) == 1) {
            return true;
        }
        return false;
    }
};

## 268. Missing Number (2024/02/20)

### Topic
Hash table, Bit manipulation

### Solution
1. Sort the input array.
2. Check from _0_ to _n_ to find out the missing number.

#### Better solution
##### Sum formula
1. Sum the input array.
2. Calculate the ideal sum.
3. Subtract _1_ and _2_ is the result.

##### Bit manipulation XOR
**Hint**: A XOR B XOR A = B
1. XOR every member in the array.
2. XOR every ideal number.
3. The resulting value is the answer.

### Code

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.size();
    }
};

## 201. Bitwise AND of Numbers Range (2024/02/21)

### Topic
Bit manipulation

### Solution
1. The key is finding the common prefix of the two boundary numbers.
2. The second key is to use `x & (x - 1)` to clear the rightmost set bit.

### Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        left = (unsigned int)left;
        right = (unsigned int)right;
        while (left < right) {
            right = right & (right - 1);
        }
        return right;
    }
};

## 997. Find the Town Judge (2024/02/22)

### Topic
Hash Table, Graph

### Solution
The key is to find the person with _n-1_ in-degree and _0_ out-degree.
1. Calculate the in-degree and out-degree of each person and store in a hash table.
2. Search for the node with the exact property.

### Code

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // trusted by, trust at
        vector<pair<int, int>> trusted(n+1, make_pair(0, 0));
        for (auto relation : trust) {
            trusted[relation[0]].second++;
            trusted[relation[1]].first++;
        }
        for (int i = 1; i <= n; i++) {
            if (trusted[i].first == n - 1 && trusted[i].second == 0) {
                return i;
            }
        }
        return -1;
    }
};

## 100. Same Tree (2024/02/27)

### Topic
Tree

### Solution

### Code

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        } else if (p->val != q->val) {
            return false;
        }
        if (isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) {
            return true;
        }
        return false;
    }
};

## 543. Diameter of Binary Tree (2024/02/27)

### Topic
Tree

### Solution
Recursively find the longest path from root to leave or the longest diameter of subtree.

#### Better solution
We can store the diameter as a class method, then we don't have to pass it through the recursion tree.

### Code

/**
 * 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:
    int diameterOfBinaryTree(TreeNode* root) {
        auto left = make_pair(0, 0);
        auto right = make_pair(0, 0);
        if (root->left) {
            left = longest_local(root->left);
            left.first += 1;
        }
        if (root->right) {
            right = longest_local(root->right);
            right.first += 1;
        }
        auto result = max(left.second, right.second);
        return max(left.first + right.first, result);
    }

    pair<int, int> longest_local(TreeNode* root) {
        // first: root to leavde, second: leave to leave
        auto left = make_pair(0, 0);
        auto right = make_pair(0, 0);
        if (root->left) {
            left = longest_local(root->left);
            left.first += 1;
        }
        if (root->right) {
            right = longest_local(root->right);
            right.first += 1;
        }
        auto sub = max(left.second, right.second);
        auto curr = left.first + right.first;
        return make_pair(max(left.first, right.first), max(sub, curr));
    }
};

## 513. Find Bottom Left Tree Value (2024/02/28)

### Topic
Tree

### Solution
1. Keep track of the deepest level and the value.
2. Use DFS and update the answer if the level is deeper.

### Code

/**
 * 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:
    int deepest = -1;
    int result = 0;
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0);
        return result;
    }
    void dfs(TreeNode* root, int depth) {
        if (!root->left && !root->right && depth > deepest) {
            deepest = depth;
            result = root->val;
            return;
        }
        if (root->left) {
            dfs(root->left, depth + 1);
        }
        if (root->right) {
            dfs(root->right, depth + 1);
        }
    }
};

## 1609. Even Odd Tree (2024/02/29)

### Topic
Tree, BFS

### Solution
Use BFS to traverse through every node and keep track of the current level and value to compare whether the next element is legal.

### Code

/**
 * 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:
    bool isEvenOddTree(TreeNode* root) {
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 0));
        int curr_val = 0;
        int curr_level = -1;
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            if (node.second > curr_level) {
                curr_level = node.second;
                curr_val = node.first->val;
                if (curr_level % 2 == curr_val % 2) {
                    return false;
                }
            } else {
                int odd_even = curr_level % 2;
                if (odd_even == node.first->val % 2) {
                    return false;
                }
                if (odd_even == 0 && node.first->val <= curr_val) {
                    return false;
                }
                if (odd_even == 1 && node.first->val >= curr_val) {
                    return false;
                }
                curr_val = node.first->val;
            }
            
            if (node.first->left) {
                q.push(make_pair(node.first->left, node.second + 1));
            }
            if (node.first->right) {
                q.push(make_pair(node.first->right, node.second + 1));
            }
        }
        return true;
    }
};