Code Blogs

 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75924/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems   class Solution { public:     int maxProfit(vector<int>& prices) {         int n=prices.size();         if(n<=1){             return 0;         }         int A=0;         int B=-prices[0];         int C=0;         for(int i=1;i<prices.size();i++){             int temp=A;             A=max(A,C);             C=B+prices[i];   ...

 https://www.interviewbit.com/old/problems/diagonal-traversal/   void preorder(map<int,vector<int> > &mp, int k, TreeNode* root){         if(root == NULL){             return;         }         mp[k].push_back(root->val);         preorder(mp, k+1, root->left);         preorder(mp,k,root->right);         return;     } vector<int> Solution::solve(TreeNode* A) {     vector<int> v;         map<int, vector<int>> mp;         preorder(mp, 0, A);         for(auto a = mp.begin(); a != mp.end(); a++){        ...

 https://leetcode.com/problems/rotate-array/  brute force:  for(int i=0;i<k;i++){             int last=nums[nums.size()-1];             for(int j=nums.size()-1;j>0;j--){                 nums[j]=nums[j-1];             }             nums[0]=last;         } soln 1: class Solution { public:     void rotate(vector<int>& nums, int k) {           k = k % nums.size();         reverse(nums.begin(), nums.end());         reverse(nums.begin(), nums.begin() + k);         reverse(nums...

 https://leetcode.com/problems/perfect-squares/ class Solution { public:     int numSquares(int n) {         if (n <= 0)         {             return 0;         }         // cntPerfectSquares[i] = the least number of perfect square numbers         // which sum to i. Note that cntPerfectSquares[0] is 0.         vector<int> cntPerfectSquares(n + 1, INT_MAX);         cntPerfectSquares[0] = 0;         for (int i = 1; i <= n; i++)         {             // For each i, it must be the sum of some number (i - j*j) and     ...

 https://www.interviewbit.com/old/problems/justified-text/ vector<string> Solution::fullJustify(vector<string> &words,  int  L) {      vector<string> res;          int  k =  0 , l =  0 ;          for  ( int  i =  0 ; i < words.size(); i += k) {              for  (k = l =  0 ; i + k < words.size() && l + words[i+k].size() <= L - k; k++) {                 l += words[i+k].size();             }      ...

 https://www.interviewbit.com/problems/power-of-2/ string mulby2(string s){      int  n = s.size();      int  carry =  0 ;      int  temp;      for ( int  i=n- 1 ;i>= 0 ;i--){         temp = ((s[i] -  '0' )* 2 );         s[i] =  '0' +((temp+carry)% 10 );         carry = (temp+carry)/ 10 ;     }      if (carry)     s.insert ( 0 ,  1 , carry+ '0' );      return  s; } int  Solution::power(string A) {      string s =  "1" ;      while ( true ){         s = mulby2(s);  ...

 https://www.hackerrank.com/challenges/lisa-workbook/problem int   workbook ( int   n ,   int   k ,   vector < int >   arr )   { int   ans = 0 ; int   p = 1 ; //page for ( int   i = 0 ; i < arr . size (); i ++){      int   m = 1 ;      int   q = arr [ i ];//no of ques      for ( int   j = 1 ; j <= q ; j ++){          if ( j <= k * m ){              if ( p == j )                  ans ++;             }          else {              p ++;              if ( p == j ) ...

 https://www.interviewbit.com/problems/grid-unique-paths/ int  Solution::uniquePaths( int  N,  int  M) {      long   long  ans =  1 ;      for  ( int  i = M; i < (N + M -  1 ); i++) {         ans *= i;         ans /= (i - M +  1 );     }      return  ans; }  

 https://www.interviewbit.com/problems/burn-a-tree/   int  dfs (TreeNode *A,  int  &h,  int  &ans,  int  B) { if  (!A) return   0 ; int  hr =  0 , hl =  0 ; bool  leftfire =  false , rightfire =  false ; leftfire = dfs (A->left, hl, ans, B); rightfire = dfs (A->right, hr, ans, B); if  (!leftfire && !rightfire)     h = max (hr, hl) +  1 ; else   if  (leftfire)     h = hl+ 1 ; else  h = hr+ 1 ; if  (B == A->val || leftfire || rightfire) {     ans = max (ans, hr + hl +  1 );      return   1 ; } return   0 ; } int  Solution::solve(TreeNode...

 https://leetcode.com/problems/word-search-ii/   class TrieNode{ public:     bool is_end;     vector<TrieNode*> children;     TrieNode(){         is_end=false;         children=vector<TrieNode*>(26, NULL);     }    }; class Trie{ public:     TrieNode* getRoot(){return root;}     Trie(vector<string>& words){         root=new TrieNode();         for(int i=0; i<words.size(); ++i)             addWord(words[i]);     }     void addWord(const string& word){         TrieNode* cur=root;         for(int i=0; i<word.size(); ++i){       ...

 https://www.interviewbit.com/problems/search-in-bitonic-array/ // Function for binary search in ascending part of array  int  asc(vector< int > A,  int  low,  int  high,  int  B)  {      while  (low <= high)     {          int  mid = low + (high - low) /  2 ;          if  (A[mid] == B)              return  mid;          else   if  (A[mid] > B)             high = mid -  1 ;          else          ...

 https://leetcode.com/problems/implement-trie-prefix-tree/ class Trie { public:     struct Node{             bool isEnd = false;         Node* children[26] = {NULL};     };          Node* root;     Trie() {         root = new Node();  // initialising the root     }          void insert(string word) {         Node* curr = root;         for(int i=0;i<word.size();i++) {             int idx = word[i]-'a';             if(curr->children[idx]==NULL) {                 curr->children[idx] = ...

 https://www.interviewbit.com/problems/insertion-sort-list/ ListNode* Solution::insertionSortList(ListNode* A) {     ListNode* first = A;     A=A->next;     ListNode* temp_first = first;      int  temp;      while  (A!=NULL)     {        if (temp_first!=A)       {          if  (temp_first->val >= A->val)         {           temp = A->val;           A->val = temp_first->val;           temp_first->val = temp;         } ...

 https://leetcode.com/problems/implement-queue-using-stacks/ class MyQueue { public:     stack<int> s1;     stack<int> s2;     MyQueue() {              }          void push(int x) {         while(!s1.empty()) {             s2.push(s1.top());             s1.pop();         }         s2.push(x);         while(!s2.empty()) {             s1.push(s2.top());             s2.pop();         }     }          int pop() {  ...

 https://leetcode.com/problems/word-search/ class Solution { public:     int x[4]={0,1,-1,0};     int y[4]={-1,0,0,1};     bool solve(int i,int j,vector<vector<char>>& board,vector<vector<int>>&vis,int k,string word,int m,int n)     {         if(k==word.size())             return true;         if(i<0||j<0||i>=m||j>=n)             return false;         if(vis[i][j]||word[k]!=board[i][j])             return false;         vis[i][j]=1;         for(int r=0;r<4;r++)         {       ...

 https://www.interviewbit.com/old/problems/merge-k-sorted-lists/ struct Compare {     bool operator()(ListNode* const& a, ListNode* const& b)     {         return a->val > b->val;     } }; ListNode* Solution::mergeKLists(vector<ListNode*> &A) {     if (A.empty())         return NULL;     ListNode* dummy = new ListNode(0);     ListNode* tail = dummy;     priority_queue<ListNode*, vector<ListNode*>, Compare> PQ;          for (auto i = 0; i<A.size(); ++i)     {         if (A[i])             PQ.emplace(A[i]);     }          while (!PQ.empty())     {      ...

 https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/775798/c%2B%2B-Four-Solution-or-O-(N*N)-to-greater-O(N)-or-Explain-All   class Solution { public:     vector<int> findDuplicates(vector<int>& nums) {         unordered_map<int,int>m;         vector<int>ans;         for(int i=0;i<nums.size();i++){             m[nums[i]]++;         }         for(auto it:m){             if(it.second>=2){                 ans.push_back(it.first);             }         }    ...

 https://www.interviewbit.com/problems/array-3-pointers/ int  Solution::minimize( const  vector< int > &A,  const  vector< int > &B,  const  vector< int > &C) { int  i= 0 ,j= 0 ,k= 0 ; int  res=INT_MAX; while (i<A.size() && j<B.size() && k<C.size()){      int  temp1=max(abs(A[i] - B[j]), abs(B[j] - C[k]));      int  temp=max(abs(A[i]-C[k]),temp1);      if (temp<res)res=temp;      if (A[i] <= B[j] && A[i] <=C[k])i++;      else   if (B[j] <= A[i] && B[j] <=C[k])j++;      else  k++; } return  res; }  

 https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=linked-lists DoublyLinkedListNode *   sortedInsert ( DoublyLinkedListNode *   head ,   int   data )   { if (! head )   return   head ; DoublyLinkedListNode *   node = new   DoublyLinkedListNode ( data ); DoublyLinkedListNode *   temp = head ; if ( head -> data >= node -> data ){      head -> prev = node ;      node -> next = head ;      return   node ; } while ( temp != NULL ){     if ( temp -> data >= node -> data ){         temp -> prev -> next = node ;         node -> prev = temp -> prev ;         temp -> prev = node ;  ...

 https://leetcode.com/problems/merge-two-sorted-lists/ class Solution { public:     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {       if(l1==NULL) return l2;       if(l2==NULL) return l1;        ListNode* res;       if(l1->val<=l2->val){           res=l1;           res->next=mergeTwoLists(l1->next,l2);       }         else{             res=l2;             res->next=mergeTwoLists(l1,l2->next);         }         return res;     } };  class Solution { public: ListNode* mergeTwoLists(Li...

 https://leetcode.com/problems/climbing-stairs/ class Solution { public:     int dp[46];     int climbStairs(int n) {        if(dp[n]!=0)return dp[n];        if(n==2) {            dp[n]=2;            return 2;        }        if(n==1){            dp[n]=1;          return 1;          }               dp[n]= climbStairs(n-1)+climbStairs(n-2);         return dp[n];     } };

 https://www.interviewbit.com/old/problems/container-with-most-water/ class Solution { public:     int maxArea(vector<int>& A) {     int l=0;     int r=A.size()-1;     int area=0;     while(l<r)     {         area=max(area,min(A[l],A[r])*(r-l));         if(A[l]<A[r])              l++;         else              r--;     }     return area;     } };

 https://leetcode.com/problems/valid-anagram/   class Solution { public:     bool isAnagram(string s, string t) {       if(s.length()!=t.length()){           return false;       }         int n=s.length();         unordered_map<char,int>m;         for(int i=0;i<n;i++){             m[s[i]]++;             m[t[i]]--;         }         for(auto j : m){             if(j.second){                 return false;         ...

https://leetcode.com/problems/ransom-note/ class Solution { public:     bool canConstruct(string ransomNote, string magazine) {         int count[26]={0};         for(char c : magazine){             count[c-'a']++;         }         for(char ch : ransomNote){             if(count[ch-'a']-- <=0){                 return false;             }         }         return true;     } };  class Solution { public:     bool canConstruct(string ransomNote, string magazine) {      ...

 https://leetcode.com/problems/first-unique-character-in-a-string/ class Solution { public:     int firstUniqChar(string s) {        unordered_map<char,int>m;         for(int i=0;i<s.length();i++){  //traversed and stored in map the char and its count             m[s[i]]++;         }         for(int j=0;j<s.length();j++){ //traversed again and find the first index where the the m[s[i]]==1             if(m[s[j]]==1){                 return j;             }         }         return -1;     } };  ...

https://leetcode.com/problems/island-perimeter/  class Solution { public:     int islandPerimeter(vector<vector<int>>& grid) {         int m=grid.size();//row         int n=grid[0].size();//col         int ans=0;         for(int i=0;i<m;i++){             for(int j=0;j<n;j++){                 if(grid[i][j]==1){                     ans+=4;//if 1 in matrix perimeter 4                     if(i<m-1 && grid[i+1][j]) ans--;//if neighbours are 1 we reduce ans      ...

https://www.interviewbit.com/old/problems/water-flow/  int n,m; void dfs(int i,int j,vector<vector<int> > &A,vector<vector<int> > &b) // b is the visited array {     if(b[i][j]==0) b[i][j]=1;     if(i>0 && A[i-1][j]>=A[i][j] && b[i-1][j]==0) dfs(i-1,j,A,b);     if(j>0 && A[i][j-1]>=A[i][j] && b[i][j-1]==0)  dfs(i,j-1,A,b);     if(j<m-1 && A[i][j+1]>=A[i][j] && b[i][j+1]==0) dfs(i,j+1,A,b);     if(i<n-1 && A[i+1][j]>=A[i][j] && b[i+1][j]==0) dfs(i+1,j,A,b);     return;      } int Solution::solve(vector<vector<int> > &A) {     n=A.size();      m=A[0].size();     vector<vector<int> > blue(n,vector<int> (m,0));     vector<vector<int> > red(n,vector...

 https://leetcode.com/problems/jump-game/ class Solution { public:     bool canJump(vector<int>& nums) {      int n=nums.size();       int reachable=0;                  for(int i=0;i<n;i++){                          if(i>reachable) return false;                          reachable=max(reachable,i+nums[i]);                      }         return true;     } };

 https://www.interviewbit.com/problems/simple-queries/ #define  ll  long   long   int const   int  mn =  1e5  +  5 ; const  ll mod =  1e9  +  7 ; ll power(ll a, ll g) {ll ag =  1 ;  while (g){ if (g& 1 ) ag = (ag%mod * a%mod)%mod; a = (a%mod * a%mod)%mod; g >>=  1 ;}  return  ag;} ll p[mn]; void  pre_compute_product_of_divisors() {     p[ 0 ] =  0 ; p[ 1 ] =  1 ;      if (p[ 2 ] !=  0 )  return ;      for (ll i =  2 ; i < mn; i +=  1 ) {          if (p[i] ==  0 ) {             p[i] =  2 ;...