[LeetCode] Divide Two Integers

Problem Statement (link):
Divide two integers without using multiplication, division and mod operator.
Analysis:
As multiplication and division operations are forbade, we could using deduction - deduct divisor from dividend until the remainder is less than the divisor, and count how many times we performed the deduction. However, the algorithm yields TLE.

The idea is that instead of deducting the divisor from dividend, we deduct i*divisor from the dividend. We repeatedly increase i to reduce the number of deductions, until the remainder is less that i*divisor.

Takeaway:
abs(INT_MIN) or -INT_MIN doesn't produce positive result. We could choose one of the following approaches:

long long pos1 = abs((double) INT_MIN);

unsigned int pos2 = -INT_MIN; // or abs(INT_MIN)

Code:
class Solution {

public:
    int divide(int dividend, int divisor) {
        if (dividend==0 || divisor==0) return 0;
        int sign=(dividend^divisor)>>31;
        long long rem=abs((double)dividend);
        long long div=abs((double)divisor);

        long long res=0;
        while(rem>=div && rem>0) {
            long long div2=div;
            for (int i=0; rem>=div2; i++, div2<<=1) {
                rem-=div2;
                res+=1<<i;
            }
        }
        return sign==0? res:-res;
    }
};

[LeetCode] Unique Binary Search Trees I && II

Unique Binary Search Trees I

Problem Statement (link):

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:
At first sight, this problem seems complicated. We may get some salt if we divide the problem into smaller sub-problems.

If n=0, there is 1 BST, which is the NULL tree.
If n=1, there is 1 BST, which is the single root node.
If n=2, there is 2 BST, which are BST with 1 being the root and 2 being the root.
...

We observe that for a value k, the root node may be any k=[1:n]. Thus, the number of BSTs in total is the number of sub-trees with node k valued from 1 to n.

Suppose the root node is k, then its left sub-tree consists of all nodes less that k, it's right sub-tree consists of all nodes larger than k. Then number of BSTs with root node k is then the product of number of BSTs of left sub-tree and number of BSTs of right sub-tree. Further, The number of BSTs of the left sub-tree is the number of sub-trees with the left root node valued from 1 to k-1, the number of BSTs of the right sub-tree is the number of sub-sub-trees with the right root node valued from k+1 to n. Thus we could model and solve this problem with recursion.

Furthermore, if we think twice about the method, it's sort of similar to the idea of DP - having previous calculated results stored, calculate and update new results.

Code:

class Solution {
public:
    int numTrees(int n) {
        // count[i] - number of unique BST constructed from i nodes
        vector<int> count(n+1);
        count[0] = 1;
        recur(count, n);
        return count[n];
    }

    void recur(vector<int> &count, int n) {
        for (int i=1; i<=n; i++) {
            // k - all possible num of nodes of left subtree
            for (int k=0; k<i; k++) {
                count[i] += count[k]*count[i-k-1];
            }
        }
    }
};

Unique Binary Search Trees II

Problem Statement (link):

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:
This problem is a bit difficult as it's not easy to come up with a clear solution.

First, the problem asks for "all" BSTs, similar to the previous problem, we consider using DFS on every possible node values, i.e., from 1 through n.

The difficulty lies in finding a way to store each BST. The root node's value i of a valid BST must be within 1 and n, the root of its left subtree must be within 1 and i-1, the root of its right subtree must be within i+1 and n. This idea is same as that of the previous problem. Now, suppose we have all the possible nodes stored in two vectors - leftSub and rightSub, in order to construct a tree, we must construct a new root node with value i that points to a member in leftSub and points to a member in rightSub, respectively. Then, we push the node into our result vector.

Codes:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode*> res;
        recur(1, n, res);
        return res;
    }
    void recur(int l, int r, vector<TreeNode*> &res) {
        if (l>r) 
            res.push_back(NULL);
        else {
            for (int i=l; i<=r; i++) {
                // recursively build-up left and right subtree for root node i
                vector<TreeNode*> leftSub, rightSub;
                recur(l, i-1, leftSub);
                recur(i+1, r, rightSub);
                // Choose left and right subtree combinations for root node i
                for (int j=0; j<leftSub.size(); j++) {
                    for (int k=0; k<rightSub.size(); k++) { 
                        TreeNode* node=new TreeNode(i);
                        node->left = leftSub[j];
                        node->right= rightSub[k];
                        res.push_back(node);
                    }
                }
            }
        }
    }
};

[LeetCode] Remove Duplicates from Sorted List I && II

Remove Duplicates from Sorted List I

Problem Statement (link):

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Analysis:
Use two pointers, one pointer points to the current node, the other pointer advances if there's duplicates.

The time complexity is O(n), where n is length of the linked list. The space complexity is constant.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head==NULL || head->next==NULL) return head;

        ListNode *p1=head;
        while (p1->next!=NULL) {
            ListNode *p2=p1->next;
            while (p2 && p1->val==p2->val)
                p2=p2->next;

            if (p1->next==p2) // no dup
                p1=p1->next;
            else
                p1->next=p2;
        }
        return head;
    }
};

Remove Duplicates from Sorted List II

Problem Statement (link):

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:
Once the previous problem is understood, the only difference with this problem is that we need to save previous node.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head==NULL || head->next==NULL) return head;

        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        head=prev;
        while(prev->next!=NULL) {
            ListNode *curr=prev->next;
            // advance pointer if duplicate
            while(curr->next && curr->val==curr->next->val)
                curr=curr->next;

            if (curr!=prev->next) // re-link prev if duplicate
                prev->next=curr->next;
            else    // advance prev if no duplicate
                prev=prev->next;
        }
        return head->next;
    }
};

[LeetCode] Merge k Sorted List

Problem Statement (link):
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Analysis:
There are three types of solutions:

Suppose the list has k linked list, the longest linked list is with length n.

1) Naive approach:
We compare each of the first k nodes' value, find the node with smallest value, pull that node out and add it to the new list. We repeat this process until all nodes are removed from the original list.

The time complexity is O(k*n*k) = O(n*k^2)

2) Similar idea to Merge sort
We merge every two linked lists in sequence, and repeat this merging until we are left only one linked list.
In run 1, we did k/2 pair merges and left with (k+1)/2 linked lists;
In run 2, we did k/4 pair merges and left with (k+1)/4 linked lists;
...

The time complexity is O(n*k*log k), the log k comes from the fact that we did log k merges in total.

The implementation of this algorithm is below in Sol 1.

3) Use container which auto-sort the incoming data. Three possible options we have are: multiset, heap, priority_queue. I choose to implement using priority_queue for no good reason.

The idea is simple: push each node in into a size k priority queue, each time we pop out the top node - the one with smallest value among all others, and connect it to output list. As we will go through each node once, and each push operation cost log k, the overall time complexity is O(n*k*log k).

Code:
Sol 1: Merge sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int k=lists.size();
        if (k==0) return NULL;
        return recur(lists, 0, k-1);
    }
    ListNode *recur(vector<ListNode *> &lists, int left, int right) {
        if (left<right) {
            int mid=(left+right)/2;
            return mergeTwoLists(recur(lists, left, mid), recur(lists, mid+1, right));
        }
        else
            return lists[left];
    }
    ListNode *mergeTwoLists(ListNode* head1, ListNode* head2) {
        if (!head1) return head2;
        if (!head2) return head1;

        ListNode *head=new ListNode(INT_MIN);
        ListNode *curr=head;

        while(head1 && head2) {
            if (head1->val<head2->val) {
                curr->next=head1;
                head1=head1->next;
            }
            else {
                curr->next=head2;
                head2=head2->next;
            }
            curr=curr->next;
        }
        if (head1) curr->next=head1;
        else if (head2) curr->next=head2;
        return head->next;
    }
};

Sol 2: Priority queue

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
private:
    struct cmp {
        bool operator() (ListNode *n1, ListNode *n2) {
            return n1->val>n2->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size()==0) return NULL;
        priority_queue<ListNode *, vector<ListNode *>, cmp> heap;

        // add all lists' heads in heap
        for (int i=0; i<lists.size(); i++)
            if (lists[i]) // skill NULL lists
                heap.push(lists[i]);

        // dummy head
        ListNode* head=new ListNode(INT_MAX);
        ListNode* curr=head;

        // pop and push
        while(!heap.empty()) {
            curr->next=heap.top();
            heap.pop();
            curr=curr->next;
            if (curr->next)
                heap.push(curr->next);
        }
        return head->next;
    }
};

Takeaways:
All the three data structures/abstract data type (ADT) are capable of storing items in sorted order. They allow user-defined comparison functions comp as well.

	multiset	heap	priority_queue
Type	Container object (ADT)	A way of organizing items in the range	Container adaptor - the standard underlying container is vector
Implementation	Self-balanced BST		Similar to heap, call make_heap, push_heap, pop_heap to maintain heap properties
Complexity (insert, emplace, erase, find, push, pop etc.)	logarithmic in general, but amortized linear or constant in special cases indicated here	Up to linear in three times the range distance	One push_back call to underlying container, one push_heap call on the range *
Key ops	empty begin, end insert, emplace erase find clear	make_heap push_heap pop_heap sort_heap	emplace empty pop push size top
Relatives	unordered_multiset - implemented using hash tables
Other			Default comparison is less, i.e., greatest value at the top

* push_back: in vector case, time complexity is constant in general. But if reallocation happens, the reallocation can be up to linear on the range of the entire data size.
   push_heap: up to logarithmic time cost.

[LeetCode] Next Permutation

Problem Statement (link):

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Analysis:
There's a classic algorithm on Wiki of finding the next string permutation in lexicographical order. There are four steps:
1) Find the largest index k where num[k]<num[k+1]
2) Find the largest index l where l>k and num[l]>num[k]
3) Swap num[k] and num[l]
4) Reverse num[k+1 : len], where len is the length of the given string

To see how this algorithm works, scratching a simple example on your own will help.

For our purpose, in addition to step 4, if there's no possible larger string found, we wrap up to find the smallest string by reversing the entire string.

Code:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int len=num.size();
        if (len<=1) return;

        // step 1
        int k=0;
        for (int i=0; i<len-1; i++)
            if (num[i]<num[i+1])
                k=i;

        // step 2
        int l=0;
        for (int i=0; i<len; i++)
            if (i>k && num[k]<num[i])
                l=i;

        // step 3 - swap
        swap(num, k, l);

        //step 4 - reverse
        k==l ? reverse(num.begin(), num.end()):reverse(num.begin()+k+1, num.end());
    }
    void swap(vector<int> &num, int a, int b) {
        int t=num[a];
        num[a]=num[b];
        num[b]=t;
    }
};

[LeetCode] Gray Code

Problem Statement (link):

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Analysis:
The OJ could only judge one instance of gray code sequence, based on wiki page, the sequence of gray code when n=3 is:

000
001
011
010
110
111
101
100

If we observe carefully, we found out that except for the MSB, where the first four numbers are all 0's and last four numbers are all 1's, the bit sequence are mirrored as color coded above. Thus, our algorithm will build new gray codes when n=k, based on the gray codes when n=k-1. This is an iterative process.

The time complexity is exponential - O(2^n), as we need 1+2+4+...+(2^(n-1)) operations.

Code:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1, 0);
        if (n==0) return res;

        for (int k=0; k<n; k++) {
            int sz=res.size(); //res's size is changing, need to assign a fixed value
            for (int i=sz-1; i>=0; i--) {
                res.push_back((1<<k)+res[i]);
            }
        }
        return res;
    }
};

[LeetCode] Minimum Path Sum

Problem Statement (link):

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Analysis:
This problem is obviously a DPproblem. We could construct a 2D dp matrix with the same size as given grid, in which entry dp[i][j] represents the minimum path sum from (0, 0) to (i, j). After we initialize the first row and col of dp matrix, we could iteratively adding new min path sums to each entry. The last dp entry is the result we are looking for. This solution is shown in Sol 1 below. The time and space complexity of this algorithm is O(m*n), where m and n are dimension of the grid.

However, using the same idea from the problem Triangle, we could reduce the space complexity to O(n). The idea is to reuse the dp vector each time we reach a new row/col - depending on which one we choose. See Sol 2 for the implementation of this algorithm.

Code:
Sol 1:

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m=grid.size();
        int n=grid[0].size();
        if (m==0) return 0;
        vector<vector<int>> dp(m, vector<int> (n));

        // init dp
        dp[0][0]=grid[0][0];
        for (int i=1; i<m; i++)
            dp[i][0]=grid[i][0]+dp[i-1][0];
        for (int j=1; j<n; j++)
            dp[0][j]=grid[0][j]+dp[0][j-1];

        // traverse
        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j];
      
        return dp[m-1][n-1];
    }
};

Sol 2:

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m=grid.size();
        int n=grid[0].size();
        if (m==0) return 0;
        vector<int> dp(n, INT_MAX);
        dp[0]=0;

        // traverse
        for (int i=0; i<m; i++) {
            dp[0]=grid[i][0]+dp[0];
            for (int j=1; j<n; j++)
                dp[j]=min(dp[j], dp[j-1])+grid[i][j];
        }
        return dp[n-1];
    }
};