Code Blogs

 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/   class Solution { public:     int findMin(vector<int>& num) {         int start=0,end=num.size()-1;                  while (start<end) {             if (num[start]<num[end])                 return num[start];                          int mid = (start+end)/2;                          if (num[mid]>=num[start]) {                 start = mid+1;   ...

https://leetcode.com/problems/palindrome-linked-list/  brute force: put all the digits in array check if that is a palindrome or not optimal: (algo) 1) find middle(slow pointer will be the middle) 2) reverse the right half of the linkedlist 3)move slow pointer by one more step 4)take dummy node and place at the head 5)start traversing both dummy and slow 6)when slow reach null and all are same then its a palindrome class Solution { public:     ListNode* reverselist(ListNode* head){         ListNode* prev=NULL;         ListNode* curr=head;         ListNode* nex=NULL;         while(curr!=NULL){             nex=curr->next;             curr->next=prev;             p...

https://www.hackerrank.com/challenges/find-digits/problem  #include   < bits/stdc++.h > using   namespace   std ; void   findDigits ( int   n )   {      int   count = 0 ;      int   num = n ;      while ( n > 0 ){          int   last = n % 10 ;          if ( last != 0   &&   num % last   ==   0 )           count ++;          n = n / 10 ;      }      cout << count << endl ; } int   main (){      int   t ;      cin >> t ;      for ( int   i = 0 ; i < t ; i ++){          int   no ;     ...

 https://leetcode.com/problems/string-to-integer-atoi/ class Solution { public:     int myAtoi(string str) {     int result=0;   //Stores and returns the integer converted value for str     int i=0;    //just a current character pointer for string     int sign = 1;   //multiplied at the end to result to determine if the string is +ve or -ve     while(str[i]==' ') i++;//to ignore the starting blank spaces      //Check the sign of string (+ or -)      if (str[i] == '-' || str[i] == '+') {                 sign = (str[i++] == '-') ? -1 : 1;             }     //Now traverse the entire string and convert it into integer     while(str[i] >= '0' && str[i] <= '9')  ...

 https://leetcode.com/problems/reverse-nodes-in-k-group/ class Solution { public:     ListNode* reverseKGroup(ListNode* head, int k) {         if(head ==NULL || k==1) return head;         ListNode* dummy = new ListNode(0);         dummy->next=head;         ListNode* cur=dummy, *nex=dummy ,*pre=dummy;         int count=0;         while(cur->next!=NULL){             cur=cur->next;             count++;         }         while(count>=k){             cur=pre->next;          ...

https://www.interviewbit.com/old/problems/diffk-ii/  int Solution::diffPossible(const vector<int> &A, int B) {     if (A.size() < 2 || B < 0)         return 0;              unordered_set<int> st;          for(auto i = 0; i < A.size(); i++)     {         int Aj = A[i] - B;                  int Ai = A[i] + B;                  if (st.find(Aj) != st.end())             return 1;         if (st.find(Ai) != st.end())             return 1;              ...

https://leetcode.com/problems/intersection-of-two-linked-lists/ brute force: start with link list 1 : check if that node is same as all other nodes of linklist 2; traverse for all nodes of linklist 1 2nd solution : use hash map traverse and hash the address of the one linklist: then for the second linklist if the address match any of the address of the hash , then that node is ans 3rd solution: create 2 dummy node: find the length of both the linklist subtract the length of long -short move the node of long by the subtracted ans then traverse both the dummy node to find where the node matches 4th solution:   class Solution { public:     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {         if(headA==NULL  || headB==NULL) return NULL;         ListNode *a=headA;         ListNode *b=headB;         while(a!=b...

 https://www.hackerrank.com/challenges/electronics-shop/problem?h_r=profile int   getMoneySpent ( vector < int >   keyboards ,   vector < int >   drives ,   int   b )   {      int   res =- 1 ; for ( int   i = 0 ; i < keyboards . size (); i ++){      for ( int   j = 0 ; j < drives . size (); j ++){          if (( keyboards [ i ]+ drives [ j ])> res   &&   ( keyboards [ i ]+ drives [ j ])<= b ){              res = max ( keyboards [ i ]+ drives [ j ], res );          }      } } return   res ; }  

https://www.interviewbit.com/old/problems/xor-between-two-arrays/ int Solution::solve(vector<int> &A, vector<int> &B) {     int maxXor=0,mask=0; unordered_set<int> s1,s2; for(int i=31;i>=0;i--) {     int newMax=(maxXor|(1<<i));     mask|=(1<<i);     for(int j=0;j<A.size();j++)     {         s1.insert(A[j]&mask);     }     for(int j=0;j<B.size();j++)     {         s2.insert(B[j]&mask);     }     for(auto prefix: s1)     {         if(s2.count(prefix^newMax))             {                 maxXor=newMax;       ...

 https://leetcode.com/problems/reverse-pairs/ BRUTE FORCE SOLUTION  class Solution { public:     int reversePairs(vector<int>& a) {         int count=0;         for(int i=0;i<a.size()-1;i++)         {             for(int j=1;j<a.size();j++)             {                 if(i!=j && a[i]>a[j]){                     if(a[i]>2*a[j]){                         count++;              ...

 https://www.hackerrank.com/challenges/game-of-stones-1/problem?h_r=internal-search string   gameOfStones ( int   n )   {      string   ans = "" ;      if ( n % 7 == 0   ||   n % 7 == 1 )   ans += "Second" ;      else   ans += "First" ; return   ans ; }

https://www.interviewbit.com/old/problems/longest-substring-without-repeat/  int Solution::lengthOfLongestSubstring(string A) {     if (A.empty())         return 0;          unordered_map<char, int> ls;     int count = 0;     int ans = 0;          auto q = 0;     auto size = A.size();          while (q<size)     {         if (ls.find(A[q]) == ls.end())         {             ls[A[q]] = q;             ++count; ++q;         }         else         {         ...

https://leetcode.com/problems/valid-palindrome/ class Solution { public:     bool isPalindrome(string s) {         transform(s.begin(), s.end(), s.begin(), ::tolower);         string str = "";         for(int i = 0 ; i < s.length() ; i++){             if((s[i]>='a' && s[i]<='z') || (s[i]>='0' && s[i]<='9')){                 str += s[i];             }         }         string str2 = str;         reverse(str.begin(),str.end());         return str == str2;     } };

 https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem Node   *   insert ( Node   *   root ,   int   value )   {          Node   *   newNode   =   new   Node ( value );      // newNode->data = value;      newNode -> left   =   NULL ;      newNode -> right   =   NULL ;      if ( root   ==   NULL ){         root   =   newNode ;      }      else   if ( root -> data   <   value   ){          root -> right   =   insert ( root -> right   ,   value );      }        else   root -> left   =   insert ( roo...

 https://leetcode.com/problems/add-digits/   class Solution { public:     int addDigits(int num) {         if(num%9 == 0 && num!=0)         return 9;         return (num%9);     } };

 https://www.interviewbit.com/old/problems/merge-k-sorted-arrays/ vector<int> Solution::solve(vector<vector<int> > &A) {     priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;     for(int i=0;i<A.size();i++)     pq.push(make_pair(A[i][0],make_pair(0,i)));     vector<int> v3;     while(!pq.empty())     {         v3.push_back(pq.top().first);         int i=pq.top().second.first,j=pq.top().second.second;         pq.pop();         if(i<A[j].size()-1)         {             i++;         ...

 https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists/problem int   findMergeNode ( SinglyLinkedListNode *   head1 ,   SinglyLinkedListNode *   head2 )   { SinglyLinkedListNode   * la   =   head1 ; SinglyLinkedListNode   * sm   =   head2 ; int   l1 = 0 , l2 = 0 ; while ( head1 != NULL ) {      l1 ++;      head1   =   head1 -> next ; } head1   =   la ; while ( head2 != NULL ) {      l2 ++;      head2   =   head2 -> next ; } head2   =   sm ; if ( l1 > l2 ) {      la   =   head1 ;      sm   =   head2 ; } else   {      la   =   head2 ;      sm   =   head1 ; } int   f   = 0 ; l1   =   abs ( l1 - l2 );      ...

 https://leetcode.com/problems/unique-paths/ //recursion (time limit exceed) int solve ( int i, int j, int m, int n) { if (i>=m||j>=n) return 0 ; if (i==m -1 &&j==n -1 ) return 1 ; return solve(i+ 1 ,j,m,n)+solve(i,j+ 1 ,m,n); } int uniquePaths ( int m, int n) { return solve( 0 , 0 ,m,n); }  //dp (recursive+memoization) class Solution { public:     int solve(int i,int j,int m,int n,vector<vector<int>>&dp){         if(i>=m||j>=n) return 0;         if(i==m-1 && j==n-1) return 1;                  if(dp[i][j]!=-1)         {             return dp[i][j];         }   ...

 https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/ https://gist.github.com/SuryaPratapK/d73b9a97c2c8a2af762af106b794ad2d      //soln class Solution { map<int,map<int,multiset<int>>> mymap; void solve(TreeNode *curr,int col,int row) { if(!curr) return; mymap[col][row].insert(curr->val); solve(curr->left,col-1,row+1); solve(curr->right,col+1,row+1); } public: vector<vector<int>> verticalTraversal(TreeNode* root) { solve(root,0,0); vector<vector<int>> ans; ...

 https://www.interviewbit.com/old/problems/is-rectangle/ int Solution::solve(int A, int B, int C, int D) {      if (((A==B)&&(C==D))||((A==C)&&(B==D))||((A==D)&&(B==C))){         return 1;     }else{         return 0;     } }  

 https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem      int   height ( Node *   root )   {         if (! root )   return   - 1 ;         return   max ( height ( root -> right ), height ( root -> left ))+ 1 ;      }  

 https://www.hackerrank.com/challenges/tree-level-order-traversal/problem void   levelOrder ( Node   *   root )   {           queue < Node  *> q ;           q . push ( root );           while (! q . empty ())           {               Node *   temp = q . front ();               q . pop ();               cout << temp -> data << " " ;               if ( temp -> left ){                   q . push ( temp -> le...

 https://leetcode.com/problems/majority-element-ii/ class Solution { public:     vector<int> majorityElement(vector<int>& nums) {         //Boyer Moore Voting Algorithm         int size=nums.size();         int num1=-1;         int num2=-1;         int c1=0;         int c2=0;         for(int i=0;i<size;i++)         {             if(nums[i]==num1) c1++;             else if(nums[i]==num2) c2++;             else if(c1==0){                 nu...

 https://leetcode.com/problems/majority-element/ MOORE'S VOTING ALGORITHM class Solution { public:     int majorityElement(vector<int>& nums) {         int count=0;         int n=nums.size();         int ele=0;         for(int i=0;i<n;i++)         {              if(count==0)              {               ele=nums[i];              }             if(ele==nums[i])             {           ...

 https://leetcode.com/problems/search-a-2d-matrix/   (ROWS ARE ONLY SORTED IN ROWS) (The first integer of each row is greater than the last integer of the previous row.) class Solution { public:     bool searchMatrix(vector<vector<int>>& matrix, int target) {         if(!matrix.size()) return false;         int n=matrix.size();         int m=matrix[0].size();         int low=0;         int high=(n*m)-1;         while(low<=high)         {             int mid=low+(high-low)/2;             if(matrix[mid/m][mid%m]==target) return true;           ...

 https://practice.geeksforgeeks.org/problems/search-in-a-matrix17201720/1 (ROWS AND COLUMNS ARE SORTED) class Solution{ public:        int matSearch (vector <vector <int>> &mat, int N, int M, int X)     {         int i=0;         int j=M-1;         while(i<N && j>=0)         {             if(mat[i][j]==X) return 1;             else if (mat[i][j]<X) i++;             else j--;         }         return 0;     } };  

 https://www.interviewbit.com/old/problems/reverse-integer/ int Solution::reverse(int n) {  long long res=0;     while(n){         res=res*10+n%10;         if(res>INT_MAX||res<INT_MIN) return 0;         n=n/10;     }     return res; }  

 https://www.hackerrank.com/challenges/compare-two-linked-lists/problem bool   compare_lists ( SinglyLinkedListNode *   head1 ,   SinglyLinkedListNode *   head2 )   { if ( head1 == NULL   &&   head2 != NULL )   return   0 ; if ( head2 == NULL   &&   head1 != NULL )   return   0 ; if ( head1 == NULL   &&   head2 == NULL )   return   1 ; SinglyLinkedListNode *   temp1   = head1 ; SinglyLinkedListNode *   temp2   = head2 ; while ( temp1 -> next != NULL   &&   temp2 -> next != NULL ) {      if ( temp1 -> data == temp2 -> data )      {          temp1 = temp1 -> next ;          temp2 = temp2 -> next ;      }      else   if ( temp1 -> data != temp2 -> data ) ...

 https://www.interviewbit.com/old/problems/balanced-parantheses/ int Solution::solve(string A) { int n=A.size(); stack<char> s; int i=0; while(i<n){ if(s.empty()) s.push(A[i]); else{ if(s.top()=='(' && A[i]==')') s.pop(); else if(s.top()=='(' && A[i]=='(') s.push(A[i]);     }     i++; } if(s.empty())     return 1; else     return 0; }

https://leetcode.com/problems/fizz-buzz/   class Solution { public:     vector<string> fizzBuzz(int n) {         vector<string> result;                  for (auto i = 1; i <= n; ++i) {             string str;             if (i % 3 == 0) str += "Fizz";             if (i % 5 == 0) str += "Buzz";             if (str.empty()) str = to_string(i);                          result.push_back(str);         }                  return ...

 https://www.interviewbit.com/old/problems/minimum-lights-to-activate/ int Solution :: solve ( vector < int > & A , int B ) { int n = ( int ) A . size (), i = 0 , ans = 0 ; if ( B == 0 ) return - 1 ; //Start from 0th index while ( i < n ) { int idx = - 1 ; //check range [X-B+1, X+B-1] and find rightmost bulb for ( int j = max ( 0 , i - B + 1 ); j < min ( n , i + B ); j ++ ) { if ( A [ j ] == 1 ) idx = j ; } if ( idx == - 1 ) return - 1 ; ans ++ ; //Start now from index which is outside the current selected bulb i = idx + B ; } return ans ; }

 https://www.interviewbit.com/old/problems/median-of-array/ https://leetcode.com/problems/median-of-two-sorted-arrays/  we need to divide the 2 array into 2 parts: l1=arr1[cut1-1]    r1=arr1[cut1] l2=arr2[cut2-1]    r2=arr2[cut2]   if none in left initialize with INT_MIN (l1,l2) if none in left initialize with INT_MAX (r1,r2) cut1=low+high/2 cut2=(n1+n2+1)/2-cut1            //work for both even and odd median= max(l1,l2) + min(r1,r2) /2                 >>even median =max(l1,l2)                      >>odd     class Solution { public:     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {         if(nums2.size()<nums1.size()){   ...