Contianer

Stack

Last in first out

empty()

size()

top()

queue uses "front()".

push()

pop()

swap()

int main (){ stack<int> foo, bar; foo.push (10); foo.push(20); foo.push(30); bar.push (111); bar.push(222); foo.swap(bar); while(!foo.empty()) { cout << foo.top() << " "; foo.pop(); } cout << "\n"; while(!bar.empty()) { cout << bar.top() << " "; bar.pop(); } return 0; } foo: 222 111 bar: 30 20 10

[Hard] No.42 Trapping Rain Water

Approach: Stack

Time Complexity: O(N), where N is the number of the list.

Space Complexity: O(N), where N is worst case of the size of stack.

class Solution { public: int trap(vector<int>& height) { int ans = 0, current = 0; stack<int> st; while (current < height.size()) { while (!st.empty() && height[current] > height[st.top()]) { int top = st.top(); st.pop(); if (st.empty()) break; int distance = current - st.top() - 1; int bounded_height = min(height[current], height[st.top()]) - height[top]; ans += distance * bounded_height; } st.push(current++); } return ans; } };

Parentheses related question

Concept

Whenever you encounter an OPENING bracket (LEFT side) i.e. '(', '[', '{', executer PUSH.

Whenever you encounter an CLOSING bracket (RIGHT side) i.e. ')', ']', '}', executer POP.

[Easy] No.20 Valid Parentheses

Approach: Stack

Time Complexity: O(N), where N is the length of string.

Space Complexity: O(N), where N is the length of string.

class Solution { public: bool isValid(string s) { stack<char> stk; for(int i = 0 ; i < s.size() ; i++) { if(s[i] == '(' || s[i] == '{' || s[i] == '[') stk.push(s[i]); else { if(stk.size() == 0) return false; if(s[i] == ')' && stk.top() != '(' || s[i] == '}' && stk.top() != '{' || s[i] == ']' && stk.top() != '[') return false; else stk.pop(); } } return stk.size() == 0 ? true : false; } };

[Hard] No.726 Number of Atoms

Approach: Stack + map

Time Complexity: O(N^2), where N is the length of formula.

Space Complexity: O(N), where N is the length of formula.

class Solution { public: string countOfAtoms(string f) { map<string, int> mp; int num=0, n=f.size(); stack<map<string, int> > st; string str=""; for(int i=0; i<f.size(); i++){ if(f[i]=='('){ //whenever we see '(', we save the exisiting map into stack and clear the map for the rest of the string st.push(mp); mp.clear(); } else if(f[i]==')'){ //whenever we see ')', we pop back the previously saved map and update the current map num=0; while(i+1<n && f[i+1]>='0' && f[i+1]<='9'){ num=(num*10)+(f[i+1]-'0'); i++; } num=max(num, 1); for(auto& it: mp) it.second*=num; for(auto it: st.top()) mp[it.first]+=it.second; st.pop(); } else if(f[i]>='A' && f[i]<='Z'){ str=""; str+=f[i]; while(i+1<n && f[i+1]<='z' && f[i+1]>='a'){ str+=f[i+1]; i++; } num=0; while(i+1<n && f[i+1]>='0' && f[i+1]<='9'){ num=(num*10)+(f[i+1]-'0'); i++; } mp[str]++; if(num>0) mp[str]+=num-1; } } while(!st.empty()){ for(auto it: st.top()) mp[it.first]+=it.second; st.pop(); } string ans=""; for(auto it: mp){ ans+=it.first; if(it.second>1) ans+=to_string(it.second); } return ans; } };