Remove Nth Node From End of List

Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Idea: use a ring buffer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode **buffer = new ListNode*[n + 1];
        memset(buffer, NULL, (n + 1) * sizeof(ListNode*));
        int ptr = 0;
        ListNode *current = head;
        
        while (current) {
            buffer[ptr] = current;
            ptr = (ptr + 1) % (n + 1);
            current = current->next;
        }
        
        if (buffer[ptr] == NULL) {
            head = n > 1 ? buffer[1] : NULL;
        }
        else {
            ListNode *last = buffer[ptr];
            last->next = last->next->next;
        }
        delete[] buffer;
        return head;
    }
};

Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (A == NULL || n == 0) return 0;
        int i = 1, j = 1, count = 1;
        
        while (j < n) {
            if (A[j] != A[j - 1]) {
                A[i] = A[j];
                ++i;
                count = 1;
            }
            else if (A[j] == A[j - 1] && count < 2) {
                A[i] = A[j];
                ++i;
                ++count;
            }
            else {
                ++count;
            }
            ++j;
        }
        
        return i;
    }
};

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (A == NULL || n == 0) return 0;
        int i = 1, j = 1;
        
        while (j < n) {
            if (A[j] != A[j - 1]) {
                A[i] = A[j];
                i++;
            }
            j++;
        }
        
        return i;
    }
};

Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

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.

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) return NULL;
        ListNode *fast = head->next, *slow = head;
        int lastVal = head->val;
        
        while (fast) {
            if (fast->val != lastVal) {
                slow->next->val = fast->val;
                slow = slow->next;
            }
            lastVal = fast->val;
            fast = fast->next;
        }
        slow->next = NULL;
        
        return head;
    }
};

Maximum Subarray

Maximum Subarray

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

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!A || !n) return 0;
        int m = A[0];
        int sumSoFar = 0;
        
        for (int i = 0; i < n; ++i) {
            sumSoFar += A[i];
            if (sumSoFar > m) {
                m = sumSoFar;
            }
            if (sumSoFar < 0) {
                sumSoFar = 0;
            }
        }
        
        return m;
    }
};

Length of Last Word

Length of Last Word

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.

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int count = 0;
        bool recount = true;
        
        while (*s != '\0') {
            if (*s != ' ') {
                if (recount) {
                    count = 1;
                    recount = false;
                }
                else {
                    ++count;
                }
            }
            else {
                recount = true;
            }
            ++s;
        }
        
        return count;
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int end = inorder.size() - 1;
        if (end < 0) return NULL;
        return getRoot(inorder, postorder, 0, end, postorder[end], 0);
    }
    
    TreeNode *getRoot(vector &inorder, vector &postorder,
                 int start, int end, int rootVal, int offset) {
        if (start > end) return NULL;
        
        TreeNode *root = new TreeNode(rootVal);
        
        int rootPosInOrder = start;
        for (; rootPosInOrder < end; ++rootPosInOrder) {
            if (inorder[rootPosInOrder] == rootVal) break;
        }
        
        root->left = getRoot(inorder, postorder, start,
               rootPosInOrder - 1, postorder[rootPosInOrder - 1 + offset], offset);
        root->right = getRoot(inorder, postorder, rootPosInOrder + 1,
              end, postorder[end - 1 + offset], offset - 1);
        return root;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int end = inorder.size() - 1;
        if (end < 0) return NULL;
        return getRoot(inorder, postorder, 0, end, 0);
    }
    
    TreeNode *getRoot(vector &inorder, vector &postorder, int start, int end, int offset) {
        if (start > end) return NULL;
        
        int rootVal = postorder[end + offset];
        TreeNode *root = new TreeNode(rootVal);
        
        int rootPosInOrder = start;
        for (; rootPosInOrder < end; ++rootPosInOrder) {
            if (inorder[rootPosInOrder] == rootVal) break;
        }
        
        root->left = getRoot(inorder, postorder, start, rootPosInOrder - 1, offset);
        root->right = getRoot(inorder, postorder, rootPosInOrder + 1, end, offset - 1);
        return root;
    }
};

Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II

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.

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *fast = head, *slow = NULL, *last = NULL, *newhead = NULL;
        int count = 1;
        
        while (fast) {
            if (last && fast->val == last->val) {
                ++count;
            }
            else if (last && fast->val != last->val) {
                if (count == 1) {
                    if (!slow) {
                        slow = last;
                        newhead = slow;
                    }
                    else {
                        slow->next = last;
                        slow = slow->next;
                    }
                }
                else {
                    count = 1;
                }
            }
            
            last = fast;
            fast = fast->next;
        }
        
        //check if the final node in the original list needs to be added
        if (last && slow && last->val != slow->val && count == 1) {
            slow->next = last;
            slow = slow->next;
        }
        else if (!slow && last && count == 1) {
            //only one node
            return last;
        }
        
        //close the new list
        if (slow) {
            slow->next = NULL;
        }
        
        return newhead;
    }
};

Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

Idea: use a hashmap to store the previous computed results

public class Solution {
    public String countAndSay(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (n == 0) return "";
        String str = "1";
        HashMap map = new HashMap();
        for (int i = 1; i < n; ++i) {
            int start = 0;
            StringBuffer newstr = new StringBuffer();
            for (int j = 0; j < str.length(); ++j) {
                if (j != str.length() - 1 && str.charAt(j) == str.charAt(j+1)) {
                    continue;
                }
                String stored = map.get(str.substring(start, j+1));
                if (stored == null) {
                    String strappend = String.valueOf(j - start + 1) + str.substring(start, start + 1);
                    map.put(str.substring(start, j+1), strappend);
                    newstr.append(strappend);
                }
                else {
                    newstr.append(stored);
                }
                start = j + 1;
            }
            str = newstr.toString();
        }
        return str;
    }
}

Edit Distance

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n1 = word1.size();
        int n2 = word2.size();
        
        if (n1 == 0) {
            return n2;
        }
        else if (n2 == 0) {
            return n1;
        }
        
        vector >dp;
        dp.resize(n1 + 1);
        for (int i = 0; i <= n1; ++i) {
            dp[i].resize(n2 + 1);
        }
        
        for (int i = 0; i <= n1; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n2; ++j) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1,
                        dp[i-1][j-1] + 1);
                }
            }
        }
        
        return dp[n1][n2];
    }
};

Balanced Binary Tree

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.

» Solve this problem

Complexity: O(n)

/**
 * 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 isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rootDepth = 0;
        return _isBalanced(root, rootDepth);
    }
    
    bool _isBalanced(TreeNode *root, int& depth) {
        if (!root) return true;
        
        int leftDepth = depth + 1;
        int rightDepth = depth + 1;
        bool subTreeResult = _isBalanced(root->left, leftDepth)
            && _isBalanced(root->right, rightDepth);
            //trigger recursion first to avoid computation of depth
            //until we reach the leaf node
        
        depth = max(leftDepth, rightDepth);
           //recursively update parent depth, bottom-up 
        if (subTreeResult && abs(leftDepth - rightDepth) <= 1) {
            return true;
        }
        else {
            return false;
        }
    }
};

Convert Sorted List to Binary Search Tree

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.

» Solve this problem

Complexity: O(n^2)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = 0;
        ListNode *node = head;
        while (node) {
            ++n;
            node = node->next;
        }
        return toBST(head, n);
    }
    
    // n - the total number of nodes needs processing
    TreeNode *toBST(ListNode *head, int n) {
        if (!head || n <= 0) return NULL;
        
        int mid = n / 2;
        ListNode *midNode = head;
        for (int i = 0; i < mid; ++i) {
            midNode = midNode->next;
        }
        
        TreeNode *root = new TreeNode(midNode->val);
        root->left = toBST(head, mid);
        root->right = toBST(midNode->next, n - mid - 1);
        return root;
    }
};

Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

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

» Solve this problem

Complexity: O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return toBST(num, 0, num.size() - 1);
    }
    
    TreeNode *toBST(vector &num, int start, int end) {
        if (end < start) {
            return NULL;
        }
        
        int mid = (start + end) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = toBST(num, start, mid - 1);
        root->right = toBST(num, mid + 1, end);
        return root;
    }
};

Binary Tree Maximum Path Sum

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.

This could be solved using DP. For each node, the max sum path for its parent could be from its left (1) or right subtree (2) through itself or only itself (3) to its parent node (_maxSubPathSum). For the global max sum, it could be the sum of a node's left subtree through the node itself to its right subtree(4), plus the above 3 cases.
Time Complexity: O(n)

/**
 * 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 maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root) return 0;
        
        int m = root->val;
        int localMax = _max(root, m);
        return localMax > m ? localMax : m;
    }
    
    int _max(TreeNode *root, int &m) {
        if (!root) return 0;
        int leftMax = _max(root->left, m);
        int rightMax = _max(root->right, m);
        
        int maxSum = max(root->val, max(root->val + leftMax, root->val + rightMax));
        m = max(max(m, maxSum), root->val + leftMax + rightMax);
        
        return maxSum; 
            
    }
};

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

» Solve this problem

Idea: The best choice could be the max of: do nothing / one more transaction based on the previous result on day j where j < i and at most one transaction was made before day j

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = prices.size();
        if (n <= 1) return 0;
        
        int minp = prices[0];
        int *dp = new int[n];
        int *dp1 = new int[n]; //max profit with one or less transaction
        
        memset(dp, 0, n*sizeof(int));
        memset(dp1, 0, n*sizeof(int));
        
        for (int i = 1; i < n; i++) {
            if (prices[i] < minp) minp = prices[i];
            dp1[i] = max(dp1[i-1], prices[i] - minp);
            if (prices[i] <= prices[i-1]) {
                dp[i] = dp[i-1];
                continue;
            }
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], dp1[j] + prices[i] - prices[j]);
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        return dp[n-1];
    }
};

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

» Solve this problem

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = prices.size();
        if (n <= 1) return 0;
        int *dp = new int[n];
        memset(dp, 0, n*sizeof(int));
        
        for (int i = 1; i < n; ++i) {
            if (prices[i] <= prices[i-1]) {
                dp[i] = dp[i - 1];
                continue;
            }
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], dp[j] + prices[i] - prices[j]);
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        return dp[n - 1];
    }
};

Flatten Binary Tree to Linked List

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

Pre-order Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (root == null) return;
        Stack stack = new Stack();
        stack.push(root);
        TreeNode lastNode = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (lastNode != null) {
                lastNode.left = null;
                lastNode.right = node;
            }
            lastNode = node;
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
        }
    }
}

Palindrome Number

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Be aware of overflow problem.

class Solution {
public:
    bool isPalindrome(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x < 0) return false;
        int digits = 1;
        int tester = 1;
        while (x / tester >= 10) {
            tester*=10;
            digits++;
        }
        
        while (x > 0) {
            if (x / tester == x % 10) {
                x -= x / tester * tester;
                x /= 10;
                tester /= 100;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

4 Sum

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

public class Solution {
    public ArrayList> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = 0; i < num.length - 3; i++) {
            int a = num[i];
            for (int j = i + 1; j < num.length - 2; j++) {
                int b = num[j];
                int k = j + 1;
                int l = num.length - 1;
                while (k < l) {
                    int c = num[k];
                    int d = num[l];
                    if (a + b + c + d == target) {
                        ArrayList sublist = new ArrayList();
                        sublist.add(a);
                        sublist.add(b);
                        sublist.add(c);
                        sublist.add(d);
                        list.add(sublist);
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                    else if (a + b + c + d < target) {
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                    }
                    else {
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                }
                
                while (j + 1 < num.length - 2 && num[j + 1] == num[j]) {
                    j++;
                }
            }
            
            while (i + 1 < num.length - 3 && num[i + 1] == num[i]) {
                i++;
            }
        }
        
        return list;
    }
}

3 Sum Closest

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList> list = new ArrayList>();
        
        Integer closest = null;
        
        for (int i = 0; i <= num.length - 3; i++) {
            int a = num[i];
            int j = i+1;
            int k = num.length - 1;
            if (closest == null) closest = a + num[j] + num[k];
            
            int best = closest.intValue();
            
            while (j < k) {
                int b = num[j];
                int c = num[k];
                if (a + b + c == target) {
                    return a + b + c;
                }
                else if (a + b + c < target) {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    j++;
                }
                else {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    k--;
                }
            }
            
            if (Math.abs(best - target) < Math.abs(closest.intValue() - target)) {
                closest = best;
            }
        }
        
        return closest.intValue();
    }
    
}