Seven Chapter
Depth-first Search && Breadth-first Search
1 Same Tree
https://leetcode.com/problems/same-tree/
>
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q) return true;
if((!p&&q)||(p&&!q) return false;
if(p->val!=q->val) return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
DFS
>
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q) return true;
if((!p||!q) return false;
stack<TreeNode*> st;
st.push(q);
st.push(p);
while(!st.empty()){
TreeNode *t1,*t2;
t1=st.top();
st.pop();
t2=st.top();
st.pop();
if(t1->val!=t2->val) return false;
if(t1->right&&t2->right){
st.push(t2->right);
st.push(t1->right);
}else if(t1->right||t2->right) return false;
if(t1->left&&t2->left){
st.push(t2->left);
st.push(t1->left);
}else if(t1->left||t2->left) return false;
}
return true;
}
BFS
>
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q) return true;
if((!p||!q) return false;
queue<TreeNode*> qt;
qt.push(p);
qt.push(q);
while(!qt.empty()){
TreeNode *t1,*t2;
t1=qt.front();
qt.pop();
t2=qt.front();
qt.pop();
if(t1->val!=t2->val) return false;
if(t1->left&&t2->left){
qt.push(t1->left);
qt.push(t2->left);
}else if(t1->left||t2->left) return false;
if(t1->right&&t2->right){
qt.push(t1->right);
qt.push(t2->right);
}else if(t1->right||t2->right) return false;
}
return true;
}
2 Symmetric Tree
https://leetcode.com/problems/symmetric-tree/
>
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return isSym(root->left,root->right);
}
bool isSym(TreeNode* left,TreeNode* right){
if(!left&&!right) return true;
if(!left||!right) return false;
if(left->val!=right->val) return false;
return isSym(left->left,right->right)&&isSym(left->right,right->left);
}
DFS
>
bool isSymmetric(TreeNode* root) {
if(!root||!root->left&&!root->right) return true;
if(!root->left||!root->right) return false;
stack<TreeNode*> st;
st.push(root->right);
st.push(root->left);
while(!st.emtpy()){
TreeNode *t1,*t2;
t1=st.top();
st.pop();
t2=st.top();
st.pop();
if(t1->val!=t2->val) return false;
if(t1->right&&t2->left){
st.push(t2->left);
st.push(t1->right);
}else if(!t1->right&&t2->left||t1->right&&!t2->left) return false;
if(t1->left&&t2->right){
st.push(t2->right);
st.push(t1->left);
}else if(!t1->left&&t2->right||t1->left&&!t2->right) return false;
}
return false;
}
BFS
>
bool isSymmetric(TreeNode* root) {
if(!root||!root->left&&!root->right) return true;
if(!root->left||!root->right) return false;
queue<TreeNode*> qt;
qt.push(root->left);
qt.push(root->right);
while(!qt.emtpy()){
TreeNode *t1,*t2;
t1=qt.front();
qt.pop();
t2=qt.front();
qt.pop();
if(t1->val!=t2->val) return false;
if(t1->right&&t2->left){
qt.push(t1->right);
qt.push(t2->left);
}else if(!t1->right&&t2->left||t1->right&&!t2->left) return false;
if(t1->left&&t2->right){
qt.push(t1->left);
qt.push(t2->right);
}else if(!t1->left&&t2->right||t1->left&&!t2->right) return false;
}
return false;
}
3 Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
>
int maxDepth(TreeNode* root) {
if(!root) return 0;
if(!root->left) return 1+maxDepth(root->right);
if(!root->right) return 1+maxDepth(root->left);
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
BFS
>
int maxDepth(TreeNode* root) {
int depth=0;
if(!root) return depth;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
depth++;
int n=q.size();
for(int i=0;i<n;i++){
TreeNode* temp=q.front();
q.pop();
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
}
return depth;
}
4 Binary Tree Paths
https://leetcode.com/problems/binary-tree-paths/
DFS
>
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
findPaths(root,"",paths);
return paths;
}
void findPaths(TreeNode* root, string path, vector<string> paths){
if(!root) return;
path+=to_string(root->val);
if(!root->left&&!root->right) paths.push_back(path);
if(root->left) findPaths(root->left,path+"->",paths);
if(root->right) findPaths(root->right,path+"->",paths);
}
5 Path Sum
https://leetcode.com/problems/path-sum/
>
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root->left&&!root->right&&root->val==sum) return true;
return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
}
6 Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/
>
int minDepth(TreeNode* root) {
if(!root) return 0;
if(!root->left) return 1+minDepth(root->right);
if(!root->right) return 1+minDepth(root->left);
return 1+min(minDepth(root->left),minDepth(root->right));
}
BFS
>
int minDepth(TreeNode* root) {
if(!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth=0;
while(!q.empty()){
depth++;
int n=q.size();
for(int i=0;i<n;i++){
TreeNode *temp=q.front();
q.pop();
if(!temp->left&&!temp->right) return depth;
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
}
return -1;
}
7 Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/
>
bool isBalanced(TreeNode* root) {
if(!root) return true;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return abs(left=right)<=1&&isBalanced(root->left)&&isBalanced(root->right);
}
int maxDepth(TreeNode* root){
if(!root) return 0;
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
8 Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/
>
bool isValidBST(TreeNode* root) {
return isBST(root,(long)INT_MIN-1,(long)INT_MAX+1);
}
bool isBST(TreeNode* root,long minV,long maxV){
if(!root) return true;
if(root->val<=minV||root->val>=maxV) return false;
return isBST(root->left,minV,root->val)&&isBST(root->right,root->val,maxV);
}
9 Convert Sorted List to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
>
TreeNode* sortedListToBST(ListNode* head) {
if(!head) return NULL;
if(!head->next){
TreeNode* root=new TreeNode(head->val);
return root;
}
ListNode *prev=NULL,*slow=head,*fast;
while(fast&&fast->next){
prev=slow;
slow=slow->next;
fast=fast->next->next;
}
prev->next=NULL;
fast=slow->next;
slow->next=NULL;
TreeNode *root=new TreeNode(slow->val);
root->left=sortedListToBST(head);
root->right=sortedListToBST(fast);
return root;
}
10 Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
>
TreeNode* sortedArrayToBST(vector<int>& nums) {
return arrayToBST(nums,0,nums.size()-1);
}
TreeNode* arrayToBST(vector<int>& nums,int left,int right){
if(left>right) return NULL;
int mid=left+(right-left)/2;
TreeNode *root=new TreeNode(nums[mid]);
root->left=arrayToBST(nums,left,mid-1);
root->right=arrayToBST(nums,mid+1,right);
return root;
}
11 Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
>
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildBT(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
}
TreeNode* buildBT(vector<int>& inorder,int is,int ie,vector<int>& postorder,int ps,int pe){
if(is>ie) return NULL;
int val=postorder[pe];
int i;
for(i=is;i<=ie;i++){
if(inorder[i]==val) break;
}
TreeNode *root=new TreeNode(val);
root->left=buildBT(inorder,is,i-1,postorder,ps,ps+i-is-1);
root->right=buildBT(inorder,i+1,ie,postorder,ps+i-is,pe-1);
return root;
}
12 Path Sum II
https://leetcode.com/problems/path-sum-ii/
>
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > paths;
vector<int> path;
findPath(root,sum,path,paths);
return paths;
}
void findPath(TreeNode* root,int sum,vector<int>& path, vector<vector<int> > paths){
if(!root) return;
path.push_back(root->val);
sum -= root->val;
if(!root->left&&!root->right){
if(sum==0) paths.push_back(path);
path.pop_back();
return;
}
findPath(root->left,sum,path,paths);
findPath(root->right,sum,path,paths);
path.pop_back();
return;
}
13 Flatten Binary Tree to Linked List
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
>
void flatten(TreeNode* root) {
TreeNode *cur=root;
while(cur){
TreeNode *prev=cur->left;
if(prev){
while(prev->right){
prev=prev->right;
}
prev->right=cur->right;
cur->right=cur->left;
cur->left=NULL;
}
cur=cur->right;
}
}
14 Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/
>
int sumNumbers(TreeNode* root) {
int sum=0;
sumNum(root,0,sum);
return sum;
}
void sumNum(TreeNode* root, int val,int& sum){
if(!root) return;
val=val*10+root->val;
if(!root->left&&!root->right){
sum+=val;
return;
}
sumNum(root->left,val,sum);
sumNum(root->right,val,sum);
return;
}
15 Clone Graph
https://leetcode.com/problems/clone-graph/
DFS
>
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
return clone(node);
}
UndirectedGraphNode* clone(UndirectedGraphNode* node){
if(!node) return NULL;
if(cloned.count(node->label)) return cloned[node->label];
UndirectedGraphNode *cNode=new UndirectedGraphNode(node->label);
cloned[node->label]=cNode;
for(auto neighbor:node->neighbors){
cNode->neighbors.push_back(clone(neighbor));
}
return cNode;
}
private:
unordered_map<int,UndirectedGraphNode*> cloned;
};
DFS
>
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
return clone(node);
}
UndirectedGraphNode *clone(UndirectedGraphNode* node){
if(!node) return NULL;
cloned[node]=new UndirectedGraphNode(node->label);
for(auto nd:node->neighbors){
if(cloned.count(nd)==0){
cloned[nd]=clone(nd);
}
cloned[node]->neighbors.push_back(cloned[nd]);
}
return cloned[node];
}
private:
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> cloned;
};
BFS
>
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
unordered_map<int,UndirectedGraphNode*> cloned;
UndirectedGraphNode *cNode=new UndirectedGraphNode(node->label);
cloned[node->label]=cNode;
queue<UndirectedGraphNode*> q;
q.push(node);
UndirectedGraphNode *temp=NULL;
while(!q.empty()){
temp=q.front();
q.pop();
for(auto nd:temp->neighbors){
if(cloned.count(nd->label)==0){
cloned[nd->label]=new UndirectedGraphNode(nd->label);
q.push(nd);
}
cloned[temp->label]->neighbors.push_back(cloned[nd->label]);
}
}
return cNode;
}
};
>
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> cloned;
cloned[node]=new UndirectedGraphNode(node->label);
queue<UndirectedGraphNode*> q;
q.push(node);
while(!q.empty()){
UndirectedGraphNode *temp=q.front();
q.pop();
for(auto nd:temp->neighbors){
if(cloned.count(nd)==0){
cloned[nd]=new UndirectedGraphNode(nd->label);
q.push(nd);
}
cloned[temp]->neighbors.push_back(cloned[nd]);
}
}
return cloned[node];
}
};
16 Binary Tree Right Side View
https://leetcode.com/problems/binary-tree-right-side-view/
DFS
>
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
sideView(root,0,res);
return res;
}
void sideView(TreeNode* root, int depth, vector<int>& res){
if(!root) return;
if(res.size()==depth) res.push_back(root->val);
sideView(root->right,depth+1,res);
sideView(root->left,depth+1,res);
return;
}
};
BFS
>
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
TreeNode *temp;
while(!q.empty()){
temp=q.front();
res.push_back(temp->val);
int n=q.size();
for(int i=0;i<n;i++){
temp=q.front();
q.pop();
if(temp->right) q.push(temp->right);
if(temp->left) q.push(temp->left);
}
}
return res;
}
};
BFS
>
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n=q.size();
for(int i=0;i<n;i++){
TreeNode *temp=q.front();
q.pop();
if(i==n-1) res.push_back(temp->val);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
}
return res;
}
};
17 Number of Islands
https://leetcode.com/problems/number-of-islands/
DFS
>
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int num=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1'){
num++;
dfs(i,j,grid);
}
}
}
return num;
}
void dfs(int i,int j,vector<vector<char> >& grid){
if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0') return;
grid[i][j]='0';
dfs(i+1,j,grid);
dfs(i-1,j,grid);
dfs(i,j+1,grid);
dfs(i,j-1,grid);
return;
}
};
Find Rectangle contains all the islands
>
class Solution {
public:
int left,right,top,bottom;
vector<int> numIslands(vector<vector<char>>& grid) {
left=grid.size(),right=-1,top=bottom[0].size(),bottom=-1;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1'){
dfs(i,j,grid);
}
}
}
return {left,right,bottom,top};
}
void dfs(int i,int j,vector<vector<char> >& grid){
if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0') return;
grid[i][j]='0';
left=min(left,i);
right=max(right,i);
top=min(top,j);
bottom=max(bottom,j);
dfs(i+1,j,grid);
dfs(i-1,j,grid);
dfs(i,j+1,grid);
dfs(i,j-1,grid);
return;
}
};
BFS
>
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1'){
count++;
bfs(i,j,grid);
}
}
}
return count;
}
void bfs(int i, int j, vector<vector<char> >& grid){
queue<pair<int,int> > q;
q.push({i,j});
grid[i][j]='0';
while(!q.empty()){
int x=q.front().first, y=q.front().second;
q.pop();
if(x>0&&grid[x-1][y]=='1'){
grid[x-1][y]='0';
q.push({x-1,y});
}
if(x<grid.size()-1&&grid[x+1][y]=='1'){
grid[x+1][y]='0';
q.push({x+1,y});
}
if(y>0&&grid[x][y-1]=='1'){
grid[x][y-1]='0';
q.push({x,y-1});
}
if(y<grid[0].size()-1&&grid[x][y+1]=='1'){
grid[x][y+1]='0';
q.push({x,y+1});
}
}
return;
}
};
18 Course Schedule
https://leetcode.com/problems/course-schedule/
DFS
>
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,vector<int> > graph=buildGraph(prerequisites);
vector<bool> visited(numCourses,false);
vector<bool> path(numCourses,false);
for(int i=0;i<numCourses;i++){
if(!visited[i]&&detectCycle(i,visited,path,graph)) return false;
}
return true;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& prerequisites){
unordered_map<int,vector<int> > graph;
for(auto p:prerequisites){
graph[p.second].push_back(p.first);
}
return graph;
}
bool detectCycle(int node,vector<bool>& visited,vector<bool>& path,unordered_map<int,vector<int> >& graph){
if(visited[node]) return false;
visited[node]=true;
path[node]=true;
for(auto nd:graph[node]){
if(path[nd]||detectCycle(nd,visited,path,graph)) return true;
}
path[node]=false;
return false;
}
};
BFS
>
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,vector<int> > graph=buildGraph(prerequisites);
vector<int> inDegree=incomeDegree(numCourses,prerequisites);
for(int i=0;i<numCourses;i++){
int j=0;
for(;j<numCourses;j++){
if(inDegree[j]==0) break;
}
if(j==numCourses) return false;
inDegree[j]--;
for(auto nd:graph[j]){
inDegree[nd]--;
}
}
return true;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& prerequisites){
unordered_map<int,vector<int> > graph;
for(auto p:prerequisites){
graph[p.second].push_back(p.first);
}
return graph;
}
vector<int> incomeDegree(int numCourses,vector<pair<int,int> >& prerequisites){
vector<int> inDegree(numCourses,0);
for(auto p:prerequisites){
inDegree[p.first]++;
}
return inDegree;
}
};
BFS
>
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,vector<int> > adj;
vector<int> inDegree(numCourses,0);
for(auto p:prerequisites){
adj[p.second].push_back(p.first);
inDegree[p.first]++;
}
queue<int> q;
for(int i=0;i<numCourses;i++){
if(inDegree[i]==0) q.push(i);
}
int count=0;
while(!q.empty()){
int node=q.front();
q.pop();
count++;
for(auto nd:adj[node]){
if(--inDegree[nd]==0) q.push(nd);
}
}
return count==numCourses;
}
};
19 Course Schedule II
https://leetcode.com/problems/course-schedule-ii/
BFS
>
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,vector<int> > adj;
vector<int> inDegree;
pair<vector<int>,unordered_map<int,vector<int> > > p=initialize(numCourses,prerequisites);
inDegree=p.first;
adj=p.second;
queue<int> q;
for(int i=0;i<numCourses;i++){
if(inDegree[i]==0) q.push(i);
}
vector<int> order;
while(!q.empty()){
int node=q.front();
q.pop();
order.push_back(node);
for(auto nd:adj[node]){
if(--inDegree[nd]==0) q.push(nd);
}
}
return order.size()==numCourses?order:(vector<int>){};
}
pair<vector<int>,unordered_map<int,vector<int> > > initialize(int numCourses,vector<pair<int,int> >& prerequisites){
vector<int> inDegree(numCourses,0);
unordered_map<int,vector<int> > adj;
for(auto p:prerequisites){
adj[p.second].push_back(p.first);
inDegree[p.first]++;
}
return {inDegree,adj};
}
};
DFS
>
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,vector<int> > adj=buildGraph(prerequisites);
vector<bool> visited(numCourses,false);
vector<bool> path(numCourses,false);
vector<int> order;
for(int i=0;i<numCourses;i++){
if(!visited[i]&&detectCycle(i,visited,path,order,adj)) return {};
}
reverse(order.begin(),order.end());
return order;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& prerequisites){
unordered_map<int,vector<int> > adj;
for(auto p:prerequisites){
adj[p.second].push_back(p.first);
}
return adj;
}
bool detectCycle(int node,vector<bool>& visited,vector<bool>& path,vector<int>& order,unordered_map<int,vector<int> >& adj){
if(visited[node]) return false;
visited[node]=true;
path[node]=true;
for(auto nd:adj[node]){
if(path[nd]||detectCycle(nd,visited,path,order,adj)) return true;
}
order.push_back(node);
path[node]=false;
return false;
}
};
20 House Robber III
https://leetcode.com/problems/house-robber-iii/
DFS
>
class Solution {
public:
int rob(TreeNode* root){
}
pair<int,int> robbedPath(TreeNode* root){
pair<int,int> p={0,0};
if(!root) return p;
pair<int,int> left=robbedPath(root->left);
pair<int,int> right=robbedPath(root->right);
p.second=max(0,left.first)+max(0,right.first);
p.first=max(p.second,max(0,left.second)+max(0,right.second)+root->val);
return p;
}
};
21 Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
DFS
>
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildBT(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
TreeNode* buildBT(vector<int>& preorder, int ps,int pe, vector<int>& inorder, int is,int ie){
if(ps>pe) return NULL;
int val=preorder[ps];
TreeNode* root=new TreeNode(val);
int i=is;
for(;i<=ie;i++) if(inorder[i]==val) break;
root->left=buildBT(preorder,ps+1,ps+i-is,inorder,is,i-1);
root->right=buildBT(preorder,ps+i-is+1,pe,inorder,i+1,ie);
return root;
}
};
22 Graph Valid Tree
DFS
>
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
unordered_map<int,vector<int> > adj=buildGraph(edges);
vector<bool> visited(n,false);
vector<bool> path(n,false);
if(detectCycle(0,path,visited,adj)) return false;
for(int i=0;i<n;i++) if(!visited[i]) return false;
return true;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& edges){
unordered_map<int,vector<int> > adj;
for(auto p:edges){
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
}
return true;
}
bool detectCycle(int node, vector<bool>& path,vector<bool>& visited,unordered_map
<int,vector<int> >& adj){
if(visited[node]) return false;
visited[node]=true;
path[node]=true;
for(auto nd:adj[node]){
if(path[nd]||detectCycle(nd,path,visited,adj)) return true;
}
path=false;
return false;
}
};
BFS
>
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
unordered_map<int,vector<int> > adj;
vector<int> inDegree(n,0);
initializeGraph(edges,adj,inDegree);
quque<int> q;
for(int i=0;i<n;i++){
if(inDegree[i]==0) q.push(i);
}
if(q.size()>1) return false;
int count=0;
while(!q.empty()){
int temp=q.front();
q.pop();
count++;
for(auto nd:adj[temp]){
if(--inDegree[nd]==0) q.push(nd);
}
}
return count==n;
}
void initializeGraph(vector<pair<int,int> >& edges, unordered_map<int,vector<int> >& adj,
vector<int>& inDegree){
for(auto p:edges){
adj[p.first].push_back(p.second);
inDegree[p.second]++;
}
return;
}
};
23 Number of Connected Components in an Undirected Graph
DFS
>
class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges){
unordered_map<int,vector<int> > adj=buildGraph(edges);
vector<bool> visited(n,false);
int count=0;
for(int i=0;i<n;i++){
if(!visited[i]){
dfs(i,visited,adj);
count++;
}
}
return count;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& edges){
unordered_map<int,vector<int> > adj;
for(auto p:edges){
adj[p.first].push_back(p.second);
//adj[p.second].push_back(p.first);
}
return adj;
}
void dfs(int node, vector<bool>& visited,unordered_map<int,vector<int> >& adj){
if(visited[node]) return;
visited[node]=true;
for(auto nd:adj[node]){
dfs(nd,visited,adj);
}
}
};
BFS
>
class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges){
int count=0;
unordered_map<int,vector<int> > adj=buildGraph(edges);
vector<bool> visited(n,false);
queue<int> q;
for(int i=0;i<n;i++){
if(!visited[i]){
q.push(i);
while(!q.empty()){
int temp=q.front();
visited[temp]=true;
q.pop();
for(auto nd:adj[temp]){
if(!visited[nd]) q.push(temp);
}
}
count++;
}
}
return count;
}
unordered_map<int,vector<int> > buildGraph(vector<pair<int,int> >& edges){
unordered_map<int,vector<int> > adj;
for(auto p:edges){
adj[p.first].push_back(p.second);
//adj[p.second].push_back(p.first);
}
return adj;
}
};
24 Recover Binary Search Tree
https://leetcode.com/problems/recover-binary-search-tree/
>
class Solution {
public:
void recoverTree(TreeNode* root) {
traversal(root);
int temp=first->val;
first->val=second->val;
second->val=temp;
return;
}
void traversal(TreeNode* root){
if(!root) return;
traversal(root->left);
if(!first&&prev->val>root->val) first=prev;
if(first&&prev->val>root->val) second=root;
prev=root;
traversal(root->right);
return;
}
private:
TreeNode *first=NULL,*second=NULL,*prev=new TreeNode(INT_MIN);
};
25 Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum
>
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxSum=INT_MIN;
findPath(root,maxSum);
return maxSum;
}
int findPath(TreeNode* root, int& maxSum){
if(!root) return 0;
int left=max(0,findPath(root->left,maxSum));
int right=max(0,findPath(root->right,maxSum));
maxSum=max(maxSum,left+right+root->val);
return max(left,right)+root->val;
}
};
26 Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/
DFS
>
class Solution {
public:
vector<char> par{'(',')'};
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
removeParentheses(s,0,0,0,res);
return res;
}
void removeParentheses(string s, int lastI,int lastJ,int start,vector<string>& res){
int count=0;
for(int i=lastI;i<s.size();i++){
if(s[i]==par[start]) count++;
if(s[i]==par[1-start]) count--;
if(count>=0) continue;
for(int j=lastJ;j<=i;j++){
if(s[j]==par[1-start]&&(j==lastJ||s[j]!=par[1-start]))
removeParentheses(s,i,j,start,res);
}
return;
}
reverse(s.begin(),s.end());
if(p[start]=='(') removeParentheses(s,0,0,1,res);
else res.push_back(s);
return;
}
};
BFS
>
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> visited;
queue<string> q;
q.push(s);
bool found=false;
while(!q.empty()){
string t=q.front();
q.pop();
if(isValid(t)){
res.push_back(t);
found=true;
}
if(found) continue;
for(int i=0;i<t.size();i++){
if(t[i]!='('&&t[i]!=')') continue;
string temp=t.substr(0,i)+t.substr(i+1);
if(visited.count(temp)==0){
visited.insert(temp);
q.push(temp);
}
}
}
return res;
}
bool isValid(string s){
int count=0;
for(auto c:s){
if(c=='(') count++;
else if(c==')') count--;
if(count<0) return false;
}
return count==0;
}
};
27 Longest Increasing Path in a Matrix
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
DFS
>
class Solution {
public:
vector<pair<int,int> > dirs{{-1,0},{1,0},{0,-1},{0,1}};
int longestIncreasingPath(vector<vector<int>>& matrix) {
int maxLen=0;
if(matrix.size()==0||matrix[0].size()==0) return maxLen;
int m=matrix.size(),n=matrix[0].size();
vector<vector<int> > visited(m,vector<int>(n,0));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int len=dfs(i,j,m,n,matrix,visited);
maxLen=max(maxLen,len);
}
}
return maxLen;
}
int dfs(int i,int j,int m, int n, vector<vector<int> >& matrix, vector<vector<int> >& visited){
if(visited[i][j]!=0) return visited[i][j];
int maxL=1;
for(auto dir:dirs){
int x=i+dir.first,y=j+dir.second;
if(x<0||x>=m||y<0||y>=n||matrix[x][y]<=matrix[i][j]) continue;
int len=1+dfs(x,y,m,n,matrix,visited);
maxL=max(maxL,len);
}
visited[i][j]=maxL;
return maxL;
}
};
28 Surrounded Regions
https://leetcode.com/problems/surrounded-regions/
BFS
>
class Solution {
public:
vector<pair<int,int> > dirs{{-1,0},{1,0},{0,-1},{0,1}};
void solve(vector<vector<char>>& board) {
if(board.size()==0) return;
queue<pair<int,int> > q;
for(int i=0;i<board.size();i++){
if(board[i][0]=='O'){
board[i][0]='#';
q.push({i,0});
}
if(board[i][board[0].size()-1]=='O'){
board[i][board[0].size()-1]='#';
q.push({i,board[0].size()-1});
}
}
for(int j=0;j<board[0].size();j++){
if(board[0][j]=='O'){
board[0][j]='#';
q.push({0,j});
}
if(board[board.size()-1][j]=='O'){
board[board.size()-1][j]='#';
q.push({board.size()-1,j});
}
}
while(!q.empty()){
pair<int,int> temp=q.front();
q.pop();
for(auto dir:dirs){
int x=temp.first+dir.first;
int y=temp.second+dir.second;
if(x<0||x>=board.size()||y<0||y>=board[0].size()||board[x][y]!='O') continue;
board[x][y]='#';
q.push({x,y});
}
}
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j]=='O') board[i][j]='X';
else if(board[i][j]=='#') board[i][j]='O';
}
}
return;
}
};
DFS
>
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size()==0) return;
for(int i=0;i<board.size();i++){
dfs(i,0,board);
dfs(i,board[0].size()-1,board);
}
for(int j=1;j<board[0].size()-1;j++){
dfs(0,j,board);
dfs(board.size()-1,j,board);
}
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j]=='O') board[i][j]='X';
else if(board[i][j]=='#') board[i][j]='O';
}
}
return;
}
void dfs(int i,int j, vector<vector<char> >& board){
if(board[i][j]!='O') return;
board[i][j]='#';
if(i>0) dfs(i-1,j,board);
if(i<board.size()-1) dfs(i+1,j,board);
if(j>0) dfs(i,j-1,board);
if(j<board[0].size()-1) dfs(i,j+1,board);
}
};
29 Minimum Height Trees
https://leetcode.com/problems/minimum-height-trees/
BFS
>
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> current;
unordered_map<int,unordered_set<int> > adj;
for(auto edge:edges){
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
if(n==1){
current.push_back(0);
return current;
}
for(int i=0;i<n;i++){
if(adj[i].size()==1) current.push_back(i);
}
while(true){
vector<int> next;
for(auto node:current){
for(auto nd:adj[node]){
adj[nd].erase(node);
if(adj[nd].size()==1) next.push_back(nd);
}
}
if(next.size()==0) return current;
current=next;
}
}
};
30 Word Ladder II
https://leetcode.com/problems/word-ladder-ii/
>
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string> > sols;
if(wordList.size()==0) return sols;
wordList.insert(beginWord);
wordList.insert(endWord);
queue<string> q;
q.push(beginWord);
unordered_map<string,int> ladder;
for(auto s:wordList){
ladder[s]=INT_MAX;
}
ladder[beginWord]=0;
unordered_map<string,vector<string> > adj;
int minStep=INT_MAX;
while(!q.empty()){
string word=q.front();
q.pop();
int step=ladder[word]+1;
if(step>minStep) break;
if(word==endWord) minStep=step;
for(int i=0;i<word.size();i++){
string newWord=word;
for(int j=0;j<26;j++){
char c='a'+j;
if(c==word[i]) continue;
newWord[i]=c;
if(ladder.count(newWord)==0) continue;
if(ladder[newWord]<step) continue;
if(ladder[newWord]>step){
ladder[newWord]=step;
q.push(newWord);
}
if(adj.count(newWord)==0) adj[newWord]={word};
else adj[newWord].push_back(word);
}
}
}
vector<string> sol;
backTracking(beginWord,endWord,adj,sol,sols);
return sols;
}
void backTracking(string beginWord,string word,unordered_map<string,vector<string> >& adj,
vector<string>& sol, vector<vector<string> >& sols){
sol.insert(sol.begin(),word);
if(word==beginWord){
sols.push_back(sol);
sol.erase(sol.begin());
return;
}
if(adj.count(word)>0){
for(auto s:adj[word])
backTracking(beginWord,s,adj,sol,sols);
}
sol.erase(sol.begin());
return;
}
};
DFS+BFS
>
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string> > sols;
wordList.insert(beginWord);
wordList.insert(endWord);
unordered_map<string, int> dist;
unordered_map<string,vector<string> > adj;
for(auto word:wordList){
dist[word]=INT_MAX;
}
dist[beginWord]=0;
queue<string> q;
q.push(beginWord);
int minStep=INT_MAX;
while(!q.empty()){
string word=q.front();
q.pop();
int step=dist[word]+1;
if(word==endWord) break;
for(int i=0;i<word.size();i++){
string newWord=word;
for(int j=0;j<26;j++){
newWord[i]='a'+j;
if(newWord==word) continue;
if(wordList.count(newWord)==0) continue;
if(dist[newWord]<step) continue;
if(dist[newWord]>step){
dist[newWord]=step;
q.push(newWord);
}
adj[word].push_back(newWord);
}
}
}
vector<string> sol;
dfs(beginWord,endWord,sol,sols,adj);
return sols;
}
dfs(string word, string endWord, vector<string>& sol, vector<vector<string> >& sols, unordered_map<string,vector<string> >& adj){
void dfs(string word, string endWord, vector<string>& sol, vector<vector<string> >& sols, unordered_map<string,vector<string> >& adj){
sol.push_back(word);
if(word==endWord){
sols.push_back(sol);
sol.pop_back();
return;
}
for(auto s:adj[word]){
dfs(s,endWord,sol,sols,adj);
}
sol.pop_back();
return;
}
};
31 Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/
>
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> visited;
queue<string> q;
vector<string> res;
q.push(s);
visited.insert(s);
bool found=false;
while(!q.empty()){
string t=q.front();
q.pop();
if(isValid(t)){
res.push_back(t);
found=true;
}
if(found) continue;
for(int i=0;i<t.size();i++){
if(t[i]!='('&&t[i]!=')') continue;
string temp=t.substr(0,i)+t.substr(i+1);
if(visited.count(temp)==0){
visited.insert(temp);
q.push(temp);
}
}
}
return res;
}
bool isValid(string s){
int count=0;
for(auto c:s){
if(c=='(') count++;
else if(c==')') count--;
if(count<0) return false;
}
return count==0;
}
};
32 Lexicographical Numbers
https://leetcode.com/problems/lexicographical-numbers/
>
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> res;
for(int i=1;i<10;i++){
dfs(i,n,res);
}
return res;
}
void dfs(int cur,int n,vector<int>& res){
if(cur>n) return;
res.push_back(cur);
for(int i=0;i<10;i++){
if(cur*10+i>n) return;
dfs(cur*10+i,n,res);
}
return;
}
};
33 Longest Increasing Path in a Matrix
>
class Solution {
public:
vector<pair<int,int> > dirs{{-1,0},{1,0},{0,-1},{0,1}};
int longestIncreasingPath(vector<vector<int>>& matrix) {
int maxLen=0;
if(matrix.size()==0||matrix[0].size()==0) return maxLen;
int m=matrix.size(),n=matrix[0].size();
vector<vector<int> > lens(m,vector<int>(n,0));
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
int len=dfs(i,j,INT_MIN,matrix,lens);
maxLen=max(maxLen,len);
}
}
return maxLen;
}
int dfs(int i, int j, int prev,vector<vector<int> >& matrix,vector<vector<int> >& lens){
if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()||matrix[i][j]<=prev) return 0;
if(lens[i][j]!=0) return lens[i][j];
int len=0;
int maxL=0;
for(auto p:dirs){
int x=i+p.first;
int y=j+p.second;
len=1+dfs(x,y,matrix[i][j],matrix,lens);
maxL=max(maxL,len);
}
lens[i][j]=maxL;
return maxL;
}
};
34 N-Queens
>
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string> > sols;
vector<string> sol(n,string(n,'.'));
solveNQueens(sols,sol,0,n);
return sols;
}
void solveNQueens(vector<vector<string> >& sols, vector<string>& sol, int row, int n){
if(row==n){
sols.push_back(sol);
return;
}
for(int col=0;col<n;col++){
if(isValid(sol,row,col,n)){
sol[row][col]='Q';
solveNQueens(sols,sol,row+1,n);
sol[row][col]='.';
}
}
}
bool isValid(vector<string> sol, int row, int col,int n){
for (int j=0;j!=row;j++){
if (sol[j][col]=='Q') return false;
}
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(sol[i][j]=='Q') return false;
}
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
if(sol[i][j]=='Q') return false;
}
return true;
}
};
35 N-QueensII
>
class Solution {
public:
int totalNQueens(int n) {
int cnt=0;
vector<string> sol(n,string(n,'.'));
solveNQueens(cnt,sol,0,n);
return cnt;
}
void solveNQueens(int &cnt, vector<string>& sol, int row, int n){
if(row==n){
cnt++;
return;
}
for(int col=0;col<n;col++){
if(isValid(sol,row,col,n)){
sol[row][col]='Q';
solveNQueens(cnt,sol,row+1,n);
sol[row][col]='.';
}
}
}
bool isValid(vector<string> sol, int row, int col,int n){
for (int i=0;i!=row;i++){
if (sol[i][col]=='Q') return false;
}
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(sol[i][j]=='Q') return false;
}
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
if(sol[i][j]=='Q') return false;
}
return true;
}
};
36 Permutation Sequence
>
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> factorial(n+1);
vector<int> nums(n);
int sum=1;
string res="";
factorial[0]=1;
for(int i=1;i<=n;i++){
sum*=i;
factorial[i]=sum;
}
for(int i=1;i<=n;i++){
nums[i-1]=i;
}
k--;
for(int i=1;i<=n;i++){
int id=k/factorial[n-i];
k%=factorial[n-i];
res += to_string(nums[id]);
nums.erase(nums.begin()+id);
}
return res;
}
};
37 Pacific Atlantic Water Flow
>
class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int> > res;
if(matrix.size()==0||matrix[0].size()==0) return res;
int m=matrix.size(),n=matrix[0].size();
vector<vector<bool> > pacific(m,vector<bool>(n,false));
vector<vector<bool> > atlantic(m,vector<bool>(n,false));
for(int i=0;i<m;i++){
dfs(i,0,pacific,INT_MIN,matrix);
dfs(i,n-1,atlantic,INT_MIN,matrix);
}
for(int j=0;j<n;j++){
dfs(0,j,pacific,INT_MIN,matrix);
dfs(m-1,j,atlantic,INT_MIN,matrix);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(pacific[i][j]&&atlantic[i][j]) res.push_back({i,j});
}
}
return res;
}
void dfs(int i, int j,vector<vector<bool> >& visited, int height,vector<vector<int> >& matrix){
if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()||visited[i][j]||matrix[i][j]<height) return;
visited[i][j]=true;
dfs(i+1,j,visited,matrix[i][j],matrix);
dfs(i-1,j,visited,matrix[i][j],matrix);
dfs(i,j+1,visited,matrix[i][j],matrix);
dfs(i,j-1,visited,matrix[i][j],matrix);
}
};
>
class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int> > res;
if(matrix.size()==0||matrix[0].size()==0) return res;
int m=matrix.size(),n=matrix[0].size();
vector<vector<bool> > pacific(m,vector<bool>(n,false));
vector<vector<bool> > atlantic(m,vector<bool>(n,false));
for(int i=0;i<m;i++){
bfs(i,0,pacific,matrix);
bfs(i,n-1,atlantic,matrix);
}
for(int j=0;j<n;j++){
bfs(0,j,pacific,matrix);
bfs(m-1,j,atlantic,matrix);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(pacific[i][j]&&atlantic[i][j]) res.push_back({i,j});
}
}
return res;
}
void bfs(int i, int j,vector<vector<bool> >& visited,vector<vector<int> >& matrix){
queue<pair<int,int> > q;
q.push({i,j});
visited[i][j]=true;
while(!q.empty()){
pair<int,int> p=q.front();
int x=p.first,y=p.second;
q.pop();
if(x<matrix.size()-1&&matrix[x][y]<=matrix[x+1][y]&&!visited[x+1][y]){
visited[x+1][y]=true;
q.push({x+1,y});
}
if(x>0&&matrix[x][y]<=matrix[x-1][y]&&!visited[x-1][y]){
visited[x-1][y]=true;
q.push({x-1,y});
}
if(y<matrix[0].size()-1&&matrix[x][y]<=matrix[x][y+1]&&!visited[x][y+1]){
visited[x][y+1]=true;
q.push({x,y+1});
}
if(y>0&&matrix[x][y]<=matrix[x][y-1]&&!visited[x][y-1]){
visited[x][y-1]=true;
q.push({x,y-1});
}
}
}
};
38 Number of Connected Components in a list of doubly linked node
DFS
>
class ListNode{
public:
int val;
ListNode *prev,*next;
ListNode(int value){
val=value;
prev=NULL;
next=NULL;
}
};
int countConnectedComponent(vector<ListNode*> list){
int cnt=0;
unordered_map<ListNode*,int> visited;
for(int i=0;i<list.size();i++){
if(visited.count(list[i])==0){
dfs(list[i],visited);
cnt++;
}
}
return cnt;
}
void dfs(ListNode* node, unordered_map<ListNode*,int>& visited){
if(visited.count(node)>0) return;
visited[node]=1;
dfs(node->prev,visited);
dfs(node->next,visited);
}
39 Maximum Induced Subgraph with at least degree k
>
unordered_map<int,unordered_set<int> > inducedSubgraph(int n, vector<pair<int,int> >& edges, int k){
vector<int> degree(n,0);
unordered_map<int,unordered_set<int> > adj;
for(auto edge:edges){
degree[edge.first]++;
degree[edge.second]++;
adj[edge.first].insert(edge.second);
adj[edge.second].insert(edge.first);
}
queue<int> q;
for(int i=0;i<n;i++) if(degree[i]<k) q.push(i);
while(!q.empty()){
int node=q.front();
q.pop();
for(auto nd:adj[node]){
adj[nd].erase(node);
if(--degree[nd]<k) q.push(nd);
}
adj.erase(node);
}
return adj;
}