Binary Tree Postorder/Inorder/Preoder Traversal (non-recursive) -- LeetCode 145, 94

[Question]

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

[Analysis]
The state of recursive calls can be simulated by stacks. The key is to find the branch (left or right) where the stack pop() happened. The preorder/inorder,/postorder functions are placed in differnt branch (in, left, right) respectively.

[Solution]
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        stack<TreeNode*> st;
        TreeNode* p=root;
        st.push(p);
        
        vector<int> res;
        while(!st.empty()) {
            if (st.top()==p && !p->left && !p->right) { 
                //-- leave node is reached and is at the top of stack.
                res.push_back(st.top()->val);     //--shared by all orders.
                st.pop();
                continue;
            }
            if (st.top()==p) {
                //res.push_back(st.top()->val);    // -- pre-order output here.
                p=p->left;
                if (p) st.push(p);
            }
            else if (st.top()->left==p) {
                res.push_back(st.top()->val);     // -- in-order output here
                p=st.top()->right;
                if (p) st.push(p);
            }
            else if (st.top()->right==p) {
                //res.push_back(st.top()->val);   //-- post-order output here
                p=st.top();
                st.pop();
            }
        }

        return res;
    }
};

Queue Reconstruction by Height -- LeetCode

[Question]

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

[Analysis]
Be Greedy. Person (h,k) at position 0 should have k=0. So group all (h,0), the one with smallest h' is at position 0. Then look at all other persons (h,k) whose h is greater or equal to h', decrease their k by 1 (because h' contribute 1 to their k values). Repeat the previous steps and find person at position 1, .., n. The time complexity is O(N^2).

Another way to reconstruct the queue is by sorting. Suppose a person (h',k'), all persons (h,k) with greater or equal height have been in a sorted queue Q, the k' is the right position to insert (h',k') into the Q and create a Q' while maintaining all existing (h,k). Repeat the same process on Q' and remaining persons. The time complexity is O(N^2).

[Solution]
//-- using sorting --
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        auto comp=[](pair<int,int> &a, pair<int,int> &b)
            { return a.first<b.first || a.first==b.first && a.second > b.second;};
        sort (people.begin(), people.end(), comp);
        vector<int,int> res;
        for (int i=people.size(); i>=0; i++)
            res.(res.begin()+people[i].second, people[i]);
    }
};

//--greedy --
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> rslt;
     
        vector<pair<int, int>> bak (people);
        auto comp= [](pair<int, int> a, pair<int,int> b)
            { return a.second < b.second || a.second ==b.second && a.first<b.first;};
         
        while (rslt.size()!= people.size() ) {
            auto it = min_element(bak.begin(), bak.end(), comp);
            rslt.push_back(people[it-bak.begin()] );
            it->second = INT_MAX;
            for (auto &p: bak) {
                if (p.second!=INT_MAX && p.first<=it->first) {
                    p.second --;
                }
            }
        }
        return rslt;
    }
};

Maximum Square -- LeetCode 221

[Question]

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

[Analysis]
This is similar with the Maximum Rectangle problem. While it can be done by the same approach, there is a  Dynamic Programming solution to solve this.

Define S[i,j] = the length of largest square positioned at Matrix[i,j], then
          S[i,0] = 1 if Matrix[i,0]= '1';
          S[0,j] = 1 if Matrix[0,j]= '1';
          S[i,j] = min ( S[i-1,j-1], S[i-1,j], S[i,j-1] ) + 1 if Matrix[i,j]='1', i>0, j>0;

Time complexity and space complexity are O(M x N).

[Solution]
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
       
        vector<vector<int>> s(matrix.size(), vector<int>(matrix[0].size(),0) );
        int max_len=0;
       
        for (int i=0; i< matrix.size(); i++) {
            s[i][0] = (matrix[i][0]=='1')?1:0;
            max_len |= s[i][0];
        }
           
        for (int i=0; i< matrix[0].size(); i++) {
            s[0][i] = (matrix[0][i]=='1')?1:0;
            max_len |= s[0][i];
        }
       
        for (int i=1; i< matrix.size(); i++)
            for (int j=1; j<matrix[0].size(); j++) {
                if (matrix[i][j] =='0') continue;
                s[i][j] = min(min(s[i-1][j], s[i][j-1]),s[i-1][j-1])+1;
                max_len = max(max_len, s[i][j]);
            }
               
        return max_len*max_len;
    }

};

Single Element in a Sorted Array -- LeetCode 540

[Question]
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

[Solution]
//--- C++ ---
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0, r=nums.size();
        int mid = 0;
        while (l+1<r) {
            mid = (l+r)>>1;
            if (nums[mid]==nums[mid^0x01])
                l = mid+1;
            else
                r = mid;
        }
        return nums[l];
    }
};

//--- Python ---
class Solution(object):
    def singleNonDuplicate(self, nums):
        lo, hi=0, len(nums)-1
        while lo<hi:
            m = (lo+hi)/2
            if nums[m]==nums[m^1]:
                lo = m+1
            else:
                hi = m
        return nums[lo]
         

Reverse Pairs -- LeetCode 493

[Question]

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

[Analysis]
This is a typical problem for Binary Index Tree (BIT). Another solution is to use a BST with a smaller counter in each node -- but this solution will make time complexity O(N*N) for sorted input array. BIT is still a better solution.

[Solution]
class BIT {
    vector<int> nodes;
    int lowbit(int x) { return -x & x; }
public:
    BIT(int n) : nodes(n+1,0) {};
 
    void add(int pos, int val) {
        while (pos<nodes.size()) {
            nodes[pos]+=val;
            pos += lowbit( pos );
        }
    }
 
    int count(int pos) {
        int res =0;
        while (pos>0) {
            res += nodes[pos];
            pos -= lowbit( pos );
        }
        return res;
    }
};

typedef long long LL;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<pair<LL,int> > sorted;
        for (int i=0; i<nums.size(); i++) {
            sorted.push_back({(LL)nums[i],i+1});
            sorted.push_back({(LL)nums[i]<<1, -i-1});
        }
        sort(sorted.begin(), sorted.end(), [](pair<LL,int>& a, pair<LL,int>& b) {
            return a.first< b.first || a.first==b.first && a.second>b.second;
        });
     
        unordered_map<LL,int> map;
        for (int i=0; i<sorted.size(); i++)
            map[sorted[i].second] = i;
     
     
        BIT tree(sorted.size());
        int res=0;
        for (int i=nums.size()-1; i>=0; i--) {
            res += tree.count(map[i+1]);
            tree.add(map[-i-1]+1,1);
        }
        return res;
    }
};

Evaluate Division -- LeetCode 399

[Question]

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

[Analysis]
Consider each equation as an edge in a directed graph, each string is a vertex, then the problem becomes to find a path for each pair of strings in the queries array.

Inspired by Floyd-Warshall algorithm, using a 2-D matrix to represent vertex A to vertex path (if exists), A[i][j] = A[i][k]*A[k][j], for k=0,...|v|-1.

[Solution]
class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        set<string> nodes;
        unordered_map<string, int> inv;
     
        for (auto& e:equations) {
            nodes.insert(e.first);
            nodes.insert(e.second);
        }
        int i=0;
        for (auto it= nodes.begin(); it!=nodes.end(); it++, i++)
            inv[*it] = i;
     
        vector<vector<double>> equ(nodes.size(), vector<double>(nodes.size(),-1.0));
        for (int i=0; i< nodes.size(); i++)
            equ[i][i]= 1.0;
         
        for (int i=0; i< equations.size(); i++) {
            int x = inv[equations[i].first];
            int y = inv[equations[i].second];
            equ[x][y] = values[i];
            equ[y][x] = 1.0 / values[i];
        }
     
        for (int k=0; k<nodes.size(); k++) {
            for (int i=0; i<nodes.size(); i++) {
                for (int j=i+1; j<nodes.size(); j++) {
                    if (equ[i][k]!=-1.0 && equ[k][j]!=-1.0) {
                        equ[i][j] = equ[i][k] * equ[k][j];
                        equ[j][i] = 1.0/ equ[i][j];
                    }
                }
            }
        }
     
        vector<double> res;
        for (auto& q: queries) {
            if (nodes.count(q.first) && nodes.count(q.second)) {
                int x= inv[q.first], y= inv[q.second];
                res.push_back( equ[x][y] );
            }
            else res.push_back(-1.0);
        }
        return res;
    }

};

Range Sum Query - Mutable -- LeetCode 307

[Question]

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

[Analysis]
By using brute force on array itself, the update() can be achieved in O(1) and the sumRange() in O(N). It is not optimal when sumRange() to be called more often.

An alternative way is to use Segment Tree. The Segment Tree is heap like data structure. Both update() and sumRange() can be achieved in O(LogN). Extra O(N) space is used though.

Another range sum problem is "Count of Range Sum".

[Solution]
//
//-- Segment Tree --
//
class NumArray {
    vector<int> seg;
    int n;
public:
    NumArray(vector<int> &nums) {
        n = nums.size();
        seg.resize(n<<1);
        for (int i=n; i< (n<<1); i++)  seg[i] = nums[i-n];
        for(int i=n-1; i>0; i--) seg[i] = seg[i<<1] + seg[i<<1|1];
    }

    void update(int i, int val) {
        int diff = val-seg[i+n];
        for( i+=n; i>0; i>>=1 )
            seg[i] += diff;
    }

    int sumRange(int i, int j) {
        int res=0;
        for (i+=n, j+=n; i<=j; i>>=1, j>>=1) {
            if (i&1) res+=seg[i++];
            if (!(j&1)) res+=seg[j--];
        }
        return res;
    }
};