[Leetcode] Gray Code

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:

    vector<int> grayCode(int n) {
  
        vector<int> codes(1,0);
        for (int i = 0; i<n; i++)
        {
            for (int j=codes.size()-1; j >=0 ; j--)
            {
                int code = 0x1 << i | codes[j];
                codes.push_back(code);
            }
        }
        
        return codes;
    }

[Leetcode] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:

    bool helper(TreeNode *root, int minVal, int maxVal) {
        if (root == NULL)
            return true;
        else
            return root->val < maxVal && 
            root->val > minVal &&
            helper(root->left, minVal, root->val) &&
            helper(root->right, root->val, maxVal);
        
    }

    bool isValidBST(TreeNode *root) {
        return helper(root, INT_MIN, INT_MAX);
    }
};

[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

For BST, the inorder traversal will get the list of elements in sorted order. If two elements were swapped, there are two cases, the elements are next to each other or not. 

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

Doing an inorder traversal and the elements are marked as p1 and p2 if current element is less than previous element.   

class Solution {
public:

    void helper(TreeNode *root, TreeNode* &prev, TreeNode* &p1, TreeNode* &p2) {
        if (root == NULL)
            return;
        
        helper(root->left, prev, p1, p2);
            
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL)
            {
                p1 = prev;
                p2 = root;
            }
            else
            {
                p2 = root;
            }
        }
        
        prev = root;
        
        helper(root->right, prev, p1, p2);
    }

    void recoverTree(TreeNode *root) {
        TreeNode *prev = NULL;
        TreeNode *p1 = NULL;
        TreeNode *p2 = NULL;
        
        helper(root, prev, p1, p2);
        
        swap(p1->val, p2->val);
    }
};

[Leetcode] Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Analysis:

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL && q == NULL)
            return true;
        else if (p == NULL || q == NULL)
            return false;
        else
        {
            return p->val == q->val && 
            isSameTree(p->left, q->left) &&
            isSameTree(p->right, q->right);
        }
    }
};

[Leetcode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:

    bool helper(TreeNode *left, TreeNode* right) {
        if (left == NULL && right == NULL)
            return true;
        else if (left == NULL || right == NULL)
            return false;
        else
        {
            return left->val == right->val 
            && helper(left->left, right->right)
            && helper(left->right, right->left);
        }
    }
    bool isSymmetric(TreeNode *root) {
        if (root == NULL)
            return true;
        else
            return helper(root->left, root->right);
    }
};

[Leetcode] Binary Tree Level Order Traversal

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]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            row.push_back(t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                currLevel = nextLevel;
                nextLevel = 0;
                ret.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};

[Leetcode] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        int level = 1;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            if (level % 2 == 1)
                row.push_back(t->val);
            else
                row.insert(row.begin(), t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                level++;
                currLevel = nextLevel;
                nextLevel = 0;
                ret.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};

[Leetcode] Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Analysis:

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root == NULL)
            return 0;
        else
        {
            return max(maxDepth(root->left), maxDepth(root->right)) + 1;
        }
    }
};

[Leetcode] Binary Tree Level Order Traversal II

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]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            row.push_back(t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                currLevel = nextLevel;
                nextLevel = 0;
                ret.insert(ret.begin(), row);
                row.clear();
            }
        }
        
        return ret;
    }
};

[Leetcode] Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

class Solution {
public:

    TreeNode *helper(vector &num, int b, int e) {
        if (b > e)
            return NULL;
        else
        {
            //middle as the root and recursively to construct the tree left and right
            int mid = (b+e)/2;
            TreeNode* root = new TreeNode(num[mid]);
            root->left = helper(num, b, mid - 1);
            root->right = helper(num, mid+1, e);
            return root;
        }
    }

    TreeNode *sortedArrayToBST(vector &num) {
        return helper(num, 0, num.size() - 1);
    }
};

[Leetcode] Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

class Solution {
public:

    TreeNode *sortedListToBST(ListNode *head) {
        if (head == NULL)
            return NULL;
        
        if (head->next == NULL)
            return new TreeNode(head->val);
        
        //use fast and slow pointer to get the middle
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //divide the list into two part
        prev->next = NULL;
        //middle as the root
        TreeNode* root = new TreeNode(slow->val);
        //recursively convert the left and right node
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

[Leetcode] Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Analysis:

Try to get the tree height and do the balance comparison in the same function to be more efficient.

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

    int helper(TreeNode *root, bool& isBalanced)
    {
        if (root == NULL)
            return 0;
        else
        {
            int leftHeight = helper(root->left, isBalanced);
            int rightHeight = helper(root->right, isBalanced);
            if (abs(leftHeight - rightHeight) > 1)
                isBalanced = false;
                
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode *root) {
        bool isBalanced = true;
        helper(root, isBalanced);
        return isBalanced;
    }
};

[Leetcode] Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL)
            return 0;
        else if (root->left == NULL)
            return minDepth(root->right) + 1;
        else if (root->right == NULL)
            return minDepth(root->left) + 1;
        else
            return min(minDepth(root->left), minDepth(root->right)) + 1;
            
    }
};

[Leetcode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL)
            return false;
        else if (root->left == NULL && root->right == NULL)
            return sum == root->val;
        else
            return hasPathSum(root->left, sum - root->val) ||
                hasPathSum(root->right, sum - root->val);
    }
};

[Leetcode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis:

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

    void helper(TreeNode *root, int sum, vector<vector<int> >& ret, vector<int>& nums)
    {
        if (root == NULL)
            return;
        //have to be leaft
        else if (root->left == NULL && root->right == NULL && sum == root->val)
        {
            //leaf number was not pushed yet
            nums.push_back(root->val);
            ret.push_back(nums);
            nums.pop_back();
        }
        else
        {
            nums.push_back(root->val);
            helper(root->left, sum - root->val, ret, nums);
            helper(root->right, sum - root->val, ret, nums);
            nums.pop_back();
        }
    }

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > ret;
        vector<int> nums;
        helper(root, sum, ret, nums);
        
        return ret;
    }
};

[Leetcode] Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Analysis:

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

    void helper(TreeNode *root, TreeNode*& lastVisited) {
        if (root == NULL)
            return;
        //preorder, the root->right will be overrided when calling helper(root->left, lastVisited)
        //need to be saved
        TreeNode* right = root->right;
            
        if (lastVisited != NULL)
        {
            lastVisited->left = NULL;
            lastVisited->right = root;
        }
        //remember last visited
        lastVisited = root;
        
        helper(root->left, lastVisited);
        helper(right, lastVisited);
    }

    void flatten(TreeNode *root) {
        TreeNode* lastVisited = NULL;
        helper(root, lastVisited);
    }
};

[Leetcode] Populating Next Right Pointers in Each Node

iven a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Analysis:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL || (root->left == NULL && root->right == NULL))
            return;
        root->left->next = root->right;
        if (root->next != NULL)
            root->right->next = root->next->left;
        
        connect(root->right);
        connect(root->left);
        
    }
};

[Leetcode] Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Analysis:

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > ret;
        for(int i=0; i<numRows; i++)
        {
            vector<int> row;
            for(int j=0; j<=i; j++)
            {
                //first and last one is 1, others are the sum of current and last pos of last line
                if (j == 0 || j == i)
                    row.push_back(1);
                else
                    row.push_back(ret[i-1][j] + ret[i-1][j-1]);
            }
            ret.push_back(row);
        }
        return ret;
    }
};

[Leetcode] Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Analysis:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret(rowIndex+1, 1);
        for(int i=0; i<=rowIndex; i++)
        {
            int last  = 1;
            for(int j=0; j<=i; j++)
            {
                if (j == 0 || j == i)
                    ret[j] = 1;
                else
                {
                    //remember the current value before it is overrided
                    int tmp = ret[j];
                    ret[j] += last;
                    last = tmp;
                }
            }
        }
        
        return ret;
    }
};

[Leetcode] Triangle

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:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        vector<int> ret(triangle.back().size() + 1, 0);
        for(int i=triangle.size()-1; i>=0; i--)
        {
            for(int j = 0; j < triangle[i].size(); j++)
            {
                ret[j] = min(ret[j], ret[j+1]) + triangle[i][j]; 
            }
        }
        
        return ret[0];
    }
};

[Leetcode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Analysis:

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

    int helper(TreeNode* root, int& maxSum)
    {
        if (root == NULL)
            return 0;
        else
        {
            int leftSum = helper(root->left, maxSum);
            int rightSum = helper(root->right,maxSum);
            
            int sum = root->val;
            if (leftSum > 0)
                sum += leftSum;
            if (rightSum > 0)
                sum += rightSum;
            
            maxSum = max(maxSum, sum);
            
            return max(leftSum, rightSum) > 0 ? max(leftSum, rightSum) + root->val : root->val;
        }
    }

    int maxPathSum(TreeNode *root) {
        int sum = INT_MIN;
        helper(root, sum);
        
        return sum;
    }
};

[Leetcode] Valid Palindrome

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:

class Solution {
public:

    bool isAlphanumeric(char c)
    {
        if ((c >= 'a' && c <='z') ||
            (c >= 'A' && c <= 'Z') ||
            (c >= '0' && c <= '9'))
            return true;
        return false;
    }

    bool isPalindrome(string s) {
        int i=0;
        int j = s.size() - 1;
        while(i < j)
        {
            if (!isAlphanumeric(s[i]))
            {
                i++;
                continue;
            }

            if (!isAlphanumeric(s[j]))
            {
                j--;
                continue;
            }

            if (toupper(s[i]) != toupper(s[j]))
                return false;
            
            i++;
            j--;
        }
        
        return true;
    }
};

[Leetcode] Sum Root to Leaf Numbers

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:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void helper(TreeNode *root, int& sum, int s)
    {
        if (root == NULL)
            return;
        else if (root->left == NULL && root->right == NULL)
            sum += (s*10 + root->val);
        else
        {
            helper(root->left, sum, s*10 + root->val);
            helper(root->right, sum, s*10 + root->val);
        }    
    }
    
    int sumNumbers(TreeNode *root) {
        int sum = 0;
        helper(root, sum, 0);
        
        return sum;
    }
};

[Leetcode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Analysis:

• If s has only character, s could be break if s[0] is a word.
• If s has two characters, s could be break if both s[0] and s[1] are the word or s.substr(0,2) is a word.
• if s has If s has two characters, s could be break if there exist a j (0<=j<i) such that s.substr(0, j) could be break and s.substr(j, i-j+1) is a word. Notice that we only need to know whether  s.substr(0, j) could be break and don't care how it is break.

Let canBreak[i] to indicate whether s.substr(0,i) could be break

    bool wordBreak(string s, unordered_set<string> &dict) {
        //indicate whether the substr(s, 0, i) could be breaked into words
        vector<bool> canBreak(s.size(), false);
        for(int i=0; i<s.size(); i++)
        {
            //either the whole string is a word
            if(dict.find(s.substr(0, i+1)) != dict.end())
                canBreak[i] = true;
            else
            {
                //or substr1 can be breaked and substr2 is a word
                for(int j=0; j<i; j++)
                {
                    if (canBreak[j] && dict.find(s.substr(j+1, i-j)) != dict.end())
                    {
                        canBreak[i] = true;
                        break;
                    }
                }
            }
        }
        
        return canBreak[s.size()-1];
    }

[Leetcode] Longest Substring Without Repeating Characters

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:
If there are duplicate characters closed to current position than j, the substring without repeating characters should start from pos+1

    int lengthOfLongestSubstring(string s) {
        map<char, int> m;
        int j = 0;
        int maxLen = 0;
        for(int i=0; i<s.size(); i++)
        {
            if (m.find(s[i]) != m.end() && m[s[i]] >= j)
            {
                j = m[s[i]] + 1;
            }
            m[s[i]] = i;
            maxLen = max(maxLen, i-j+1);
        }
        return maxLen;
    }

[Leetcode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Analysis:

Let p be the product of all numbers in the array.

If p > 0, the largest product is p.

If p == 0, there must be at least one 0 in the array. The array should be something like [x1, 0, x2, 0, x3...], where x1, x2, x3 is a subarray containing no 0s. So, the largest product is maximum of largest product of x1, x2, x3 and 0. We can iterate the array and maintain the product of numbers and reset the product to be 1 when an 0 encountered. 

If p < 0, there must be odd number of negative elements.  The array should be something like [x1, -y1, x2, -y2, x3...], where x1, x2, x3 is a subarray containing no negative numbers. Since the number of negative element is odd in the array, product of x1 and product of [x2, -y2, x3, ...] must be positive and could be the potential largest product. Product of x1 could be calculated by iterating x1 and product of [x2, -y2, x3, ...] could be calculated by reverse iterating. 

Thus, the largest product must be the product of subarray between 0s (if there are 0s) and the left and right subarray of the negative elements. 

    int maxProduct(int A[], int n) {
        int maxProd = INT_MIN;
        int prod = 1;
        for(int i=0; i <n; i++)
        {
            prod = prod * A[i];
            maxProd = max(maxProd, prod);
            if (A[i] == 0)
                prod = 1;
        }
        
        prod = 1;
        for(int i=n-1; i >=0; i--)
        {
            prod = prod * A[i];
            maxProd = max(maxProd, prod);
            if (A[i] == 0)
                prod = 1;
        }
        
        return maxProd;
    }

[Leetcode] Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Analysis:

From the example, we observed that the permutations can be divided into n groups, each beginning with degit 1 <=i <=n and the first digit must be i = k/(n-1)!

Similarly, the position of k in the group is k % (n-1)! and the remaining numbers are divided into n-1 groups and the first digit must be i = (k % (n-1)!)/(n-2)!.

Loop until all the numbers are set.

    string getPermutation(int n, int k) {
     vector<int> nums;
     //set an array with all numbers
     for (int i = 0; i<n; i++)
      nums.push_back(i + 1);
        
        //get (n-1)!
     int nn = 1;
     for (int i = 1; i < n; i++)
      nn = nn * i;
    
     string str;
     int kk = k - 1;
     while (n > 1)
     {
         //the kth permutation is at (k-1)/(n-1)! group
      int pos = kk / nn;
      str.push_back(nums[pos] + '0');
      //the number has been used, removed it from the array
      nums.erase(nums.begin() + pos);
      //the position in the group is at (k-1) % (n-1)!
      kk = kk % nn;
      //the number of permutations in the group is (n-2)!
      n = n - 1;
      nn = nn / n;
     }
     str.push_back(nums[0] + '0');
     return str;
    }

[Leetcode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Analysis:

• Take the given example, we know the length of the list is 5 and the position to split the list is 3, then we can rotate the list by splitting the list between 3 and 4 and linking the tail and head of the list. The steps would be:

1. Get the length of the list, l and the tail of the list tail
2. Get the position p1 and p2 to split the list at l - k%l since k may be greater than l
3. Get the new head by setting p1->next = NULL, tail->next = head and newhead = p2
4. Note: if k%l == 0, simply return the head

ListNode *rotateRight(ListNode *head, int k) {
        if (head == NULL)
            return head;
        int len = 0;
        ListNode* curr = head;
        ListNode* tail = NULL;
        while(curr != NULL)
        {
            len++;
            tail = curr;
            curr = curr->next;
        }
        //Note:len could not be 0
        int pos = len - k % len;
        if (pos == len)
            return head;
        curr = head;
        ListNode* prev = NULL;
        for(int i=0; inext;
        }
        
        ListNode* newhead = curr;
        if (prev != NULL) {
            prev->next = NULL;
            tail->next = head;
        }
        
        return newhead;
    }

[Leetcode] Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Analysis:

Let f[i][j] be the minimum number of steps required to convert word1 of size i to word2 of size j. The last character of word1 may or may not be equal to the one of word2. 

Case1: considering word1 (Xa) and word2 (Ya). Since the last character of word1 is equal to the last character of word2, deleting the last character of both would not change the steps converting word1 to word2, that is, f[i][j] = f[i-1][j-1].

Case 2: Considering word1 (Xa) and word2 (Yb). Since last character of word1 is NOT equal to the last character of word2, to convert word1 to word2, there are 3 ways to convert word1 to word2 and the minimum one is the one we wanted:

• Replace the character a with b of word1, so that word1(Xb) and word2(Yb). so the steps will become f[i][j] = f[i-1][j-1] + 1
• Insert character b to word1, so that word1(Xab) and word2(Yb) and according to case1, so deleting b would make the steps become f[i][j] = f[i][j-1] + 1
• Insert character a to word2, so that word1(Xb) and word2(Yba) and according to case1, so deleting a would make the steps become f[i][j] = f[i-1][j] + 1

We have f[i][j] = min(min(f[i][j-1], min(f[i-1][j]), f[i-1][j-1])

If word1 is empty, f[0][j] = j and if word2 is empty, f[i][0] = i

Given the above equation, it is pretty easy to have the code.  

    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > f(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; i++)
        {
            for(int j=0; j<=n; j++)
            {
                if (i == 0)
                    f[i][j] = j;
                else if (j == 0)
                    f[i][j] = i;
                else
                {
                    if (word1[i-1] == word2[j-1])
                        f[i][j] = f[i-1][j-1];
                    else
                        f[i][j] = min(min(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + 1;
                }
            }
        }
        
        return f[m][n];
        
    }