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