628. Maximum Product of Three Numbers

https://leetcode.com/problems/maximum-product-of-three-numbers/description/
Solution 1. O(n) version of Solution 2.
    int maximumProduct(vector<int>& nums) {
        int N = nums.size();
        int mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN, mi1 = INT_MAX, mi2 = INT_MAX;
        for(int n : nums) {
            if(n>mx1){
                mx3 = mx2;
                mx2 = mx1;
                mx1 = n;
            }
            else if(n>mx2) {
                mx3 = mx2;
                mx2 = n;
            }
            else if(n>mx3) {
                mx3 = n;
            }
            if(n<mi1) {
                mi2 = mi1;
                mi1 = n;
            }
            else if(n<mi2){
                mi2 = n;
            }
        }
        return max(mx1*mx2*mx3, mx1*mi1*mi2);
    }
Solution 2.
    int maximumProduct(vector<int>& nums) {
        int N = nums.size();
        sort(nums.begin(),nums.end());
        if(nums[0]>=0 || nums[N-1]<=0) return nums[N-1]*nums[N-2]*nums[N-3]; //could skip this
        // the maximum would be the bigger one of the two cases:
        return max(nums[0]*nums[1]*nums[N-1], nums[N-1]*nums[N-2]*nums[N-3]);
    }

447. Number of Boomerangs

https://leetcode.com/problems/number-of-boomerangs/description/
Solution 1. 
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(auto &x : points) {
            unordered_map<int,int> vm(points.size());
            for(auto &y : points) {
                d = pow(x.first - y.first, 2) + pow(x.second - y.second, 2);
                res += 2 * vm[d]++;
            }
        }
        return res;
    }
Solution 2.
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int d, res = 0;
        for(int i=0; i<points.size(); i++) {
            unordered_map<int,int> vm(points.size());
            for(int j=0; j<points.size(); j++) {
                d = pow(points[i].first - points[j].first, 2) + pow(points[i].second - points[j].second, 2);
                vm[d]++;
            }
            for(auto &x: vm){
                res += x.second * (x.second - 1);
            }
        }
        return res;
    }

409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/
Solution 1.
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
                res += (cnt[i]& ~1);
        }
        return res + (res < s.size()); // there is odd when (res < s.size())
    }

Solution 2. slower
    int longestPalindrome(string s) {
        int cnt['z'+1] = {0};
        int res = 0;
        int odd = 0;
        for(int i=0; i<s.size(); i++) {
            cnt[s[i]]++;
        }
        for(int i=0; i<='z'; i++){
            if(cnt[i]%2==0)
                res += cnt[i];
            else {
                res += cnt[i] - 1;
                odd = 1;
            }
        }
        return res + odd;
    }

661. Image Smoother

https://leetcode.com/problems/image-smoother/description/
Solution 0. Use the bits at the same address to store the sum and counts
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int L = M.size();
        int W = M[0].size();

        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                for(int m=i-1;m<=i+1;m++) {
                    for(int n=j-1;n<=j+1;n++) {
                        if(m>=0 && m<L && n>=0 && n<W) {
                            // bits 0~7: 255 = 11111111b
                            // original value = M[m][n] & 255
                            // bits 8~11: counts 
                            // 256 = 100000000b
                            // bits 12~ : sum
                            M[i][j] += 256 + ((M[m][n]&255) << 12);
                        }
                    }
                }
            }
        }
        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                // 15 = 1111b, use & to get the counts
                M[i][j] = (M[i][j]>>12)/((M[i][j]>>8) & 15);
            }
        }
        return M;
    }
Solution 1. A boring solution.

206. Reverse Linked List

Solution 1. Iterative method
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* node = head;
        while(node){
            head = node;
            node = node->next;
            head->next = prev;
            prev = head;
        }
        return head;

    }
Solution 2. Recursion
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return node;

    }
Solution 2. With the help of a stack
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;
        ListNode* node = head;
        while(node){
            st.push(node);
            node = node->next;
        }
        if(head) {
            head = st.top();
            node = head;
            st.pop();
        }
        while(!st.empty()) {
            node->next = st.top();
            st.pop();
            node = node->next;
        }
        if(node) node->next = nullptr;
        return head;
    }

13. Roman to Integer

https://leetcode.com/problems/roman-to-integer/description/
Solution 1. Use a map
    int romanToInt(string s) {
        unordered_map<char, int> R2I = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int res = 0;
        for(int i=0; i<s.size();i++) {
            if(i+1<s.size() && R2I[s[i]]<R2I[s[i+1]])
                res -= R2I[s[i]];
            else
                res += R2I[s[i]];
        }
        return res;
    }

Solution 2. Convert each char in s to the corresponding number first.
    int romanToInt(string s) {
        int res = 0;
        int nums[s.size()];
        for(int i=0; i<s.size();i++) {
            switch(s[i]){
                case 'I': nums[i] = 1; break;
                case 'V': nums[i] = 5; break;
                case 'X': nums[i] = 10; break;
                case 'L': nums[i] = 50; break;
                case 'C': nums[i] = 100; break;
                case 'D': nums[i] = 500; break;
                case 'M': nums[i] = 1000; break;
            }
        }
        for(int i=0; i<s.size();i++) {
            if(i+1<s.size() && nums[i]<nums[i+1])
                res -= nums[i];
            else
                res += nums[i];
        }
        return res;
    }

217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/description/
Solution 1. Use a map.
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int n: nums) {
            m[n]++;
            if(m[n]==2) return true;
        }
        return false;
    }

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/
Solution 1. Use array as map.
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size()) return false;
        int cnt[26] = {0};
        for(int i=0; i<s.size();i++){
           // do the counting in one loop
            cnt[s[i]-'a']++;
            cnt[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }
Solution 2. Compare sorted string.
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return(s==t);
    }

100. Same Tree

https://leetcode.com/problems/same-tree/description/
Try to simplify the code.
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p || !q) return p == q;
        return 
            (p->val == q->val) &&
            isSameTree(p->left, q->left) && 
            isSameTree(p->right, q->right);
    }

C++ priority_queue

http://en.cppreference.com/w/cpp/container/priority_queue

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

506. Relative Ranks

https://leetcode.com/problems/relative-ranks/description/
Solution 1. Lambda expression.
    vector<string> findRelativeRanks(vector<int>& nums) {
        int N = nums.size();
        if(N==0) return vector<string> {};
        vector<int> rank2idx(N);
        vector<string> res(N);

        for(int i=0; i < N; i++) rank2idx[i] = i;
        sort(rank2idx.begin(), rank2idx.end(), [&](int i, int j){return nums[i]>nums[j];});
        for(int i=3; i < N; i++) {
            res[rank2idx[i]] = to_string(i+1);
        }
        if(N>0) res[rank2idx[0]] = "Gold Medal";
        if(N>1) res[rank2idx[1]] = "Silver Medal";
        if(N>2) res[rank2idx[2]] = "Bronze Medal";
        return res;
    }

Solution 2.  Using a map.
    vector<string> findRelativeRanks(vector<int>& nums) {
        map<int, int, greater<int>> score2idx;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            score2idx[nums[i]] = i;
        }
        int i=1;
        for(auto &x: score2idx) {
            if(i==1) res[x.second] = "Gold Medal";
            else if(i==2) res[x.second] = "Silver Medal";
            else if(i==3) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i);
            i++;
        }
        return res;
    }
Solution 3. Use a priority_queue
    vector<string> findRelativeRanks(vector<int>& nums) {
        priority_queue<pair<int,int>> q;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            q.push(make_pair(nums[i],i));
        }
       
        for(int i=0; i<nums.size();i++) {
            auto x = q.top();
            if(i==0) res[x.second] = "Gold Medal";
            else if(i==1) res[x.second] = "Silver Medal";
            else if(i==2) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i+1);
            q.pop();
        }
        return res;
    }

compare

map<int, int, greater<int>>

sort(nums.begin(),nums.end(), greater<int>());

387. First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/description/
Solution 1. Use int array as hash table.
    int firstUniqChar(string s) {
        int m[26+'a'] = {0};
        for(auto c : s){
            m[c]++;
        }
        for(int i=0; i<s.size();i++){
            if(m[s[i]]==1) return i;
        }
        return -1;
    }
Solution 2. Use hash table.
    int firstUniqChar(string s) {
        unordered_map<char,int> m;
        for(int i=0;i<s.size();i++){
            m[s[i]]++;
        }
        for(int i=0;i<s.size();i++){
            if(m[s[i]]==1) return i;
        }
        return -1;
    }

169. Majority Element

https://leetcode.com/problems/majority-element/description/
Solution 1. Use Boyer–Moore majority vote algorithm.
http://shxi.blogspot.com/2017/11/boyermoore-majority-vote-algorithm.html
Make use of the fact that the majority element appears more than n/2 times. Keep track of the element value and count when looping the array. Increase the count each time when get the same value and decrease the count when get a different value. When the count is 0, change the value to the new element. Because the majority element appears more than n/2 times, the value kept after looping is always the majority element with count larger than 0.
    int majorityElement(vector<int>& nums) {
        int res = nums[0], cnt = 1;
        for(int i=1; i<nums.size(); i++){
            if(cnt == 0){
                res = nums[i];
                cnt = 1;
            }
            else if(nums[i] == res)
                cnt++;
            else
                cnt--;
        }
        return res;
    }

Solution 2. Use map to count for each element
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        int mx = 0, res = 0;
        for(int n: nums)
            m[n]++;
        for(auto const& x: m) {
            if(mx < x.second) {
                mx = x.second;
                res = x.first;
            }
        }
        return res;
    }

Loop through map

https://stackoverflow.com/questions/26281979/c-loop-through-map
Loop through a map:

map<string, int>::iterator it; for ( it = symbolTable.begin(); it != symbolTable.end(); it++ ) { std::cout << it->first // string (key) << ':' << it->second // string's value << std::endl ; } With C++11 ( and onwards ), for (auto const& x : symbolTable) { std::cout << x.first // string (key) << ':' << x.second // string's value << std::endl ; } With C++17 ( and onwards ), for( auto const& [key, val] : symbolTable ) { std::cout << key // string (key) << ':' << val // string's value << std::endl ; }

563. Binary Tree Tilt

https://leetcode.com/problems/binary-tree-tilt/description/
Solution 1. Recursive post order traversal.
    void tilt(TreeNode *node, int &s, int &st) {
        if(!node) return;
        int sl=0, sr=0;
        tilt(node->left, sl, st);
        tilt(node->right, sr, st);
        s = node->val + sl + sr;
        st += abs(sl-sr);
    }
    int findTilt(TreeNode* root) {
        int s = 0, st = 0;
        tilt(root, s, st);
        return st;
    }
or
    int tilt(TreeNode *node, int &st) {
        if(!node) return 0;
        int sl = tilt(node->left, st);
        int sr = tilt(node->right, st);
        st += abs(sl-sr);
        return node->val + sl + sr;
    }
    int findTilt(TreeNode* root) {
        int st = 0;
        tilt(root, st);
        return st;
    }
Solution 2. Iterative post order traversal. Using maps to save the sums and tilts of the sub-tree at a particular node. (much slow by using the maps)

599. Minimum Index Sum of Two Lists

https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/
Solution 1. Hash table
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string,int> m;
        vector<string> res;
        int least = INT_MAX, s;
        for(int i=0;i<list1.size();i++) {
            m[list1[i]] = i;
        }
        for(int i=0;i<list2.size();i++) {
            if(m.count(list2[i])) {
                s = i+m[list2[i]];
                if( s == least) {
                    res.push_back(list2[i]);
                }
                else if(s < least){
                    res.clear();
                    res.push_back(list2[i]);
                    least = s;
                }
            }
        }
        return res;
    }

657. Judge Route Circle

https://leetcode.com/problems/judge-route-circle/description/

    bool judgeCircle(string moves) {
        int h=0, v=0;
        for(int i=0;i<moves.size();i++) {
            switch (moves[i]) {
                case 'R': h++; break;
                case 'L': h--; break;
                case 'U': v++; break;
                case 'D': v--; break;
            }
        }
        return h==0 && v==0;
    }

404. Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/description/
Solution 1. Recursive tree traversal, use a bool to indicate if the node is the left branch.
    void inOrder(TreeNode*node, int &s, bool left) {
        if(!node) return;
        if(node->left) inOrder(node->left, s, true);
        if(left && !node->left && !node->right) s += node->val;
        if(node->right) inOrder(node->right, s, false);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int s=0;
        inOrder(root, s, false);
        return s;
    }
Solution 2. Iterative tree traversal.
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        int s=0;
        bool isLeft = false;
        TreeNode* node = root;
        stack<TreeNode*> st;
        st.push(node);
        while(!st.empty()){
            node = st.top();
            st.pop();
            if(isLeft && !node->left && !node->right) {
                s += node->val;
                isLeft = false;
                continue;
            }
            if(node->right) {
                st.push(node->right);
                isLeft = false;
            }
            if(node->left) {
                st.push(node->left);
                isLeft = true;
            }
        }
        return s;
    }

122. Best Time to Buy and Sell Stock II

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
    int maxProfit(vector<int>& prices) {
        int p=0;
       
        for(int i=1;i<prices.size();i++) {
            if(prices[i] > prices[i-1])
                p += prices[i]-prices[i-1];
        }
        return p;

    }