[LeetCode] Anagrams

Problem Statement (link):

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

Analysis:
How to determine if two strings are anagrams?

My first thought was to store each chars from the first string in a hash map, then probe the hash map with each chars in the second string to determine if two strings have the sames chars. If we use this approach, we need to make sure we consider the duplication cases. We could potentially use the value field in the hash map to record the number of occurrence of each char. The time complexity is O(m), where m is the length of the string. The implementation is provided at the end of this post

The second idea is to simply sort string 1, and compare it with the sorted string 2, if they are equal, it means these two are anagrams. The time complexity of this algorithm is O(m log m), which is worse than the first one where we use hash map. However, it turned out that this idea suits this problem better as we have to probe another hash map that stores all strings every time a new string comes in in order to determine if the incoming string is anagram with any of the existing strings in the hash map, this leads to a O(m*n^2) algorithm in general.

The overall time complexity of the second approach is O(n * m log m). Where n is the number of strings and m is the average string length.

Code:

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> out;
        if (strs.empty()) return out;
        unordered_map<string, int> map;

        for (int i=0; i<strs.size(); i++) {
            string tmp=strs[i];
            sort(tmp.begin(), tmp.end());

            if (map.find(tmp)!=map.end()) { // found
                out.push_back(strs[i]);
                // insert the 1st occurance string if hvn't done it
                if (map[tmp]>=0) { 
                    out.push_back(strs[map[tmp]]);
                    map[tmp]=-1;
                }
            }
            else
                map.emplace(tmp, i);
        }
        return out;
    }
};

Takeaways:
- A better partial solution doesn't necessarily lead to a better overall solution.

Here is the code for checking if two strings are anagrams using a hash map, assuming the strings are legal.

bool isAnagram(string a, string b) {
    unordered_map<char, int> map;

    // construct map using string a
    for (int i=0; i<a.size(); i++) {
        if (map.find(a[i]) == map.end())
            map.emplace(a[i], 1);
        else
            map[a[i]]++;
    }

    // check anagram using the map
    for (int i=0; i<b.size(); i++) {
        if (map.find(b[i])==map.end() || map[b[i]]<1)
            return false;
        else
            map[b[i]]--;
    }

    // check map if all value is 0
    for (unordered_map<char, int>::iterator it=map.begin(); it!=map.end(); it++)
        if (it->second!=0)
            return false;
    return true;
}

[LeetCode] Binary Tree Level Order Traversal I & II

Binary Tree Level Order Traversal I

Problem statement (link):

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Analysis:
Just add a level variable to indicate whether we are at a new level and increase the size of output vector<vector<int>>.

Code:

/**
 * 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<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > nodeV;
        if (root==NULL) return nodeV;

        int level = 0;
        helper(nodeV, root, level);

        return nodeV;
    }
  
    void helper(vector<vector<int> > &nodeV, TreeNode *node, int level) {
        if (node==NULL) return;

        if (level >= nodeV.size())
            nodeV.push_back(vector<int> ());
        nodeV[level].push_back(node->val);

        if (node->left != NULL) helper(nodeV, node->left, level+1);
        if (node->right !=NULL) helper(nodeV, node->right, level+1);
    }
};

Binary Tree Level Order Traversal II

Problem Statement (link):

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Analysis:
Same as the previous problem, we just need to reverse the output vector order.

Code:

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> out;
        if (root==NULL) return out;

        int level=0;
        recur(out, root, level);

        // reverse order
        for (int i=0; i<out.size()/2; i++) {
            vector<int> tmp=out[i];
            out[i]=out[out.size()-i-1];
            out[out.size()-i-1]=tmp;
        }
        return out;
    }

    void recur(vector<vector<int>>& out, TreeNode* node, int level) {
        if (node==NULL) return;
        if (out.size()<=level)
            out.push_back(vector<int> ());

        out[level].push_back(node->val);
        recur(out, node->left, level+1);
        recur(out, node->right, level+1);
    }
};

[LeetCode] Implement strStr()

Problem Statement (link)

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Analysis:
No specific algorithm needed for this problem. We simply traverse the two strings and compare each char. The time complexity is O(n*m), where n and m are the lengths of string needle and string haystack, respectively.

Code:

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        char *st=haystack;
        char *pt1=haystack;
        char *pt2=needle;

        while(*pt1!=NULL && *pt2!=NULL) {
            if (*pt1==*pt2) {
                pt1++; pt2++;
                continue;
            }
            st++;
            pt1=st;
            pt2=needle;
        }
        return *pt2==NULL ? st:NULL;
    }
};

[LeetCode] Rotate Image

Problem Statement (link):

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

Analysis:
This is a problem from CrackCode150 book, it's problem 1.6.

Basically, we modified the values layer by layer from outside to inside. The outer loop is to traverse from outer layer to inner layer, the inner loop is to traverse the pixel entries in each layer.

Code:

class Solution {
public:
    // 4-way swaps from outer to inner
    void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        if (n==0) return;

        // i - layers
        for (int i=0; i<n/2; i++) {
            int st=i, ed=n-i-1;

            // traverse each edge
            for (int j=st; j<ed; j++) {
                int tmp=matrix[st][j];

                // left to top
                matrix[st][j]=matrix[st+ed-j][st];
                // bottom to left
                matrix[st+ed-j][st]=matrix[ed][st+ed-j];
                // right to bottom
                matrix[ed][st+ed-j]=matrix[j][ed];
                // top to right
                matrix[j][ed]=tmp;
            }
        }
    }
};

[LeetCode] Valid Palindrome

Problem Statement (link):

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
We compare the to chars from head and tail of the string, if they are the same, we proceed on checking the next char pair, otherwise, we return false.

Note that we need to check if the chars are valid chars before comparison.

This algorithm gives us O(n) time complexity.

Code:

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) return true;
        int len=s.length();
       
        int head=0, tail=len-1;
        while (tail>=head) {
            // Skip invalid chars
            if (!isValid(s[head])) {
                head++;
                continue;
            }
            if (!isValid(s[tail])) {
                tail--;
                continue;
            }

            if (!isEqual(s[head], s[tail])) return false;
            head++; tail--;
        }
        return true;
    }
       
    bool isEqual(char c1, char c2) {
        if (c1==c2 || c1-c2=='A'-'a' || c1-c2=='a'-'A')
            return true;
        return false;
    }
    bool isValid(char c1) {
        if ((c1-'0'>=0 && c1-'0'<10) || (c1-'a'>=0 && c1-'a'< 26) || (c1-'A'>=0 && c1-'A'<26))
            return true;
        return false;
    }
};

[LeetCode] Sum Root to Leaf Numbers

Problem Statement (link):

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

Analysis:
This problem should be straightforward, we need to traverse to each leaf to form a number, and add all the numbers together. We use a vector<int> to store the traversed node's value.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    // Recursive - preorder
    int sumNumbers(TreeNode *root) {
        if (root==NULL) return 0;
        vector<int> sum;
        int nodeSum=0;
        dfs(root, sum, nodeSum);
        nodeSum=0;

        for (int i=0; i<sum.size(); i++) {
            nodeSum += sum[i];
        }

        return nodeSum;
    }

    void dfs(TreeNode *node, vector<int> & sum, int nodeSum)  {
        nodeSum = 10*nodeSum+node->val;
        if (node->left==NULL && node->right==NULL) {
            sum.push_back(nodeSum);
        }
        else {
            if (node->left!=NULL)
                dfs(node->left, sum, nodeSum);
            if (node->right!=NULL)
                dfs(node->right, sum, nodeSum);
        }
    }
};

[LeetCode] Longest Consecutive Sequence

Problem Statement (link):

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

Analysis:
Apparently we are not allowed to sort the array as the fastest sorting algorithm gives us O(n lg n) complexity yet the problem requires a O(n) time complexity.

Hashing technique should come to our mind as it gives us a constant access to every entry. Suppose we build a hash map with same entries as the given array, start from one value, we could easily probe to see if the next larger value exist, if so, we continue probing the next larger value. If we traverse all entries in this manner, we will finally find the expected smallest value that starts the longest sequence.

However, the above algorithm is not ideal. Why? Imagine the following case: 4 3 5 9 1. Starting from 4, we checked 5; starting from 3, we checked 4 and 5; then we check 5 again. As you can see, there are absolutely lots of redundant probings.

One way to remove the redundancy is to remove the visited value. However, we couldn't just simply erase a value just because we visited. The reason is that we can't guarantee to find the longest sequence that has the current value. But what if we could? For each entry, suppose we not only find its larger values, but also we find its smaller values, now we are safe to remove the visited values as the longest sequence that has the current values is considered.

For instance, in the above example, if we are at entry 4, we find a larger value 5, and erase 5, and there's no 6; now we start to find the smaller value 3, and erase 3. Since there are no value 2, we are safe to say the longest sequence that contains value 3, 4 and 5 is with length 3.

The above algorithm gives us O(n) time complexity.

Code:

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()==0) return 0;

        unordered_map<int, int> hash;
        for (int i=0; i<num.size(); i++) {
            hash.emplace(num[i], 0);
        }
       
        int maxlen=1;
        for (int i=0; i<num.size(); i++) {
            int maxlen_tmp=1;
           
            // Search for the larger value
            int value = num[i]+1;
            while(hash.find(value)!=hash.end()) { // found
                hash.erase(value);
                maxlen_tmp++;
                value++;
            }
            // Search for the smaller value
            value = num[i]-1;
            while(hash.find(value)!=hash.end()) {
                hash.erase(value);
                maxlen_tmp++;
                value--;
            }

            maxlen=max(maxlen, maxlen_tmp);
        }
        return maxlen;
    }
};

[LeetCode] Reorder List

Problem Statement (link):

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Analysis:
If we are given an array, we simply need to interleave the corresponding nodes with O(1) access time. However, linked list doesn't offer us a constant access time and it's too costly to traverse the list every time to access a node.

If we think about how we construct the reordered list, we notice that we want to traverse from L_n to L_(n/2) reversely for insertion, where all the inserted nodes are from the second half of the list. If we could reverse the second half list, we could access each nodes in linear time.

Thus, we use the following algorithm:
1) Split the list into two halves. We find the middle of the list using two pointers - a slow pointer and a fast pointer. This costs us O(n) time.
2) Reverse the second half of the list. This takes O(n) time using the algorithm below.
3) Traverse the two lists one node each time and link pairs together --> O(n) time.

For step 2), it's easy to see that bubble sort would do the work with time O(n^2). But there is a faster way with O(n) time: From the start, we repeatedly insert the current node to the front until we reach the end, i.e.,

Original list:         a --> b --> c --> d
Insert a to front:   b --> a --> c --> d
Insert c to front:   c --> b --> a --> d
Insert d to front:  d --> c --> b --> a
Done.

The overall algorithm takes O(n) time.

Code:

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

class Solution {
public:
    // time: O(N), space: O(1)
    void reorderList(ListNode *head) {
        if (head==NULL || head->next==NULL) return;
        // split list into two halves
        ListNode* slow=head; ListNode* fast=head;
        while(fast!=NULL && fast->next!=NULL) {
            slow=slow->next;
            fast=fast->next->next;
        }

        // Reverse the 2nd half list, slow is head of the 2nd half
        slow=rev(slow);

        // Add 2nd list interleaved to 1st list
        ListNode* cur=head; // don't move head
        ListNode* tmp1=cur->next; ListNode* tmp2=slow->next;

        while(slow!=NULL) {
            tmp1=cur->next; tmp2=slow->next;
            cur->next=slow;
            slow->next=tmp1;
            slow=tmp2;
            cur=tmp1;
        }
        if (tmp1!=NULL) tmp1->next=NULL;
    }

    ListNode* rev(ListNode *head) {
        if (head->next==NULL) return head;
        ListNode* prev=new ListNode(0);
        prev->next=head;
        head=prev;
        ListNode* cur=prev->next;

        while(cur->next!=NULL) {
            ListNode* tmp= cur->next;
            cur->next=tmp->next;
            tmp->next=prev->next;
            prev->next=tmp;
        }
        return prev->next;
    }
};

[LeetCode] Spiral Matrix II

Problem Statement (link):

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Analysis:
This problem is exactly the opposite of Spiral Matrix I, where we peel off the matrix layer by layer. Here, we need to construct the matrix following the same spiral traverse. We use recursion to add layers to matrix from outer layer to inner layers.

The complexity of the algorithm is O(n^2), where n is the given number - largest edge length.

Code:

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int> > mat;
        if (n==0) return mat;
        // construct the matrix
        for (int i=0; i<n; i++)
            mat.push_back(vector<int> (n));
        recur(mat, 1, 0, n);
        return mat;
    }

    // start - start int value of current recursion
    // rec - current number of recursions
    void recur(vector<vector<int> >& mat, int val, int rec, int n) {
        if (val>pow(n,2)) return;
        int l=n-2*rec; // current edge length

        for (int i=rec; i<l+rec; i++)
            mat[rec][i]=val++;
        for (int i=rec+1; i<l+rec; i++)
            mat[i][l+rec-1]=val++;
        for (int i=l+rec-2; i>=rec; i--)
            mat[l+rec-1][i]=val++;
        for (int i=l+rec-2; i>rec; i--)
            mat[i][rec]=val++;

        recur(mat, val, rec+1, n);
    }
};

[LeetCode] Spiral Matrix I

Problem Statement (link):

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Analysis:
Imagine we have a large matrix, this problem asks us to spirally traverse from outer "edges" to inside. We traverse from upper-left to upper-right, to lower-right, to lower-left, to upper-left, then we do the same traversal again on a smaller matrix, which is the "peel-off" version of the original matrix.

How should we control the start and end of each traversal? Aha, we could use recursion on the smaller matrix, repeatedly. In order to generate the smaller matrix for next traversal, we need to "peel off" the previous matrix.

A corner case to be aware of:
- If the matrix has only one row, or only one column, we should return after scanning through the row/column;

The time complexity of this algorithm is O(m*n), where m, n are the dimensions of the matrix.

Code:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> out;
        if (matrix.empty()) return out;
        recur(matrix, out);
        return out;
    }

    void recur(vector<vector<int>> & matrix, vector<int> &out) {
        if (matrix.size()==0) return;

        // special case if matrix has only 1 row/col
        if (matrix.size()==1) {
            for (int i=0; i<matrix[0].size(); i++)
                out.push_back(matrix[0][i]);
            return;
        }
        if (matrix[0].size()==1) {
            for (int i=0; i<matrix.size(); i++)
                out.push_back(matrix[i][0]);
            return;
        }
       
        for (int i=0; i<matrix[0].size(); i++)
            out.push_back(matrix[0][i]);
        for (int i=1; i<matrix.size(); i++)
            out.push_back(matrix[i][matrix[0].size()-1]);
        for (int i=matrix[0].size()-2; i>=0; i--)
            out.push_back(matrix[matrix.size()-1][i]);
        for (int i=matrix.size()-2; i>=1; i--)
            out.push_back(matrix[i][0]);

        // erase the traversed values
        matrix.erase(matrix.end()-1);
        matrix.erase(matrix.begin());
        while(!matrix.empty() && matrix[0].size()==2)
            matrix.erase(matrix.begin());

        for (int i=0; i<matrix.size(); i++) {
            matrix[i].erase(matrix[i].end()-1);
            matrix[i].erase(matrix[i].begin());
        }

        recur(matrix, out);
    }
};

[LeetCode] Restore IP Address

Problem Statement (link):

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Analysis:
There's no specific algorithm used in this problem. I loop through all the possible positions to add dots.

A value IP address is defined such that each three-digits segment is valued between 0 and 255, inclusive. A corner case is that each segment should begin with non-zero digits, i.e., xx.013.xxx.xxx is not a valid segmentation as 013 is invalid.

Code:

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> out;
        if (s.size()<4 || s.size()>12) return out;
        // loop thru all possible positions for adding "."
        for (int i=0; i<s.size()-3; i++) {
            for (int j=i+1; j<s.size()-2; j++) {
                for (int k=j+1; k<s.size()-1; k++) {
                    int a=atoi(s.substr(0,i+1).c_str());
                    string t=to_string(a);
                    if (t!=s.substr(0,i+1)) continue; // to eliminate case where starts with 0

                    int b=atoi(s.substr(i+1,j-i).c_str());
                    t=to_string(b);
                    if (t!=s.substr(i+1,j-i)) continue;

                    int c=atoi(s.substr(j+1,k-j).c_str());
                    t=to_string(c);
                    if (t!=s.substr(j+1,k-j)) continue;

                    int d=atoi(s.substr(k+1,s.size()-k).c_str());
                    t=to_string(d);
                    if (t!=s.substr(k+1,s.size()-k)) continue;

                    if (a<=255 && b<=255 && c<=255 && d<=255)
                        out.push_back(s.substr(0,i+1)+"."+s.substr(i+1,j-i)+"."+s.substr(j+1,k-j)+"."+s.substr(k+1,s.size()-k));
                }
            }
        }
        return out;
    }
};

[LeetCode] Length of Last Word

Problem Statement (link):

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

Analysis:
- Just traverse the char array until you hit NULL.
- Remember to reset the count once you hit a space char, iff it's not the last word.
- The logic I use to determine that it is NOT the last word, where we need to reset the count, is: 1) If current char is space char; 2) If the next char is not space char; 3) If the next char is not NULL.

e.g., string: "ab     cde    "

where we need to reset count when we hit the space before c, we shouldn't reset count when we hit spaces after e.

Code:

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        if (*s==NULL) return 0;
        int len=0;
        const char *cur=s;

        while(*cur!=NULL) {
            if (*cur!=' ')
                len++;
            if (*cur==' ' && *(cur+1)!=' ' && *(cur+1)!=NULL) // if there is a next word
                    len=0;
            cur++;
        }
        return len;
    }
};

[LeetCode] Swap Nodes in Pairs

Problem Statement (link):

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis:
The problem requires to swap node pairs, e.g., swap(node1, node2), swap(node3, node4). So the thing you need to be careful with is when the list has odd number of nodes, you need to stop traversing the list if there's only one node left.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (head==NULL) return NULL;
        ListNode *prev=new ListNode(0); // a pesudo node
        prev->next=head;
        ListNode *newHead=prev;
        ListNode *cur1=head, *cur2=head->next;

        while(cur2!=NULL) {
            cur1=prev->next;
            cur2=cur1->next;
            swap(prev,cur1,cur2);
            if (cur1->next==NULL || cur1->next->next==NULL)
                break;
            prev=prev->next->next;
        }
        return newHead->next;
    }

    void swap(ListNode *prev, ListNode*cur1, ListNode*cur2) {
        ListNode *temp=cur2->next;
        cur2->next=cur1;
        cur1->next=temp;
        prev->next=cur2;
    }
};

[LeetCode] Roman to Interger

Problem Statement (link):

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Analysis:
There isn't so much to say about this problem. Just adding the number together. When the number current char represents is smaller than that of the next char, to calculate the number that these two chars represent, you need to subtract the number that current char represents from that of the next char. e.g., XXIX, the first two X represent 10+10, the next IX represent 10-1, thus the result is 10+10+(10-1)=29.

A comprehensive description of the rules of Roman Numeral is here. Unfortunately, the link is Chinese.

Code:

class Solution {
public:
    int romanToInt(string s) {
        if (s.empty()) return 0;
        int out=0, i=0;
        while (i<s.size()) {
            if (i+1<s.size() && helper(s[i])<helper(s[i+1])) { // the next char exists and it's greater than curr
                out+=helper(s[i+1])-helper(s[i]);
                i++;
            }
            else
                out+=helper(s[i]);
            i++;
        }
        return out;
    }

    int helper(char c) {
        int num=0;
        switch(c) {
            case 'I':
                num=1;
                break;
            case 'V':
                num=5;
                break;
            case 'X':
                num=10;
                break;
            case 'L':
                num=50;
                break;
            case 'C':
                num=100;
                break;
            case 'D':
                num=500;
                break;
            case 'M':
                num=1000;
                break;
            default:
                num=0;
                break;
        }
        return num;
    }
};

[LeetCode] Longest Substring Without Repeating Characters

Problem Statement (link):
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Analysis:
The algorithm is straightforward. We start at the beginning of the string s, for char s[i], we find the longest substr, and move on to the next char s[i+1], repeat.

The interesting part is to choose the best data structure to store the substr's each char as we do need to compare the new char with chars we've seen. I chose unordered_map<string, int> to store and hope the hash map could give me O(1) access each time. I passed all the tests months ago, but now I re-submit the solution, it notified TLE for a rather long string. Apparently, there's collision that drove the complexity beyond O(n), where n is the string length.

Another data structure that fits this problem is array, which provides us O(1) access time. Also, remember that ASCII chars are indexed from 0 to 127. Thus, we could match the ASCII index for each char with our array map, which indicates if we have seen the char before.

Code:
Sol 1: Use unordered_map<string, int>

int lengthOfLongestSubstring(string s) {
    if (s.compare("")==0) return 0;
    int len = s.size();
    int maxLength = 1;
    unordered_map<string, int> table;
    int i = 0;
    while (i<len) {
        table.emplace(s.substr(i,1), i);  // i is the char's location
        for (int j = 1; j < len-i; j++) { // represent the length
            if (table.find(s.substr(i+j, 1)) != table.end()) {   // found the same char, break
                i=table.find(s.substr(i+j,1))->second;
                table.clear();
                break;
            }
            else { // not found - update max length
                maxLength=max(maxLength, j+1);
                table.emplace(s.substr(i+j, 1), i+j);
            }
       }
       i++;
    }
    return maxLength;
}

Sol 2: Use bool arr[128]

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int len=s.size();
        int maxLen=1;
        int i=0;
        while (i<len) {
            bool arr[128]={false}; // to record if any char appeared in ASCII, Unicode has 256 chars
            arr[s[i]]=true;
            for (int j=1; j<len-i; j++) {
                if (arr[s[i+j]]==true) { // found same char
                    break;
                }
                else {
                    maxLen=max(maxLen,j+1);
                    arr[s[i+j]]=true;
                }
            }
            i++;
        }
        return maxLen;
    }
};

Takeaways:
- hash based data structure cannot guarantee O(1) access. If possible, think about using other O(1) structure instead.

[LeetCode] Binary Tree Preorder && Inorder && Postorder Traversal

Tree traversal is quite standard problems. For each of the traversals, both recursive and Iterative methods are described.

Binary Tree Preorder Traversal

Problem Statement (link):

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

Analysis:
Recursive method is trivial as implemented in Sol 1.

In iterative method, a stack is used to store nodes temporarily. In each loop, the current top node in stack is popped and push_back in output vector, then we push its right child and left child in stack if not NULL. The push order is reversed compare to pre-order traversal as stack has the first-in-last-out property. This process continues until the stack is empty.

Code:
Sol 1 - Recursive:

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if (node==NULL) return;
    out.push_back(node->val);
    recur(node->left, out);
    recur(node->right, out);
}

Sol 2 - Iterative:

/**
 * 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<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> nodeS;
        vector<int> valV;
        if (root == NULL) return valV;
        nodeS.push(root);
        while(!nodeS.empty()) {
            TreeNode *node = nodeS.top();
            nodeS.pop();
            valV.push_back(node->val);

            // Note the push order is reversed as the push order is exact reversed of pop order
            if (node->right != NULL) {
                nodeS.push(node->right);
            }
            if (node->left != NULL) {
                nodeS.push(node->left);
            }
        }
        return valV;
    }
};

Binary Tree Inorder Traversal

Problem Statement (link):

Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

Analysis:
A good analysis article about in-order traversal is here.

Recursive method is trivial as implemented in Sol 1.

In the iterative method, a stack is used to store nodes temporarily. We store nodes if it's not NULL, and traverse to its left child; we pop the nodes and store in output vector if current node is NULL, and traverse to its right child. As in Sol 2.

Code:
Sol 1 - Recursive:

vector<int> inorderTraversal(TreeNode *root) {
    vector<int> valV;
    inOrder(root, valV);
    return valV;
}

void inOrder(TreeNode *node, vector<int> &valV) {
    if (node==NULL) return;
    inOrder(node->left, valV);
    valV.push_back(node->val);
    inOrder(node->right, valV);
}

Sol 2 - Iterative:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
using namespace std;
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> output;
        if (root==NULL) return output;
        stack<TreeNode*> nodeS;
        TreeNode* node = root;
        while (node!=NULL || !nodeS.empty()) {
            if(node!=NULL) {
                nodeS.push(node);
                node = node->left;
            }
            else {
                node = nodeS.top();
                nodeS.pop();
                output.push_back(node->val);
                node = node->right;
            }
        }
    }
};

Binary Tree Postorder Traversal

Problem Statement (link):

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

Analysis:
A very good article about the post-order traversal is here.

The recursive solution is trivial as implemented in Sol 1.

In the iterative method, two stacks are used - one stack method exists but a bit complicated. When traversing the tree from left child to right child, we push nodes into a nodeStack, then pop each node into outputStack. See Sol 2 below.

Code:
Sol 1: Recursive

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> out;
    recur(root, out);
    return out;
}
void recur(TreeNode *node, vector<int>& out) {
    if(node==NULL) return;
    recur(node->left, out);
    recur(node->right, out);
    out.push_back(node->val);
}

Sol 2: Iterative

/**
 * 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<int> postorderTraversal(TreeNode *root) {
        vector<int> output;
        if (root==NULL) return output;
        // use two stacks
        stack<TreeNode *> nodeStack;
        stack<TreeNode *> outputStack;
        TreeNode* node = root;
        nodeStack.push(node);
        while(!nodeStack.empty()) {
            node = nodeStack.top();
            outputStack.push(node);
            nodeStack.pop();
            if (node->left != NULL) nodeStack.push(node->left);
            if (node->right != NULL) nodeStack.push(node->right);
        }
        while(!outputStack.empty()) {
            node = outputStack.top();
            output.push_back(node->val);
            outputStack.pop();
        }
    }
};

[LeetCode] Two Sum

Problem Statement (link):

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:
The naive approach is to scan every pairs, which requires O(n^2) --> TLE.

Consider using map, which has O(log n) time complexity. For each number, we need to find if there's another number such that the two add up to the target number. The search is O(log n).

A corner case we need to consider is: e.g., if target==6, and there's only one 3 in vector<int> numbers, we need to eliminate the index of current position i (see code below).

The overall algorithm complexity is O(n logn). For a detail comparison of std::map and std::unordered_map, please see the Note below.

Code:

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> out;
        if (numbers.size()<2) return out;
            map<int, int> map;
            // Create map
            for (int i=0; i<numbers.size(); i++) {
                map[numbers[i]]=i;
            }
            // Find if the pair exists
            for (int i=0; i<numbers.size(); i++) {
                int diff=target-numbers[i];
                // found in hashmap && it's a differnt element
                if (map.find(diff)!=map.end() && map.find(diff)->second!=i) {
                    out.push_back(i+1);
                    out.push_back(map[diff]+1);
                    return out;
                }
            }
        return out;
    }
};

Note:

std::map vs. std::unordered_map

	std::map	std::unordered_map
Element ordering	ordered	Un-ordered
Implementation in C++11	Red-black tree (or balanced tree)	Hash table
Search time complexity	O(log(n))	O(1) if no hash collisions Up to O(n) if there are collisions
Insertion time complexity	O(log(n)) + re-balance	Same as search
Deletion time complexity	O(log(n)) + re-balance	Same as search
Need hash function	No	Yes
Space utilization	Use less memory (just pointers)	Use more memory
Common use cases	When good hash is not possible or too slow. Or when order is required	Other cases

[LeetCode] Add Two Numbers

Problem Statement (link):

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:
This problem is quite straight-forward: we traverse the linked list and add corresponding node's values from two given lists to form a new list.

There are several corner cases to consider:
1) Two lists may have different length: we need to consider the extra nodes from longer list.
2) Carry: we need to remember the carry - 1 or 0 - from previous node(s). If it's end of the list and there's a carry, we need to create a new node with value 1.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (l1==NULL && l2==NULL) return NULL;
        ListNode* h1=l1, *h2=l2;
        // add first node
        ListNode* l3=new ListNode((h1->val+h2->val)%10);
        int carry=(h1->val+h2->val>=10)?1:0;
        h1=h1->next; h2=h2->next;
        ListNode* prev=l3;
        // traverse
        while(h1!=NULL && h2!=NULL) {
            ListNode* tmp=new ListNode((h1->val+h2->val+((carry==1)?1:0))%10);
            carry=(h1->val+h2->val+((carry==1)?1:0)>=10)?1:0;
            prev->next=tmp;
            prev=prev->next;
            h1=h1->next;
            h2=h2->next;
        }
        // If list 1 is longer than list 2
        if (h1!=NULL) {
            while(h1!=NULL) {
                ListNode* tmp=new ListNode((h1->val+((carry==1)?1:0))%10);
                carry=(h1->val+((carry==1)?1:0)>=10)?1:0;
                prev->next=tmp;
                prev=prev->next;
                h1=h1->next;
            }
        }
        // If list 2 is longer than list 1
        if (h2!=NULL) {
            while(h2!=NULL) {
                ListNode* tmp=new ListNode((h2->val+((carry==1)?1:0))%10);
                carry=(h2->val+((carry==1)?1:0)>=10)?1:0;
                prev->next=tmp;
                prev=prev->next;
                h2=h2->next;
            }
        }
        // If there's carry at the last node - create a new node->val=1
        if (h1==NULL && h2==NULL && carry==1) {
            ListNode* tmp=new ListNode(1);
            prev->next=tmp;
        }
        return l3;
    }
};

[LeetCode] Triangle

Problem Statement (link):

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Analysis:
This problem is similar to find-shortest-path problem, it's obvious a DP.

I tried DFS first - as in Sol 1, using an int to store the smallest sum we got so far, even though it uses O(1) space, it has O(n^2) time complexity and overlapped sub-problems.

I turned to DP. It is obvious we can use a 2-D dp matrix to record all the smallest sum up to some number, where dp[i][j] record the smallest sum to j-th entry of i-th vector in triangle. However, the problem asks for O(n) space complexity.

Think about bottom-up approach instead. We use a length-n dp vector to record the smallest sum up to some number as well, where n is length of triangle. But this time, we update/re-use the dp vector iteratively as we scan through the triangle toward the pinnacle. Thus, for triangle[i], we only need the first [0 : i] of the vector.

How about the transition function? Well, except for the bottom row, where dp[i] equals each entry of the vector, we compute the new dp[i] by adding the number itself to the smallest value of its adjacent two number in the row below. We repeat this process until we reach the pinnacle. See Sol 2 for code.

Code:
Sol 1 - DFS (TLE)

int minimumTotal(vector<vector<int> > &triangle) {
    if (triangle.empty()) return 0;
    int n=triangle.size();
    //vector<int> minVec(n,INT_MAX);
    int m=INT_MAX;
    recur(triangle, m, 0, 0, 0);
    return m;
}
// i-row num; j-index in each vector
void recur(vector<vector<int>>& triangle, int& m, int val, int i, int j) {
    if (i==triangle.size()) {
        m=min(m,val);
        return;
    }
    recur(triangle, m, triangle[i][j]+val, i+1, j);
    recur(triangle, m, triangle[i][j]+val, i+1, j+1);
}

Sol 2 - DP

class Solution {
public:
    // try 2 - DP
    int minimumTotal(vector<vector<int> >&triangle) {
        if (triangle.empty()) return 0;
        vector<int> dp(triangle.size(), INT_MAX); // dp vector-reuse on every row
        // Build bottom up
        for (int i=triangle.size()-1; i>=0; i--) {
            for (int j=0; j<triangle[i].size(); j++) {
                if (i==triangle.size()-1) // The initial condition
                    dp[j]=triangle[i][j];
                else
                    dp[j]=triangle[i][j]+min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
};