Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> pascal(rowIndex+1);
        if (rowIndex>=0){
            pascal[0] = vector<int>(1,1);
        }
        for(int i=1;i<=rowIndex;i++){
            vector<int> temp(i+1,1);
            for(int j=1;j<i;j++){
                temp[j]=pascal[i-1][j-1]+pascal[i-1][j];
            }
            pascal[i]=temp;
        }
        return pascal[rowIndex];
    }
};

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res;
        for(int i=0;i<rowIndex+1;i++){
            res.insert(begin(res),1);
            for(int j=1;j<res.size()-1;j++){
                res[j]+=res[j+1];
            }
        }
        return res;
    }
};

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int l = digits.size();
        for(int i=l-1;i>=0;i--){
            if(digits[i]<9){
                digits[i]++;
                return digits;
            }
            else{
                digits[i]=0;
            }
        }
        vector<int> res(l+1);
        res[0]=1;
        return res;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = nums.size();
        if (l<1) return l;
        int count = 1;
        int ele = nums[0];
        for(int i=1;i<l;i++){
            if(ele!=nums[i]){
                ele=nums[i];
                nums[count++]=nums[i];
            }
        }
        return count;
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int cur = m+n-1;
        int pos1 = m-1;
        int pos2 = n-1;
        while(pos1>=0 && pos2>=0){
            if(nums1[pos1]>nums2[pos2]){
                nums1[cur--] = nums1[pos1--];
            }
            else{
                nums1[cur--] = nums2[pos2--];
            }
        }
        while(pos2>=0){
            nums1[cur--] = nums2[pos2--];
        }
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = nums.size();
        int sum_ = (1+l)*l/2;
        for (int i=0;i<l;i++){
            sum_ -= nums[i];
        }
        return sum_;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = nums.size();
        int res = 0;
        for (int i=0;i<l;i++){
            res = res^i^nums[i];
        }
        res = res^l;
        return res;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int res = 0;
        for(auto ele : nums){
            if (count==0){
                count++;
                res = ele;
            }
            else if(ele==res){
                count++;
            }
            else{
                count--;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mymap;
        int l = nums.size();
        vector<int> res;
        int the_other = -1;
        for(int i=0;i<l;i++){
            the_other = target - nums[i];
            if (mymap.find(the_other) != mymap.end()){
                res.push_back(mymap[the_other]);
                res.push_back(i);
                break;
            }
            else{
                mymap[nums[i]] = i;
            }
        }
        return res;
    }
};

class Solution {
public:int thirdMax(vector<int>& nums) {
        int l = nums.size();
        long firstMax = LONG_MIN;
        long secondMax = LONG_MIN;
        long thirdMax = LONG_MIN;
        int cur = 0;
        for(int i=0;i<l;i++){
            cur = nums[i];
            if(cur>firstMax){
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = cur;
            }
            else if(cur>secondMax&&cur!=firstMax){
                thirdMax = secondMax;
                secondMax = cur;
            }
            else if(cur>thirdMax&&cur!=firstMax&&cur!=secondMax){
                thirdMax = cur;
            }
        }
        return thirdMax==LONG_MIN?firstMax:thirdMax;
    }
};

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        nums.push_back(0);
        vector<int>::iterator it;
        it = nums.begin();
        it = nums.insert ( it , 0 );
        int start = 0;
        int l = nums.size();
        int res = 0;
        for (int i=0;i<l;i++){
            if (nums[i]==0){
                res = max(res,i-start-1);
                start = i;
            }
        }
        return res;
    }
};

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int l = nums.size();
        int res = 0;
        int count = 0;
        for (int i=0;i<l;i++){
            if (nums[i]==0){
                res = max(res,count);
                count = 0;
            }
            else{
                count++;
            }
        }
        return max(res,count); // for special input [1]
    }
};

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int l = prices.size();
        if (l<1) return l;
        int min_ = prices[0];
        int res = 0;
        for(auto ele : prices){
            res = max(res,ele-min_);
            min_ = min(min_,ele);
        }
        return res;
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_map<int,int> mymap;
        for(auto ele : nums){
            mymap[ele]++;
        }
        int res = 0;
        if (k<0) return res;
        if (k==0){
            for(auto ele : mymap){
                if (ele.second>1)
                    res++;
            }
        }
        else{
            for(auto ele : mymap){
                if(mymap.find(ele.first+k) != mymap.end()){
                    res++;
                }
                    
            }
        }
        return res;
    }
};

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        const int max_val = 10000;
        vector<int> val_idx_map(2*max_val);
        for (auto ele : nums){
            val_idx_map[ele+max_val]++;
        }
        bool first = true;
        int n = -max_val;
        int res = 0;
        while(n<max_val){
            if (!val_idx_map[n+max_val]){
                n++;
                continue;
            }
            if (first){
                res += n;
                first = false;
            }else{
                first = true;
            }
            val_idx_map[n+max_val]--;
        }
        return res;
    }
};

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int res = 0;
        int l = flowerbed.size();
        for (int i=0;i<l;i++){
            if (flowerbed[i]==1) continue;
            if (i>0 && flowerbed[i-1]==1) continue;
            if (i<l-1 && flowerbed[i+1]==1) continue;
            res ++;
            flowerbed[i] = 1;
        }
        if (res>=n)
            return true;
        else
            return false;
    }
};

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        int l = nums.size();
        for (int i=0;i<l-1;i++){
            if (nums[i]>nums[i+1]){
                count+=1;
                if(i==0){
                    nums[i]=nums[i+1]-1;
                }
                else if(nums[i-1]<nums[i+1]){ 
                    nums[i]=nums[i+1]-1;
                }
                else{
                    nums[i+1]=nums[i]+1;
                }
            }
                
            if (count>1)
                return false;
        }
        return true;
    }
};

Input: 
bits = [1, 0, 0]
Output: True
Explanation: 
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Input: 
bits = [1, 1, 1, 0]
Output: False
Explanation: 
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int l=bits.size();
        int i=0;
        while(i<l-1){
            if(bits[i]==0)
                i++;
            else
                i+=2;
        }
        if (i==(l-1) && bits[i]==0)
            return true;
        else
            return false;
    }
};

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Input:
matrix = [
  [1,2],
  [2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.
**Note:**

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        for (int i=0;i<row-1;i++){
            for (int j=0;j<col-1;j++){
                if (matrix[i][j]!=matrix[i+1][j+1])
                    return false;
            }
        }
        return true;
    }
};

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Input: [1]
Output: false
Explanation: No possible partition.

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        map<int,int> count;
        for (int i:deck){
            count[i] ++;
        }
        int min_count = 0;
        for (auto &v:count){
            if (min_count>v.second){
                min_count = v.second;
            }
        }
        for (auto &v:count){
            min_count = __gcd(min_count,v.second);
            if (min_count<2){
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int pos = INT_MAX;
        vector<int> dis(seats.size(),INT_MAX);
        for (int i=0;i<seats.size();i++){
            if (seats[i]==1){
                pos = i;
                dis[i] = 0;
            }
            else{
                dis[i] = abs(pos-i);
            }
        }
        
        pos = INT_MAX;
        for (int i=seats.size()-1;i>-1;i--){
            if (seats[i]==1){
                pos = i;
            }
            else{
                dis[i] = min(abs(i-pos),dis[i]);
            }
        }
        auto maxPosition = max_element(dis.begin(), dis.end());
        return dis[maxPosition - dis.begin()];
        
    }
};