LeetCode Find Minimum in Rotated Sorted Array II a short one

LeetCode Find Minimum in Rotated Sorted Array II a short one

class Solution {

public:

    int search(vector<int>& nums,int l,int r)

    {

        if(l>r)

          return INT_MAX;

        else if(l==r)

          return nums[l];

        else if(nums[l]<nums[r])

          return nums[l];

        int mid=(l+r)/2;

        return min(search(nums,l,mid),search(nums,mid+1,r));

    }

    int findMin(vector<int>& nums) {

        return search(nums,0,nums.size()-1);

    }

};

LeetCode Binary Tree Maximum Path Sum nice bottom up recursion

LeetCode Binary Tree Maximum Path Sum nice bottom up recursion

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    int fun(TreeNode* root,int *max_sum)

     {

         if(root==NULL)

           return 0;

         int ls=fun(root->left,max_sum);

         int rs=fun(root->right,max_sum);

         int mx=max(max(root->val+ls,root->val+rs),root->val+ls+rs);

           mx=max(mx,root->val);

          if(mx>(*max_sum))

             (*max_sum)=mx;

          return max(max(root->val+ls,root->val+rs),root->val);

     }

    int maxPathSum(TreeNode* root) {

        int max_sum=INT_MIN;

        fun(root,&max_sum);

        return max_sum;

    }

};

LeetCode Symmetric Tree

LeetCode Symmetric Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

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

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

         return true;

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

         return false;

        return (root1->val==root2->val && fun(root1->left,root2->right) && fun(root1->right,root2->left));

    }

    bool isSymmetric(TreeNode* root) {

        if(root==NULL)

          return true;

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

       

    }

};

LeetCode Symmetric Tree

LeetCode Symmetric Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

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

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

         return true;

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

         return false;

        return (root1->val==root2->val && fun(root1->left,root2->right) && fun(root1->right,root2->left));

    }

    bool isSymmetric(TreeNode* root) {

        if(root==NULL)

          return true;

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

       

    }

};

LeetCode Validate Binary Search Tree

LeetCode Validate Binary Search Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool fun(TreeNode* root,int mn,int mx,int * cmn,int * cmx){

        if(root==NULL)

         return true;

        if(root->val <= mn){

         if(mn==-2147483648 && *cmn==0)

             {

             *cmn=1;

             return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

             }

           return false;

        }

        if(root->val >= mx)

         {

             if(mx==2147483647 && *cmx==0)

             {

             *cmx=1;

             return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

             }

            return false;

         }

        return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

    }

    bool isValidBST(TreeNode* root) {

        int cmn=0;

        int cmx=0;

        return fun(root,INT_MIN,INT_MAX,&cmn,&cmx);

    }

};

LeetCode Restore IP Addresses O(n3) still accepted

LeetCode  Restore IP Addresses

class Solution {

public:

    vector<string> restoreIpAddresses(string s) {

     vector < string > ans;

     int l=s.size();

     if(l>12 || l<4)

       return ans;

     int i,j,k;

     int first,second,third,fourth;

     for(i=0;i<l-3;i++){

          string temp(s.begin(),s.begin()+i+1);

          if(temp.size()>=2 && temp[0]=='0')

           break;

          first=stoi(temp);

          if(first>255)

            break;

         for(j=i+1;j<l-2;j++){

            string temp1(s.begin()+i+1,s.begin()+j+1);

            if(temp1.size()>=2 && temp1[0]=='0')

             break;

            second=stoi(temp1);

            if(second>255)

            break;

         for(k=j+1;k<l-1;k++){

            string temp3(s.begin()+j+1,s.begin()+k+1);

            if(temp3.size()>=2 && temp3[0]=='0')

              break;

            third=stoi(temp3);

            string temp4(s.begin()+k+1,s.end());

            if(temp4.size()>=2 && temp4[0]=='0')

               continue;

            fourth=stoi(temp4);

            if(third<=255 && fourth<=255)

             {

                 string s1(s.begin(),s.end());

                 s1.insert(s1.begin()+i+1,'.');

                 s1.insert(s1.begin()+j+2,'.');

                 s1.insert(s1.begin()+k+3,'.');

                 ans.push_back(s1);

             }

          }

         }

       }

       return ans;

    }

};

LeetCode Reverse Linked List II

LeetCode Reverse Linked List II

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

       if(head==NULL || head->next==NULL || (m==n))

         return head;

       ListNode * current=head;

       ListNode * prev=NULL;

       ListNode * next;

       ListNode * temp;

       ListNode *p;

       int cnt=n-m;

       while(m--){

           p=prev;

           prev=current;

           current=current->next;

       }

       temp=prev;

       while(cnt--){

           next=current->next;

           current->next=prev;

           prev=current;

           current=next;

       }

       if(p==NULL)

         head=prev;

       else

         p->next=prev;

       temp->next=current;

       return head;

    }

};

#LeetCode# Subsets II stl awesome

LeetCode Subsets II

class Solution {

public:

    void subset(vector<int>& nums,set < vector < int > > &ans,vector < int > temp,int idx,int n){

        if(idx==n)

        {

            ans.insert(temp);

            return ;

        }

        subset(nums,ans,temp,idx+1,n);

        temp.push_back(nums[idx]);

        subset(nums,ans,temp,idx+1,n);

    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        vector < vector < int > > a;

        set < vector < int > > ans;

        vector < int > temp;

        int n=nums.size();

        if(n==0)

          return a;

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

        subset(nums,ans,temp,0,n);

      vector < vector < int > > b(ans.begin(),ans.end());

      return b;

    }

};

#LeetCode# Subsets II stl awesome

LeetCode Subsets II

class Solution {

public:

    void subset(vector<int>& nums,set < vector < int > > &ans,vector < int > temp,int idx,int n){

        if(idx==n)

        {

            ans.insert(temp);

            return ;

        }

        subset(nums,ans,temp,idx+1,n);

        temp.push_back(nums[idx]);

        subset(nums,ans,temp,idx+1,n);

    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        vector < vector < int > > a;

        set < vector < int > > ans;

        vector < int > temp;

        int n=nums.size();

        if(n==0)

          return a;

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

        subset(nums,ans,temp,0,n);

      vector < vector < int > > b(ans.begin(),ans.end());

      return b;

    }

};

LeetCode Gray Code

LeetCode Gray Code

class Solution {

public:

    vector<int> grayCode(int n) {

       vector < int > ans;

       ans.push_back(0);

       if(n==0)

         return ans;

       ans.push_back(1);

       if(n==1)

         return ans;

       int cnt=2,size;

       while(cnt<=n)

       {

           int k=1;

           size=ans.size();

           while(k<=size)

           {

               ans.push_back((size+ans[size-k]));

               k++;

           }

           cnt++;

       }

       return ans;

    }

};

LeetCode Partition List

LeetCode Partition List

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode * insert(int x){

        ListNode * temp=(ListNode *)malloc(sizeof(ListNode ));

        temp->val=x;

        temp->next=NULL;

        return temp;

    }

    ListNode * partition(ListNode* head, int x) {

        if(head==NULL || head->next==NULL)

          return head;

        vector < int > v;

        ListNode * current=head;

        ListNode * prev=NULL;

        ListNode * temp;

        while(current!=NULL){

                if(current->val < x)

                {

                 temp=current;

                 v.push_back(current->val);

                 if(prev==NULL)

                   head=current->next;

                 else

                   prev->next=current->next;

                 current=current->next;

                 free(temp);

                }

                else

                {

                    prev=current;

                    current=current->next;

                }

            }

        if(v.size()==0)

          return head;

        prev=NULL;

        current=head;

        int k=0;

        while(k < v.size()){

            temp=insert(v[k]);

            if(prev==NULL){

              temp->next=head;

              head=temp;

              prev=head;

            }

            else{

            prev->next=temp;

            temp->next=current;

            prev=temp;}

            k++;

         }

      return head;

    }

};

LeetCode Remove Duplicates from Sorted List

LeetCode  Remove Duplicates from Sorted List 

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* deleteDuplicates(ListNode* head) {

        if(head==NULL || head->next==NULL)

          return head;

         ListNode* current=head->next;

         ListNode* prev=head;

         ListNode* temp=NULL;

         while(current!=NULL){

             if(current->val==prev->val)

             {

                 temp=current;

                 prev->next=current->next;

                 current=current->next;

                 free(temp);

             }

             else

             {

                 prev=current;

                 current=current->next;

             }

         }

         return head;

    }

};

LeetCode Remove Duplicates from Sorted List II

LeetCode Remove Duplicates from Sorted List II

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* deleteDuplicates(ListNode* head) {

     if(head==NULL || head->next==NULL)

       return head;

     ListNode * current=head->next;

     ListNode * p=NULL;

     ListNode * prev=head;

     while(current!=NULL){

          if(current->val==prev->val)

          {

           prev=current;

           current=current->next;

          }

         else

         {

            if(p!=NULL)

              {

                if(p->next!=prev)

                  p->next=current;

                else

                  p=prev;

              }

            else

              {

                if(prev->val==head->val && prev!=head)

                 {

                  head=current;

                  p=NULL;

                 }

                else

                  p=prev;

              }

            prev=current;

            current=current->next;

         }

     }

     if(p==NULL && prev!=head && prev->val==head->val)

      return NULL;

     else if(p!=NULL){

      if(p->next!=prev)

         p->next=current;

     }

     return head;

    }

};

LeetCode Remove Duplicates from Sorted Array II

LeetCode Remove Duplicates from Sorted Array II

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        int i,k=1;

        int n=nums.size();

        if(n==0)

         return 0;

        if(n==1)

         return 1;

        int prev=nums[0];

        int cnt=0;

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

            if(nums[i]==prev && cnt==0){

              nums[k]=nums[i];

              cnt=1;

              k++;

            }

            else if(nums[i]!=prev){

                 cnt=0;

                 nums[k]=nums[i];

                 prev=nums[i];

                 k++;

             }

        }

        return k;

    }

};

LeetCode Word Search simple BFS

LeetCode Word Search simple BFS

class Solution {

public:

    bool is_valid(int row,int col,int m,int n){

        if(row>=0 && row<m && col>=0 && col<n)

          return true;

        else

         return false;

    }

    bool bfs(vector<vector<char>>& board, string &word,int row,int col,bool visited[1000][1000],int row_arr[],int col_arr[],int m,int n,int idx){

        if(word[idx]=='\0')

          return true;

        int new_row,new_col;

        for(int i=0;i<4;i++)

        {

            new_row=row+row_arr[i];

            new_col=col+col_arr[i];

            if(is_valid(new_row,new_col,m,n) && !(visited[new_row][new_col]) && board[new_row][new_col]==word[idx])

            {

              visited[new_row][new_col]=true;

              if(bfs(board,word,new_row,new_col,visited,row_arr,col_arr,m,n,idx+1)==true)

                return true;

              else{

                visited[new_row][new_col]=false;

                continue;

              }

            }

        }

        return false;

    }

    bool exist(vector<vector<char>>& board, string word) {

        int m=board.size();

        if(m==0)

          return false;

        int n=board[0].size();

        int row_arr[]={-1,0,1,0};

        int col_arr[]={0,1,0,-1};

        bool visited[1000][1000];

        memset(visited,false,sizeof(visited));

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

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

               if(board[i][j]==word[0]){

                visited[i][j]=true;

                if(bfs(board,word,i,j,visited,row_arr,col_arr,m,n,1))

                 return true;

                else

                 memset(visited,false,sizeof(visited));

               }

            }

        }

        return false;

    }

};

LeetCode Sort Colors

LeetCode Sort Colors

class Solution {

public:

    void sortColors(vector<int>& nums) {

        int n=nums.size(),i;

        int count0=0,count1=0,count2=0;

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

         {

             switch(nums[i])

             {

                 case 0:

                   (count0)++;

                   break;

                 case 1:

                   (count1)++;

                   break;

                 case 2:

                   (count2)++;

                   break;

                 default:

                    ;

             }

         }

        i=0;

        while((count0)--)

          nums[i++]=0;

        while((count1)--)

          nums[i++]=1;

        while((count2)--)

          nums[i++]=2;

    }

};

LeetCode 2D Matrix log(row)+log(col)=O(n)

LeetCode  2D Matrix

class Solution {

public:

    int search_row(vector<vector<int>>& matrix,int target,int l,int r,int m)

    {

        if(l>r)

         return -1;

        if(l==r)

          {

              if(l==0)

                return l;

              else

                return (l-1);

          }

        int mid=(l+r)/2;

        if(matrix[mid][0]==target)

         return mid;

        if(mid-1>=0 && matrix[mid-1][0]<=target && matrix[mid][0]>target)

         return (mid-1);

        if(mid+1<m && matrix[mid][0]<target && matrix[mid+1][0]>=target)

         {

             if(matrix[mid+1][0]==target)

               return (mid+1);

             else

               return mid;

         }

        if(target<matrix[mid][0])

         return search_row(matrix,target,l,mid-1,m);

        else

         return search_row(matrix,target,mid+1,r,m);

    }

    bool binary_search(vector<vector<int>>& matrix, int target,int row,int l,int r){

        if(l>r)

         return false;

        int mid=(l+r)/2;

        if(target==matrix[row][mid])

         return true;

        if(target<matrix[row][mid])

         return binary_search(matrix,target,row,l,mid-1);

        else

         return binary_search(matrix,target,row,mid+1,r);

    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int m=matrix.size();

        if(m==0)

          return false;

        int n=matrix[0].size();

        if(n==0)

          return false;

        int row=search_row(matrix,target,0,m,m);

        if(row==-1)

          return false;

        if(matrix[row][0]==target)

          return true;

        return binary_search(matrix,target,row,0,n);

    }

};

LeetCode Set Matrix Zeroes

LeetCode Set Matrix Zeroes

class Solution {

public:

    void setZeroes(vector<vector<int>>& matrix) {

        int m=matrix.size();

        if(m==0)

          return ;

        int n=matrix[0].size();

        if(n==0)

          return ;

        vector < int > store_row;

        vector < int > store_col;

        vector < bool > visited_col(n,false);

        int i,j,tag=0;

        for(i=0;i<m;i++){

         tag=0;

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

            if(matrix[i][j]==0 && tag==0)

              {

                  store_row.push_back(i);

                 store_col.push_back(j);

                  visited_col[j]=true;

                  tag=1;

              }

            if(matrix[i][j]==0 && visited_col[j]==false){

                   store_col.push_back(j);

                   visited_col[j]=true;

            }

         }

        }

        i=0;

        while(i<store_row.size()){

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

               matrix[store_row[i]][j]=0;

            }

            i++;

        }

        i=0;

        while(i<store_col.size()){

            for(j=0;j<m;j++){

               matrix[j][store_col[i]]=0;

            }

            i++;

        }

    }

};

LeetCode Climbing Stairs! like fabonacci series from last point

LeetCode Climbing Stairs! like fabonacci series from last point 

class Solution {

public:

    int climbStairs(int n) {

        if(n<=3)

         return n;

        int i=3,j=2;

        int temp;

        int cnt=3;

        while(cnt<n)

         {

             temp=i;

             i=i+j;

             j=temp;

             cnt++;

         }

         return i;

    }

};

LeetCode Add Binary adddition of two strings

LeetCode Add Binary addition of two strings

class Solution {

public:

    string addBinary(string str1, string str2) {

       int l1=str1.size();

       int l2=str2.size();

       int i=l1-1,j=l2-1;

       int carry=0;

       int sum;

       string result;

       stack < char > s;

       while(i>=0 && j>=0){

           sum=carry + (str1[i]-'0') + (str2[j]-'0');

           carry=sum/2;

           s.push((sum%2)+48);

           i--;

           j--;

       }

       if(i==-1 && j==-1 && carry!=0){

           s.push(carry+48);

       }

       if(i>=0){

           while(i>=0){

           sum=carry+(str1[i]-'0');

           carry=sum/2;

           s.push((sum%2)+48);

  i--;}

       if(i==-1 && carry!=0){

           s.push(carry+48);

       }

       }

       if(j>=0){

           while(j>=0){

           sum=carry+(str2[j]-'0');

           carry=sum/2;

           s.push((sum%2)+48);

  j--;}

       if(j==-1 && carry!=0){

           s.push(carry+48);

          }

       }

      while(!s.empty()){

          result.push_back(s.top());

          s.pop();

      }

     return result;

     }

};

LeetCode Plus One Easy One

LeetCode Plus One Easy One

class Solution {

public:

    vector<int> plusOne(vector<int>& digits) {

        vector < int > ans;

        if(digits.size()==0)

         return digits;

        int carry=1;

        for(int i=digits.size()-1;i>=0;i--){

           int sum=carry+digits[i];

            if(sum<10){

                digits[i]=sum;

                return digits;

            }

            else{

                digits[i]=sum%10;

                carry=sum/10;

            }

        }

            digits.insert(digits.begin(),carry);

            return digits;

    }

};

LeetCode Plus One Easy One

LeetCode Plus One Easy One

class Solution {

public:

    vector<int> plusOne(vector<int>& digits) {

        vector < int > ans;

        if(digits.size()==0)

         return digits;

        int carry=1;

        for(int i=digits.size()-1;i>=0;i--){

           int sum=carry+digits[i];

            if(sum<10){

                digits[i]=sum;

                return digits;

            }

            else{

                digits[i]=sum%10;

                carry=sum/10;

            }

        }

            digits.insert(digits.begin(),carry);

            return digits;

    }

};

LeetCode Valid Number so many corner cases

LeetCode Valid Number so many corner cases

class Solution {

public:

    bool isNumber(string s) {

       int i,j,n=s.size();

       char prev;

       bool dot=false;

       int is_digit=0;

       bool is_e=false;

       j=0;

           while(j<n && s[j]==' ')

            j++;

           if(j==n)

            return false;

           if(s[j]!='-' && s[j]!='+' && s[j]!='.' && !(s[j]>='0' && s[j]<='9'))

            return false;

           if(s[j]=='-' || s[j]=='+' || s[j]=='.')

           {

             dot=(s[j]=='.');

             j++;

           }

            if(j==n)

             return false;

           while(j<n && (s[j]=='e' || s[j]=='+' || s[j]=='-' || s[j]=='.' || (s[j]>='0' && s[j]<='9'))){

             if((s[j]=='+' || s[j]=='-') && s[j-1]!='e')

              return false;

             if(s[j]=='e')

             {

               if(is_digit==0)

                 return false;

               else if(is_e==true)

                return false;

               else

                 is_e=true;

             }

             if(s[j]=='.'){

              if(is_e)

                return false;

              if(dot)

               return false;

              else

               dot=true;

             }

             if((s[j]>='0' && s[j]<='9'))

               is_digit=1;

             j++;

           }

           if(j==n && is_digit==1 && s[j-1]!='e' && s[j-1]!='+' && s[j-1]!='-')

            return true;

           else

           {

            if(j<n){

                int idx=j;

                while(j<n && s[j]==' ')

                 j++;

                if(j==n && is_digit==1 && s[idx-1]!='e'&& s[j-1]!='+' && s[j-1]!='-')

                 return true;

                else

                 return false;

            }

            return false;

           }

    }

};

LeetCode Minimum Path Sum a similar one to Unique Paths II

LeetCode Minimum Path Sum a similar one to Unique Paths II

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        int i,j;

        int m=grid.size();

        if(m==0)

          return 0;

        int n=grid[0].size();

        if(n==0)

          return 0;

        if(m<=1 && n<=1 && grid[0][0]==0)

         return grid[0][0];

         i=1;

         while(i<n)

          {

              grid[0][i]+=grid[0][i-1];

              i++;

          }

         i=1;

         while(i<m)

          {

              grid[i][0]+=grid[i-1][0];

              i++;

          }

          if(m==1)

           return grid[0][n-1];

          if(n==1)

           return grid[m-1][0];

          for(i=1;i<m;i++){

              for(j=1;j<n;j++){

                  grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);

                }

          }

          return grid[m-1][n-1];

    }

};

LeetCode Unique Paths II small variation in Unique Paths

LeetCode Unique Paths II small variation in Unique Paths

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int i,j;

        int m=obstacleGrid.size();

        if(m==0)

          return 0;

        int n=obstacleGrid[0].size();

        if(n==0)

          return 0;

        if(m<=1 && n<=1 && obstacleGrid[0][0]==0)

         return 1;

        if(obstacleGrid[0][0])

         return 0;

        i=1;

         while(i<n && obstacleGrid[0][i]==0)

          {

              obstacleGrid[0][i]=1;

              i++;

          }

         while(i<n){

           obstacleGrid[0][i]=0;

           i++;

         }

         i=1;

         while(i<m && obstacleGrid[i][0]==0)

          {

              obstacleGrid[i][0]=1;

              i++;

          }

         while(i<m){

           obstacleGrid[i][0]=0;

           i++;

         }

          if(m==1)

           return obstacleGrid[0][n-1];

          if(n==1)

           return obstacleGrid[m-1][0];

          for(i=1;i<m;i++){

              for(j=1;j<n;j++){

                  if(obstacleGrid[i][j]==0)

                    obstacleGrid[i][j]=obstacleGrid[i][j-1]+obstacleGrid[i-1][j];

                  else

                    obstacleGrid[i][j]=0;

                }

          }

          return obstacleGrid[m-1][n-1];

    }

};

LeetCode Rotate List easy one but don't forget k=k%(no of nodes)

LeetCode  Rotate List easy one but don't forget k=k%(no of nodes)

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* rotateRight(ListNode* head, int k) {

        if(head==NULL)

         return head;

        ListNode* fast=head;

        ListNode* slow=head;

        int cnt=0;

        while(fast!=NULL)

        {

            cnt++;

            fast=fast->next;

        }

        if(k%cnt==0)

         return head;

        else

         k=k%cnt;

        fast=head;

        while(k && fast->next){

          fast=fast->next;

          k--;

        }

        while(fast->next!=NULL)

         {

             fast=fast->next;

             slow=slow->next;

         }

         fast->next=head;

         head=slow->next;

         slow->next=NULL;

         return head;

    }

};

LeetCode Spiral Matrix II a little modification required in Spiral Matrix done earlier

LeetCode Spiral Matrix II a little modification required in Spiral Matrix done earlier

class Solution {

public:

    vector<vector<int>> generateMatrix(int n) {

      vector < int > temp(n,0);

      vector < vector< int >  > ans(n,temp);

      int s1,s2;

      int e1=n,e2=n;

      int i=0,j=0,cnt=1;

      n=n*n;

     while(cnt<=n){

      s1=i;s2=j;

      while(s2<e2){

            ans[s1][s2]=cnt;

          s2++;cnt++;

      }

      if(cnt>n)

           break;

      s1=i+1;s2=e2-1;

      while(s1<e1){

           ans[s1][s2]=cnt;

           s1++;cnt++;

      }

      if(cnt>n)

           break;

      s1=e1-1;s2=e2-2;

      while(s2>=j){

          ans[s1][s2]=cnt;

          s2--;cnt++;

      }

      if(cnt>n)

           break;

      s1=e1-2;s2=j;

      while(s1>i){

          ans[s1][s2]=cnt;

          s1--;cnt++;

      }

      if(cnt>n)

           break;

      i=i+1;j=j+1;

      e1=e1-1;e2=e2-1;

     }

     return ans;

    }

};

LeetCode Length of Last Word really very easy

LeetCode Length of Last Word really very easy

class Solution {

public:

    int lengthOfLastWord(string s) {

        int l=s.size();

        int cnt=0;

        int j=l-1;

        while(j>=0 && s[j]==' ')

          j--;

        while(j>=0 && s[j]!=' '){

          cnt++;

          j--;

        }

        return cnt;

    }

};

LeetCode Insert Interval insert interval in the given list and rest is same as done in merge interval

LeetCode Insert Interval insert interval in the given list and rest is same as done in merge interval

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

 *     Interval() : start(0), end(0) {}

 *     Interval(int s, int e) : start(s), end(e) {}

 * };

 */

class Solution {

public:

    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

        vector <Interval> ans;

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

         ans.push_back(newInterval);

         return ans;

        }

        vector < Interval > :: iterator it,it1;

        it=intervals.begin();

        while(it!=intervals.end() && (it)->start <= newInterval.start)

          it++;

        intervals.insert(it,newInterval);

        it=intervals.begin();

        it1=intervals.begin();

        it1++;

        while(it!=intervals.end() && (it1)!=intervals.end()){

            if((it)->end < (it1)->start){

             ans.push_back((*it));

             it=it1;

             it1++;

            }

            else if((it)->end >= (it1)->end){

             it1++;

            }

            else

            {

             (it)->end=(it1)->end;

             it1++;

            }

        }

        if(it!=intervals.end())

         ans.push_back((*it));

        return ans;

    }

};

LeetCode Merge Intervals O(n) complexity

LeetCode Merge Intervals O(n) complexity

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

 *     Interval() : start(0), end(0) {}

 *     Interval(int s, int e) : start(s), end(e) {}

 * };

 */

class Solution {

public:

    static bool myfunc(const Interval &a, const Interval &b){

        return (a.start < b.start);

    }

    vector<Interval> merge(vector<Interval>& intervals) {

        int i,j;

        vector <Interval> ans;

        if(intervals.size()==0)

         return ans;

        sort(intervals.begin(),intervals.end(),Solution :: myfunc);

        vector < Interval > :: iterator it,it1;

        it=intervals.begin();

        it1=intervals.begin();

        it1++;

        while(it!=intervals.end() && (it1)!=intervals.end()){

            if((it)->end < (it1)->start){

             ans.push_back((*it));

             it=it1;

             it1++;

            }

            else if((it)->end >= (it1)->end){

             it1++;

            }

            else

            {

             (it)->end=(it1)->end;

             it1++;

            }

        }

        if(it!=intervals.end())

         ans.push_back((*it));

        return ans;

    }

};

LeetCode Jump Game a simple one

LeetCode Jump Game a simple one

class Solution {

public:

    bool canJump(vector<int>& nums) {

        int i,sum;

        int n=nums.size();

        if(n<=1)

         return true;

        vector < int > reach(n,0);

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

            if(nums[i])

            reach[i]=nums[i]+i;

        }

        int mx=reach[0];

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

            if(reach[i]>=(n-1))

             return true;

            if(reach[i]==0 && mx<=i)

             return false;

            if(reach[i]>mx)

             mx=reach[i];

        }

        return false;

    }

};

LeetCode Spiral Matrix O(n) time complexity and O(1) extra space

LeetCode Spiral Matrix O(n) time complexity and O(1) extra space

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int> >& matrix) {

      vector < int > ans;

      int row=matrix.size();

      if(row==0)

       return ans;

      int column=matrix[0].size();

      if(column==0)

       return ans;

      int s1,s2,n=row*column;

      int e1=row,e2=column;

      int i=0,j=0,cnt=0;

     while(cnt<n){

      s1=i;s2=j;

      while(s2<e2){

            ans.push_back(matrix[s1][s2]);

          s2++;cnt++;

      }

      if(cnt==n)

           break;

      s1=i+1;s2=e2-1;

      while(s1<e1){

           ans.push_back(matrix[s1][s2]);

           s1++;cnt++;

      }

      if(cnt==n)

           break;

      s1=e1-1;s2=e2-2;

      while(s2>=j){

          ans.push_back(matrix[s1][s2]);

          s2--;cnt++;

      }

      if(cnt==n)

           break;

      s1=e1-2;s2=j;

      while(s1>i){

          ans.push_back(matrix[s1][s2]);

          s1--;cnt++;

      }

      if(cnt==n)

           break;

      i=i+1;j=j+1;

      e1=e1-1;e2=e2-1;

     }

     return ans;

    }

};

LeetCode Pow(x, n) simple O(logn) solution .

LeetCode Pow(x, n) simple O(logn) solution .

class Solution {

public:

    double myPow(double x, int n) {

      double temp;

       if(n==0)

         return 1;

       if(n==1)

        return x;

       if(n==-1)

        return 1/x;

        temp=myPow(x,n/2);

      if(abs(n)%2==0){  //if n is even

           return temp*temp;

      }

      else   //if n is odd

      {

       if(n>0)

          return x*temp*temp;

        else

          return (1/x)*(temp)*(temp); //if n is negative return 1/x either

      }

    }

};

#LeetCode# Trapping Rain Water C++/C solution

#LeetCode#  Trapping Rain Water. C/C++ solution

class Solution {

public:

    int fun(vector<int>& height,int i,int j,int mx){

        int ans=0;

        if((mx+1)!=i){

                if(height[mx]==height[i]){             //if left and right bars are equal

                    ans=(height[mx]-height[mx+1])*(i-j-1);   //calculate the area

                    int h=(height[mx]-height[mx+1]);

                    for(j=mx+1;j<i;j++){

                     height[j]=height[j]+h;  //update the heights of each bar in between for upcomming calculations

                    }

                }

                else if(height[mx]<height[i]){  //if left bar is less than right bar

                     ans=(height[mx]-height[mx+1])*(i-j-1); //calculate area

                     int h=(height[mx]-height[mx+1]);

                    for(j=mx+1;j<i;j++)

                     height[j]=height[j]+h;  //update the heights

                }

                else{

                    ans=(height[i]-height[i-1])*(i-j-1); //if left bar is greater than right bar

                    int h=(height[i]-height[i-1]);

                    for(j=mx+1;j<i;j++)

                     height[j]=height[j]+h;  //do the same as above

                }

        }

        return ans;

    }

    int trap(vector<int>& height) {

        int n=height.size(),i,j;

        if(n==0 || n==1 || n==2)

         return 0;

        i=0;

        int ans=0;

        while(height[i]==0)

         i++;

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

            if(height[i]<=height[i-1]){  //if adjacent bars have equal heights no water can be stored so check for next

                continue;

            }

            else

            {

                j=i-1;

                int mx=j;

                while(j>=0){

                    if(height[j]>=height[i])  //if left bar has height equal to right bar

                     {

                         mx=j;

                         ans+=fun(height,i,j,mx); //calculate area and update height

                         break;

                     }

                     else if(height[j]>height[j+1])  //do the same if left has greater height

                     {

                          mx=j;

                          ans+=fun(height,i,j,mx);

                     } //if left bar has less area then no water can be stored

                     j--;

                }

            }

        }

        return ans;

    }

};

#LeetCode# Multiply Strings lenthy but straightforward algorithm!

class Solution {

public:

   void add(char str1[],char str2[]){  //function to add two strings

       int l1=strlen(str1);

       int l2=strlen(str2);

      // char result[100000];

       int i=l1-1,j=l2-1;

      // cout << l1 << " " << l2 << endl;

       int carry=0;

       stack < int > s;

       while(i>=0 && j>=0){

           int sum=carry+(str1[i]-'0')+(str2[j]-'0');

           carry=sum/10;

           sum=sum%10;

           s.push(sum+48);

           i--;

           j--;

       }

       if(i==-1 && j==-1 && carry!=0){

           s.push(carry+48);

       }

       if(i>=0){

           while(i>=0){

           int sum=carry+(str1[i]-'0');

           carry=sum/10;

           sum=sum%10;

           s.push(sum+48);

  i--;}

       if(i==-1 && carry!=0){

           s.push(carry+48);

       }

       }

       if(j>=0){

           while(j>=0){

           int sum=carry+(str2[j]-'0');

           carry=sum/10;

           sum=sum%10;

           s.push(sum+48);

  j--;}

       if(j==-1 && carry!=0){

           s.push(carry+48);

          }

       }

      int k=0;

      while(!s.empty()){

          str1[k]=s.top();

          s.pop();

          k++;

      }

      str1[k]='\0';

      //return result;

     

   }

    string multiply(string num1, string num2) {

        int l1=num1.size();

        int l2=num2.size();

        if(num1[0]=='0')

          return "0";

        if(num2[0]=='0')

          return "0";

        char mult[100000];

        char result[100000];

        result[0]='\0';

        if(l1==0 && l2==0)

          return "";

        if(l1>=l2){   //if nums2 is smaller

       

            int j=l2-1;

            stack < char > s;

            int cnt=0;

            while(j>=0){

            int n1=num2[j]-'0';

            int i=l1-1;

              int carry=0;

            int c=0;

            while(c!=cnt){

             s.push(48);

             c++;}

             while(i>=0){

             int n2=num1[i]-'0';

             int sum=carry+(n1*n2);

             carry=(sum)/10;

             s.push((sum%10)+48);

             i--;

             }

             if(carry){

                 s.push(carry+48);

             }

             int k=0;

             while(!s.empty()){

                 mult[k++]=s.top();

                 s.pop();

             }

             mult[k]='\0';


             add(result,mult);

             cnt++;

j--;

            }

        }

        else{ //if nums1 is smaller

            int j=l2-1;

            stack < char > s;

            int cnt=0;

            while(j>=0){

            int n1=num2[j]-'0';

            int i=l1-1;

            int carry=0;

            int c=0;

            while(c!=cnt){

             s.push(48);

             c++;}

             while(i>=0){

             int n2=num1[i]-'0';

             int sum=carry+(n1*n2);

             carry=(sum)/10;

             s.push((sum%10)+48);

             i--;

             }

             if(carry){

                 s.push(carry+48);

             }

             int k=0;

             while(!s.empty()){

                 mult[k++]=s.top();

                 s.pop();

             }

             mult[k]='\0';


             add(result,mult);


             cnt++;

j--;

            }

        }

        return (string)result;

    }

};