int height(Node* node, int &dia) {
// code here
if(node == NULL) return 0;
int lh = height(node->left,dia);
int rh = height(node->right,dia);
dia = max(dia, lh+rh);
return max(lh, rh) +1;
}
int diameter(Node* root) {
// Your code here
int diameter = 0;
height(root, diameter);
return diameter;
}GFG PTOD | 03 Feb | Height of Binary Tree | Medium level | Tree
Using Iteration Using Recursion
GFG PTOD | 02 Feb | Level order traversal | Medium level | Backtracking
vector<vector<int>> levelOrder(Node *root) {
// Your code here
vector<vector<int>> ans;
if(root == NULL) return ans;
queue<Node*> q;
q.push(root);
while(!q.empty()) {
vector<int> res;
int len = q.size();
for(int i=0; i<len; i++) {
Node *cur = q.front();
q.pop();
res.push_back(cur->data);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
ans.push_back(res);
}
return ans;
}GFG PTOD | 01 Feb | Word Search | Medium level | Backtracking
bool solve(vector<vector<char>>& mat, string& word, int i, int j, int widx) {
int wlen = word.length();
int n = mat.size();
int m = mat[0].size();
//base case
if(widx == wlen) return true;
if(i<0 || j<0 || i>=n || j>=m) return false;
//recursive case
if(mat[i][j] == word[widx]) {
bool res = false;
char tmp = mat[i][j];
mat[i][j] = '_';
if(solve(mat, word, i-1, j, widx+1) || solve(mat, word, i+1, j, widx+1) ||
solve(mat, word, i, j+1, widx+1) || solve(mat, word, i, j-1, widx+1))
res = true;
mat[i][j] = tmp;
return res;
}
return false;
}
bool isWordExist(vector<vector<char>>& mat, string& word) {
// Code here
int n = mat.size();
int m = mat[0].size();
int wlen = word.length();
for(int i=0;i<n; i++) {
for(int j=0; j<m; j++) {
if(solve(mat, word, i, j, 0)) return true;
}
}
return false;
}GFG PTOD | 31 Jan | Solve the Sudoku | Hard level | Backtracking
bool setisfy(vector<vector<int>> &mat, int i, int j, int num) {
for(int x= 0; x<9; x++) {
if(mat[i][x] == num || mat[x][j] == num)
return false;
}
int str = i-i%3, stc = j-j%3;
for(int a=0; a<3; a++){
for(int b=0;b<3; b++) {
if(mat[str+a][stc+b] == num)
return false;
}
}
return true;
}
bool solve(vector<vector<int>> &mat) {
for(int i=0; i<9; i++) {
for(int j=0; j<9; j++) {
if(mat[i][j] == 0) {
for(int num = 1; num<=9; num++) {
if(setisfy(mat, i, j, num)) {
mat[i][j] = num;
if(solve(mat)) return true;
mat[i][j] = 0;
}
}
return false;
}
}
}
return true;
}
// Function to find a solved Sudoku.
void solveSudoku(vector<vector<int>> &mat) {
// code here
solve(mat);
}GFG PTOD | 30 Jan | N-Queen Problem | Hard | Backtracking
void solve(int colm, int n, vector<bool> &col, vector<bool> &ldiag, vector<bool> &rdiag, vector<vector<int>> &ans, vector<int> &res) {
for(int i=0; i<n; i++) {
if(colm == n) {
ans.push_back(res);
return;
}
if(!col[i] && !ldiag[colm-i + n-1] && !rdiag[i+colm]) {
res.push_back(i+1);
col[i] = true;
ldiag[colm-i+n-1] = true;
rdiag[i+colm] = true;
solve(colm+1, n, col, ldiag, rdiag, ans, res);
res.pop_back();
col[i] = false;
ldiag[colm-i+n-1] = false;
rdiag[i+colm] = false;
}
}
}
vector<vector<int>> nQueen(int n) {
// code here
vector<bool>col(n, false);
vector<bool>ldiag(2*n-1, false);
vector<bool>rdiag(2*n-1, false);
vector<vector<int>> ans;
vector<int> res;
solve(0, n, col, ldiag, rdiag, ans, res);
return ans;
}GFG PTOD | 29 Jan | Implement Pow
double power(double b, int e) {
// code here
int n = abs(e);
double res = 1.0;
while(n>0) {
if(n%2 == 0) {
b *=b;
n=n/2;
} else {
res *= b;
n--;
}
}
if(e<0) res = double(1.0)/res;
return res;
}GFG PTOD | 28 Jan | Permutations of a String
void helper(int i, int n, string &s, unordered_set<string> &st, string &cur) {
if(cur.size() == n) {
st.insert(cur);
return;
}
for(int j=i; j<n; j++) {
swap(s[i], s[j]);
cur.push_back(s[i]);
helper(i+1, n, s, st, cur);
cur.pop_back();
swap(s[i], s[j]);
}
}
vector<string> findPermutation(string &s) {
// Code here there
unordered_set<string> st;
string cur;
helper(0, s.size(), s, st, cur);
vector<string> res(st.begin(), st.end());
return res;
}GFG PTOD | 26 Jan | Remove loop in Linked List
void removeLoop(Node* head) {
// code here
Node* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
// check if fast and slow pointer at head node
if(fast == slow) {
while(fast->next != slow)
fast = fast->next;
}
else {
while(slow->next !=fast->next) {
slow = slow->next;
fast = fast->next;
}
}
fast->next = NULL;
}
}
}GFG PTOD | 25 Jan | Find the first node of loop in linked list
Node* findFirstNode(Node* head) {
// your code here
Node* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
while(slow!=fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}