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

Best time to buy and sell stock 2

Problem:

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() < 2) {
            return 0;
        }
        int minSoFar = prices[0];
        int maxSoFar = prices[0];
        int bestBuy = 0;
        int maxBestBuy = 0;
        int sum = 0;
        int it;
        for(it = 1; it < prices.size(); it++) {
            if (prices[it] >= maxSoFar) {
                maxSoFar = prices[it];
                bestBuy = maxSoFar - minSoFar;
                maxBestBuy = max(bestBuy, maxBestBuy);
            } else {
                sum += maxBestBuy;
                maxBestBuy = 0;
                minSoFar = prices[it];
                maxSoFar = prices[it];
            }
        }
        return sum + maxBestBuy;
    }
};

Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:


class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       string solution;
       int size1 = a.size() - 1, size2 = b.size() - 1;
       char carry;
     
       while (size1 >= 0 && size2 >= 0) {
           if (a[size1] == b[size2] && a[size1] != '0') {
                if (carry != '1') {
                    solution += '0';
                } else {
                    solution += '1';
                }
                carry = '1';
           }
           else if (a[size1] == '1') {
               if (b[size2] == '0')
                    if (carry == '1') {
                        solution += '0';
                        carry = '1';
                    } else {
                        solution += '1';
                    }
           } else {
                    if (carry == '1') {
                        if (b[size2] == '1') {
                            solution += '0';
                            carry = '1';
                        } else {
                            solution += '1';
                            carry = '0';
                        }
                    } else {
                        solution += b[size2];
                    }
           }
           size1--;
           size2--;
       }
       if (size2 >= 0 ) {
            size1 = size2;
            a = b;
       }
       while (size1 >= 0) {
               if (carry == '1') {
                   if (a[size1] == '1') {
                         solution += '0';
                        carry = '1';
                   } else {
                       solution += '1';
                       carry = '0';
                   }
               } else {
                   solution += a[size1];
               }
               size1--;
        }
        if (carry == '1')
            solution += carry;

        if (solution.size() > 1)
            reverse(solution);
     
        return solution;
    }
 
    void reverse(string &s) {
        int end = s.size() - 1, i = 0;
        for (i = 0; i < end;  i++,end--) {
            char temp = s[i];
            s[i] = s[end];
            s[end] = temp;
        }
    }
};

 ======== Second time =====
class Solution {
public:
    char oper(char a, char b, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
            else
                if (b == '1') {
                    to_ret = '0';
                } else {
                    to_ret = '1';
                    *carry = '0';
                }
        } else {
            if (a == '1')
                if (b == '1') {
                    to_ret = '0';
                    *carry = '1';
                } else {
                    to_ret = '1';
                }
            else
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
        }
        return to_ret;
                
    }
    
    char oper_on_remaining(char a, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                to_ret = '0';
            else {
                to_ret = '1';
                *carry = '0';
            }
        } else {
            if (a == '1')
                to_ret = '1';
            else
                to_ret = '0';
        }
        return to_ret;
                
    }
    string addBinary(string a, string b) {
        string bigger;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        int size_a = a.size();
        int size_b = b.size();
        
        if (size_a > size_b)
            bigger = a;
        else
            bigger = b;
        
        string sol(bigger);

        char carry = '0';        
        for (int i = 0; i < min(size_a, size_b); i++)
            sol[i] = oper(a[i], b[i], &carry);
        for (int i = min(size_a, size_b); i < max(size_a, size_b); i++)
            sol[i] = oper_on_remaining(bigger[i], &carry);
            
        if (carry == '1')
            sol.push_back(carry);
        reverse(sol.begin(), sol.end());
        return sol;
    }
};


====== Shorter solution ====

string addBinary(string a, string b) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string result;  
5:      int maxL = a.size() > b.size()? a.size():b.size();  
6:      std::reverse(a.begin(), a.end());  
7:      std::reverse(b.begin(), b.end());  
8:      int carry=0;  
9:      for(int i =0; i<maxL;i++)  
10:      {  
11:        int ai = i<a.size()? a[i]-'0':0;  
12:        int bi = i<b.size()?b[i]-'0':0;  
13:        int val = (ai+bi+carry)%2;  
14:        carry = (ai+bi+carry)/2;  
15:        result.insert(result.begin(), val+'0');  
16:      }  
17:      if(carry ==1)  
18:      {  
19:        result.insert(result.begin(), '1');  
20:      }  
21:      return result;  
22:    }  

=== Third time =====
string addBinary(string a, string b) {
        string ans;
       
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
       
        int carry = 0, sum = 0, i = 0;
        while (i < a.size() || i < b.size()) {
            sum = (i < a.size() ? a[i] - '0': 0) +
                  (i < b.size() ? b[i] - '0': 0) +
                  carry;
            carry = sum / 2;
            ans += to_string(sum % 2);
            i++;
        }
        if (carry == 1) {
            ans += "1";
        }
       
        reverse(ans.begin(), ans.end());
        return ans;
    }

========== Best one ========

class Solution { public: string addBinary(string a, string b) { string str = ""; int i = a.size()-1, j = b.size()-1; int c=0; while(i>=0||j>=0||c==1) { c+=(i>=0)?a[i--]-'0':0; c+=(j>=0)?b[j--]-'0':0; str = char(c%2+'0')+str; c/=2; } return str; } };

Subsets

Problem:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > solution;
        int size = S.size();
     
        if (size == 0)
            return solution;

        sort(S.begin(), S.end());
        vector<int> subset;
        solution.push_back(subset);
     
        for (int i = 0; i < size; i++) {
            int subset_count = solution.size();
            for (int sln_idx = 0; sln_idx < subset_count; sln_idx++) {
                subset = solution[sln_idx];
                subset.push_back(S[i]);
                solution.push_back(subset);
            }
        }
        return solution;
    }
};

=============== Alternate (Small one)=======================

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
    sort(S.begin(), S.end());
    vector<vector<int> > v(1);
    for(int i = 0; i < S.size(); ++i) {
        int j = v.size();
        while(j-- > 0) {
            v.push_back(v[j]);
            v.back().push_back(S[i]);
        }
    }
    return v;
    }
};

=================== Alternate (Bitwise) ========================

class Solution {

public:

    vector<vector<int> > subsets(vector<int> &S) {

sort(S.begin(), S.end());

int n = S.size();

vector<vector<int> > result;

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

vector<int> s;

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

if ((i >> j) & 1) {

s.push_back(S[j]);

}

}

result.push_back(s);

}

return result;

    }

};

============ Another attempt =========

vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > ans;
        ans.push_back(vector<int>());
        
        if (nums.size() == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }

=============================== Another =========

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        ans.push_back(vector<int>());
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }
};