Remove Duplicates from Sorted Array

Problem:

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

Solution:

class Solution {

public:

    int removeDuplicates(int A[], int n) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        int iter = 0;

        if (n == 0)

            return 0;

        for (int i = 0; i < n - 1; i++) {

            if (A[i] != A[i+1])

                A[iter++] = A[i];

        }

        A[iter++] = A[n - 1];

        return iter;

    }

};

==== Second time ====

class Solution {

public:

    int removeDuplicates(int A[], int n) {

        int result = 0;

        if (n == 0)

            return result;

        for (int i = 0; i < n; i++) {

            if (A[i] != A[result]) {

                result++;

                A[result] = A[i];

            }

        }

        return result + 1;

    }

};

==== Third time =======

int removeDuplicates(vector<int>& nums) {
        int ans = 1, iter = 0;
        if (nums.size() == 0) {
            return 0;
        }
        
        int num_comp = nums[iter];
        for (iter = 1; iter < nums.size(); iter++) {
            if (nums[iter] != num_comp) {
                nums[ans++] = nums[iter];
                num_comp = nums[iter];
            }
        }
        
        return ans;
    }

=============

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        int cur = 1;

        int prev = 0;

        if (nums.size() == 0) {

            return prev;

        }

        int prev_num = nums[0];

        prev = 1;

        while (cur < nums.size()) {

            if (nums[cur] != prev_num) {

                nums[prev++] = nums[cur]; 

            }

            prev_num = nums[cur];

            cur++;

        }

        return prev;

    }

};

Largest Rectangle in Histogram

Problem:
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.


Solution:
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = height.size();
        if (size == 0)
            return 0;
        int largest = 0;
        stack<pair<int, int> > height_index_stack;
       
        for (int i = 0; i < size; i++) {
            if (height_index_stack.empty() || height[i] > height_index_stack.top().first) {
                height_index_stack.push(make_pair(height[i], i));
            } else if (height[i] < height_index_stack.top().first) {
                int last_index;
                while (!height_index_stack.empty() &&
                        height_index_stack.top().first > height[i]) {
                    pair<int, int> last_poped = height_index_stack.top();
                    height_index_stack.pop();
                    last_index = last_poped.second;
                    int area = last_poped.first * (i - last_index);
                    largest = max(area, largest);
                }
                height_index_stack.push(make_pair(height[i], last_index));
            }
        }
       
        while (!height_index_stack.empty()) {
            pair<int, int> last_poped = height_index_stack.top();
            height_index_stack.pop();
            int last_index = last_poped.second;
            int area = last_poped.first * (size - last_index);
            largest = max(area, largest);
        }
        return largest;
    }
};


======== Awesome one by Leetcode forum ===========
class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack<int> p;
    int i = 0, m = 0;
    h.push_back(0);
    while(i < h.size()) {
        if(p.empty() || h[p.top()] <= h[i])
            p.push(i++);
        else {
            int t = p.top();
            p.pop();
            m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
        }
    }
    return m;
    }
};

Symmetric Tree

Problem:

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.

Solution: Recursive:

/**

 * 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 isSymmetric(TreeNode *root) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (root == NULL)

            return true;

        else

            return isMirror(root->left, root->right);

    }

    

    bool isMirror(TreeNode *root1, TreeNode *root2) {

        if (root1 == NULL && root2 == NULL)

            return true;

        else if (root1 == NULL || root2 == NULL)

            return false;

        else

            return (root1-> val == root2 -> val) &&

                isMirror(root1->left, root2->right) &&

                isMirror(root1->right, root2 -> left);

    }

};

==== Second time ====
/**
 * 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 isMirror (TreeNode *left, TreeNode *right) {
        if (left == NULL && right == NULL)
            return true;
        else if (left != NULL && right != NULL)
            return (left -> val == right -> val) &&
                isMirror(left -> right, right -> left) &&
                isMirror(left -> left, right -> right);
        else
            return false;
    }
    bool isSymmetric(TreeNode *root) {
        if (root == NULL)
            return true;
        else
            return isMirror(root -> left, root -> right);
    }
};

Longest Consecutive Sequence

 Problem:

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.

Solution:
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        int count = 1, count_so_far = 1;
        sort(num.begin(), num.end());
        for (int i = 0; i < size; i++) {
            if (num[i+1] == num[i] + 1) {
                count_so_far++;
                count = (count_so_far > count ? count_so_far : count);
            } else if (num[i+1] != num[i]) {
                count_so_far = 1;
            }
        }
        return count;
    }
};

======= Second time ===== without sort ======

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for (int i = 0; i < nums.size(); i++) {
            st.insert(nums[i]);
        }
        set<int>::iterator it = st.begin();
        int sol = 0, ans = 1, prev = 0;
        while (it != st.end()) {
            if (it != st.begin()) {
                if (*it - prev == 1) {
                   ans++;
                } else {
                    ans = 1;
                }
            }
            sol = max(sol, ans);
            prev = *it;
            it++;
        }    
        return sol;
    }
};

======= using unordered stl =========
http://yucoding.blogspot.com/2013/05/leetcode-question-129-longest.html

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        if (nums.size() == 0) {
            return ans;
        }
     
        unordered_map<int, bool> mp;
        for (auto val : nums) {
            mp[val] = true;
        }
     
        for (auto val : nums) {
            int count = 1;
            int num = val;
            if (mp.find(num) == mp.end()) {
                ans = max(ans, count);
                continue;
            }
            mp.erase(num);
            while (mp.find(num + 1) != mp.end()) {
                count++;
                mp.erase(num + 1);
                num++;
            }
         
            num = val;
            while (mp.find(num - 1) != mp.end()) {
                count++;
                mp.erase(num - 1);
                num--;
            }
         
            ans = max(ans, count);
        }
        return ans;
    }
};

============== Map ========
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        map<int, bool> mp;
        for (int num : nums) {
            mp[num] = false;
        }
     
        int ans = 0;
        for (int num : nums) {
            int count = 0;
            if (mp[num]) {
                continue;
            }
            int temp = num;
            while (true) {
                if (mp.find(num) == mp.end() ||
                   mp[num]) {
                    break;
                }
                mp[num] = true;
                count++;
                num--;
            }
            num = temp + 1;
            while (true) {
                if (mp.find(num) == mp.end() ||
                   mp[num]) {
                    break;
                }
                mp[num] = true;
                count++;
                num++;
            }
            ans = max(ans, count);
        }
     
        return ans;
    }
};

===================== Another attempt =======
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for (auto num : nums) {
            st.insert(num);
        }
        int ans = 0;
       
        for (auto num : nums) {
            if (!st.count(num)) {
                continue;
            }
            int count = 0;
            int temp = num;
            while (st.count(temp)) {
                st.erase(temp);
                count++;
                temp++;
            }
            int temp2 = --num;
            while (st.count(temp2)) {
                st.erase(temp2);
                count++;
                temp2--;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

First Missing Positive

Problem:
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

Solution:
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int cur = 0; cur < n; cur++) {
            if (A[cur] <= 0) {
                A[cur] = n + 1;
            }
        }

        for (int i = 0; i < n; i++)
            if (abs(A[i]) <= n && A[abs(A[i]) - 1] > 0)
                A[abs(A[i]) - 1] *= -1;

        for (int i = 0; i < n; i++)
            if (A[i] > 0) {
                return i + 1;
            }

        return n + 1;
    }
};

Maximum Subarray

Problem:

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.

Solution:

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

Path Sum

Problem:

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,

Solution:


/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL)
            return false;
        if (root != NULL && root->left == NULL &&
            root->right == NULL && sum == root->val)
            return true;
        else {
            return hasPathSum(root->left, sum - root->val) ||
                hasPathSum(root->right, sum - root->val);
        }
    }
};

====== Second Try ========
/**
 * 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 -> val == sum && root -> left == NULL && root -> right == NULL)
            return true;
        else if (hasPathSum(root -> left, sum - root -> val) ||
                 hasPathSum(root -> right, sum - root -> val))
            return true;
        else
            return false;
    }
};

==== Clean one ====

/**
 * 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 -> val == sum && root -> left == NULL && root -> right == NULL)
            return true;
        else
            return hasPathSum(root -> left, sum - root -> val) ||
                 hasPathSum(root -> right, sum - root -> val);
    }
};