20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Approach: The idea is to use Stack and implement the following algorithm:

1. if the current character is an opening bracket (of any type), push it to the stack and continue with the next character
2. else if the current character is a closing bracket, following cases apply:
1. if stack is empty - return error and exit
2. else if the current character and the stack top forms matching parenthesis i.e. opening and closing brackets are of same type, pop the stack top and continue with the next character otherwise return error and exit
3. Return error if the stack is not empty after all the characters are exhausted otherwise successful

class Solution {
public:
    
    int isMatching(stack<char> &stk, char c){
        if(stk.empty()){
            return 0;
        }
        char topC = stk.top();
        if( (topC == '(' && c == ')') || (topC == '{' && c == '}') || (topC == '[' && c == ']') )
            return 1;
        return 0;
    }
    
    bool isValid(string s) {
        stack<char> stk;
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                    stk.push(s[i]);
                    continue;
            } else if((s[i] == ')' || s[i] == '}' || s[i] == ']') && isMatching(stk, s[i])){
                stk.pop();
                continue;
            }
            return false;
        }
        if(!stk.empty())
            return false;
        return true;
    }
};

Here is the link to the ideone solution : http://ideone.com/jzfJnv

Read More

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Approach: First find the place for the newly arrived interval in the existing intervals. Then perform the approach used in this problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/** * 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) { int i = 0; int n = intervals.size(); vector<Interval> out; //find the location of new interval while(i < n && intervals[i].start < newInterval.start){ i++; } //add the vector at the specified location intervals.insert(intervals.begin() + i, newInterval); //merge the possible intervals stack<Interval> it; it.push(intervals[0]); n = intervals.size(); for(int i = 1; i < n; i++){ Interval topInterval = it.top(); //if start time of next is after the end of the prev, push the next if(intervals[i].start > topInterval.end){ it.push(intervals[i]); }else if(intervals[i].end > topInterval.end){ //if start time of next is before the end of the prev and the end of the next is after the end of the prev, then update the end of the prev topInterval.end = intervals[i].end; it.pop(); it.push(topInterval); } } while(!it.empty()){ Interval curr = it.top(); out.push_back(curr); it.pop(); } //reverse to get the output reverse(out.begin(), out.end()); return out; } };

Read More

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

 /**  
  * Your MinStack object will be instantiated and called as such:  
  * MinStack obj = new MinStack();  
  * obj.push(x);  
  * obj.pop();  
  * int param_3 = obj.top();  
  * int param_4 = obj.getMin();  
  */  
 class MinStack {  
 public:  
   int StckTop;  
   int stck[10000], minStck[10000];  
   /** initialize your data structure here. */  
   MinStack() {  
     StckTop = -1;  
   }  
   void push(int x) {  
     if(StckTop == -1){  
       StckTop++;  
       stck[StckTop] = x;  
       minStck[StckTop] = x;  
     }else{  
       int mini = minStck[StckTop];  
       StckTop++;  
       stck[StckTop] = x;  
       if(x < mini){  
         minStck[StckTop] = x;  
       }else{  
         minStck[StckTop] = mini;  
       }  
     }  
   }  
   void pop() {  
     if(StckTop == -1){  
       cout << "Stack underflow";  
     }else{  
       StckTop--;  
     }  
   }  
   int top() {  
     if(StckTop == -1){  
       cout << "Stack underflow";  
       return INT_MIN;  
     }  
     return stck[StckTop];  
   }  
   int getMin() {  
     if(StckTop == -1){  
       cout << "Stack underflow";  
       return INT_MIN;  
     }  
     return minStck[StckTop];  
   }  
 };  

Read More