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