solution of your problems

 detecting cycle in the undirected  graph(dfs,cpp)) ================================================== bool dfs ( vector < vector < int >> g , int s , int par ) { visited [ s ] = 1 ; for ( int i = 0 ; i < g [ s ] . size (); i ++) { if ( visited [ g [ s ] [ i ] ] == 0 ) { par = s ; if ( dfs ( g , g [ s ] [ i ] , par )) return true ; } else { if ( g [ s ] [ i ] != par ) return true ; } } return false ; } /////////////////////////////////////////////////////////////// //// Returns true if the graph contains a cycle, else false. // /////////////////////////////////////////////////////////////// bool isCyclic ( vector < vector < int >> g ) { for ( int i = 0 ; i < g . size (); i ++) visited [ i ] = false ; for ( int u = 0 ; u < g . size (); u ++) if (! visited [ u ] ...

Number of Islands(leetcode,cpp) Given a 2d grid map of '1' s (land) and '0' s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.   Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3...

     Lowest Common Ancestor in a Binary Tree(###,cpp) Given a Binary Tree with all unique values and two nodes value  n1 and n2 . The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.  Example 1: Input: n1 = 2 , n2 = 3     1   /  \   2   3 Output: 1     Example 2: Input: n1 = 3 , n2 = 4         5        /       2     /  \    3   4 Output: 2   ---------------------------------------------------------------------------------------------------------------------------- Node* lca(Node* root ,int n1 ,int n2 ) {     if(root==NULL)       return root;          if(root->data==n1  || root->data=...

Longest Increasing Subsequence   Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101] , therefore the length is 4 .    ============================================================================== code= class Solution { public: int lengthOfLIS(vector<int>& a) { if(a.size()==0) return 0; int dp[a.size()]; for(int i=0;i<a.size();i++) dp[i]=1; int j=0; for(int i=1;i<a.size();i++) { while(j<i) { if(a[j]<a[i]) { dp[i]=max(dp[i],1+dp[j]); } j++; } j=0; } sort(dp,dp+a.size()); return dp[a.size()-1]; } };

 Maximal Rectangle in given matrix with 1,0(cpp, leetcode) ============================================== Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Example: Input: [ ["1","0","1","0","0"], ["1","0"," 1 "," 1 "," 1 "], ["1","1"," 1 "," 1 "," 1 "], ["1","0","0","1","0"] ] Output: 6 ======================================================================================== code .... class Solution { public: int largestRectangleArea(vector<int>& a) { if(a.size()==0) return 0; else if(a.size()==1) return a[0]; stack <int>s; int i=0; int maxm=0; int area=0; while(i<a.size()) ...

Largest Rectangle in Histogram (cpp,using stack,leetcode) =========================   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.   Example: Input: [2,1,5,6,2,3] Output: 10  ============================================================================================  code: class Solution { public: int largestRectangleArea(vector<int>& a) { if(a.size()==0) return 0; else if(a.size()==1) return a[0]; stack <int>s; int i=0; int maxm=0; int area=0; while(i<a.size()) { if(s.empty() || a[i]>=a[s.top()]) { ...

Maximal Square (dp,cpp,leetcode) Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4    problem link====== https://leetcode.com/problems/maximal-square/ ========================================================================================== class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int maxm=0; if(matrix.size()==0) return 0; int t[matrix.size()][matrix[0].size()]; memset(t,0,sizeof(t)); for(int i=0;i<matrix.size();i++) { t[i][0]=matrix[i][0]-48; if(maxm<t[i][0]) maxm=t[i][0]; } for(int i=0;i<matrix[0].size();i++) { t[0][i]=matrix[0][i]-48; if(maxm<t[0][i]) maxm=t[0][i]; } ...

Edit Distance(leetcode, cpp,dp)  ===============================================   Given two words word1 and word2 , find the minimum number of operations required to convert word1 to word2 . You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')  =================================================== class Solution { public:     int minDistance(string w1, string w2)     {         int t[w1.size()+1][w2.size()+1];         for(int  i=0;i<w2.size()+1;i++)         {             t[0][i]=i;         }  ...

 Amazing subarray(cpp,interviewbit) You are given a string S , and you have to find all the amazing substrings of S . Amazing Substring is one that starts with a vowel (a, e, i, o, u, A, E, I, O, U). ================================================= Example Input ABEC Output 6 Explanation Amazing substrings of given string are : 1. A 2. AB 3. ABE 4. ABEC 5. E 6. EC here number of substrings are 6 and 6 % 10003 = 6. =========================================================================================== int Solution::solve(string s) { long int count=0; long int x=0; unordered_map<char,int>m={{'a',1},{'e',1},{'i',1},{'o',1},{'u',1},{'A',1},{'E',1},{'O',1},{'I',1},{'U',1}}; for(long int i=s.size()-1;i>=0;i--) { x++; if(m.find(s[i]) != m.end()) { count=count+x; } } return count%100...

3Sum(cpp,leetcode) Given an array nums of n integers, are there elements a , b , c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]  ================================================================================ class Solution { public: vector<vector<int>> threeSum(vector<int>& a) { sort(a.begin(),a.end()); int left,right; vector<vector<int>>v; if(a.size()<3) { return v; } // left=1; // right=a.size()-1; for(int i=0;i<a.size()-2;i++) { int t=a[i]; left=i+1; right=a.size()-1; if(i>0 && a[i]==a[i-1]) continue; ...

  Palindrome Linked List(cpp) Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->2 Output: false Example 2: Input: 1->2->2->1 Output: true ========================================================================================= class Solution { public: bool isPalindrome(ListNode* head) { stack<int>st; ListNode *temp; temp=head; while(temp) { st.push(temp->val); temp=temp->next; } temp=head; while(temp) { int x=st.top(); st.pop(); if(x!=temp->val) return false; temp=temp->next; } return true; } };  

converts a string to an integer. ============================================== The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. Note: Only the space character ' ' is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2 31 ,  2 31  − 1]. If the numerical value is out of the range of representable values, INT_MAX (2 31  − 1) or INT_MIN (−2 31 ) is returned.   =============================================== Example 1: Input: "42" Output: 42 Example 2: Input: " -42" Output: -42 Explanation: The first non-whitespace character is '-', which is the minus sign.   Then take as many numer...

Invert Binary Tree into its mirror tree.(cpp,leetcode)   input: 4 / \ 2 7 / \ / \ 1 3 6 9   output: 4 / \ 7 2 / \ / \ 9 6 3 1 =============================================== code:-   class Solution { public:     void xx(TreeNode *root)     {          if(root==NULL)             return ;         else         {             invertTree(root->left);             invertTree(root->right);             swap(root->left,root->right);                 ...

  Symmetric Tree(leetcode,cpp):    Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). 1 / \ 2 2 ==>>mirror of itself / \ / \ 3 4 4 3 1 / \ 2 2 ==>> not mirror of iitself \ \ 3 3  ============================================= code:- class Solution { public:     bool ismirror(TreeNode *node1,TreeNode* node2)     {         if(node1==NULL && node2==NULL)             return true;         if(node1==NULL || node2==NULL)             return false;          return node1->val==node2->val && ismirror(node1->left,node2->right) && ismirror(node1->right,node2->left);     }  ...

  Find Mode in Binary Search Tree (the most frequently occurred element) cpp, leetcode --------------------------------------------------------------------------------------------------------------- Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. For example: Given BST [1,null,2,2] , 1 \ 2 / 2   return [2] . =============================================     class Solution { public:     vector<int> findMode(TreeNode* root)     {         stack<TreeNode* >s;         map<int,int>m;         vector<int>v;         int maxm=INT_MIN;                  if(root==NULL)        ...

 Validate Binary Search Tree(cpp, leetcode,tree)  Given a binary tree, determine if it is a valid binary search tree (BST). Example 2: 5 / \ 1 4   / \   3 6 Output: false Explanation: The root node's value is 5 but its right child's value is 4.  ------------------------------------------------------------------------------- class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*>s; vector<int>a; if(root==NULL) return true; s.push(root); root=root->left; while(1) { while(root) { s.push(root); root=root->left; } if(s.empty()) { break; } root=s.top(); s.pop(); a.push_back(root->val); root=root->right; } ...

 Unique Paths II(cp,cpp,dp) A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?     An obstacle and empty space is marked as 1 and 0 respectively in the grid. ////////////////////////////////////////////////////////////////////////////////////////////////////////////// class Solution { public:     int uniquePathsWithObstacles(vector<vector<int>>& a)     {         int n=a.size();         int m=a[0].size();                 int t[n][m];        ...

 Unique Paths -------------------------------------------------------- A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? //////////////////////////////////////////////////////////////////////////////////////////////      class Solution { public:     int uniquePaths(int m, int n)     {         int t[n][m];         for(int i=0;i<n;i++)         {             for(int j=0;j<m;j++)             {            ...

 shortest common supersequence. Given two strings str1 and str2 , return the shortest string that has both str1  and str2  as subsequences.  If multiple answers exist, you may return any of them. Input: str1 = "abac" , str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties. ////////////////////////////////////////////////////////////////////////////////////////////// string shortestCommonSupersequence(string t1, string t2) { int t[t1.size()+1][t2.size()+1]; for(int i=0;i<t1.size()+1;i++) { for(int j=0;j<t2.size()+1;j++) { if(i==0 || j==0) t[i][j]=0; else ...

 Given two strings text1 and text2 , return the length  of their longest common subsequence (leetcode,c++).   Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.  ////////////////////////////////////////////////////////////////////////////////////////    int longestCommonSubsequence(string t1, string t2) {                  int t[t1.size()+1][t2.size()+1];         for(int i=0;i<t1.size()+1;i++)         {             for(int j=0;j<t2.size()+1;j++)             {                 if(i==0 || j==0)         ...

Adding two number represented by linklist (leetcode, cpp solution)     You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.      ---------------------------------------------------------------------------------------------- class Solution { public: ListNode* addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode* temp; temp=l1; int carry=0; while(1) { temp->val=((temp->val+l2->val)); if(temp->next!=NULL && l2->next!=NULL) { ...