stack : gfg and other selected Ques Level Wise

                                 design and implementation





                                          Basic/Easy Level

Check for Balanced Brackets in an expression (well-formedness) using Stack:

Example: 

Input: exp = “[()]{}{[()()]()}” 
Output: Balanced

Input: exp = “[(])” 
Output: Not Balanced 

  bool ispar(string s)
    {
        stack<char> st;
        
        for(auto x:s){
            // push  when open bracket
            if(x=='(' || x=='{' || x=='['){
                st.push(x);
                continue;
            }
            // most imp
            //if stack is empty, then  x not be closing bracket
            // mtlb jo hm closinng push krne ja rhe hai, uska opening stack me phle se hona chaiye
            if(st.empty()) return false;
            
            //pop when closing bracket and its opening matching with top of stack
            if(x==')' && st.top()=='(') st.pop();
            else if(x=='}' && st.top()=='{') st.pop();
            else if(x==']' && st.top()=='[') st.pop();
            else return false;
        }
        //in last, if stack becomes empty then balanced otherwise not
        if(st.empty()) return true;
        return false;
    }




----


                                                Medium Level

Next Greater Element

For the input array [4, 5, 2, 25],'
Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1  https://www.geeksforgeeks.org/next-greater-element/


 vector<long long> nextLargerElement(vector<long long> arr, int n){
   
        unordered_map<long long,long long>mp;
        
        stack<long long> st;
        //reverse iterate
          for(int i=n-1;i>=0;i--){
            
            while(true){
                if(st.empty() || st.top()>arr[i]) break;
                st.pop();
            }
          
          mp[arr[i]]=st.empty()?-1:st.top();
          st.push(arr[i]);
        }
        vector<long long> v;
        
        for(auto x:arr) v.push_back(mp[x]);
     return v;
    }





---------------

Comments

Post a Comment

Popular posts from this blog

c++ oops

Image
   class:   It is a user-defined data type, which holds its own data members and member functions, which can be accessed and used by creating an instance of that class. A class is like a blueprint for an object. blue-print representing a group of objects which shares some common properties and behaviours. object: An Object is an instance of a Class. When a class is defined, no memory is allocated but when it is instantiated (i.e. an object is created) memory is allocated. Member Functions in Classes There are 2 ways to define a member function: Inside class definition Outside class definition To define a member function outside the class definition we have to use the scope resolution :: operator along with class name and function name. C++ Constructor: A constructor in C++ is a special ‘MEMBER FUNCTION’ having the same name as that of its class which is used to initialize some valid values to the data members of an object. It is executed automatically whenever an object o...
Read more

Takeoff (hackerearth.3, datastructure, array 1-D)

      There are three planes  A ,  B  and  C . Plane  A  will takeoff on every  p t h  day i.e.  p ,  2 p ,  3 p  and so on. Plane  B  will takeoff on every  q t h  day and plane  C  will takeoff on every  r t h  day. There is only one runway and the takeoff timing is same for each of the three planes on each day. Your task is to find out the maximum number of flights that will successfully takeoff in the period of  N  days. Note:  If there is collision between the flights no flight will take off on that day. Input Format The first line of the input contains a single integer  T , the number of test cases. Then  T  lines follow each containing four space-separated integers  N ,  p ,  q  and  r  as denoted in the statement. Output Format For each test case print a single integer representing the maximum num...
Read more

Aptitude tricks

Image
                                                                                    Time and Work 1.      Work from Days: If A can do a piece of work in  n  days, then A's 1 day's work = 1 . n 2.      Days from Work: If A's 1 day's work = 1 , then A can finish the work in  n  days. n 3.      Ratio: If A is thrice as good a workman as B, then: Ratio of work done by A and B = 3 : 1. Ratio of times taken by A and B to fin...
Read more