To generate permutation you can use these codes-

void f(int i,vector<int>&nums,vector<vector<int>>&ans){

if(i==nums.size()-1){
ans.push_back(nums);
return;
}
for(int ind=i;ind<nums.size();ind++){
swap(nums[i],nums[ind]);
f(i+1,nums,ans);
swap(nums[i],nums[ind]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>>ans;
f(0,nums,ans);
return ans;
}

To find Time Complexity

Sorting:-
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Recursive Bubble Sort
6. Recursive Insertion Sort
7. Quick Sort

Arrays:-
1. Largest Element in an Array
2. Second Largest Element in an Array without sorting
3. Check if the array is sorted
4. Remove duplicates from Sorted array
5. Left Rotate an array by one place
6. Left rotate an array by D places
7. Move Zeros to end
8. Linear search
9. Find the Union
10. Find missing number in an array
 11. Max consecutive one’s
12. Find the number that appears once, and the other numbers twice
13. Longest Subarray with given Sum K(Positives)
14. Longest Subarray with sum K | [Postives and Negatives]
15. Two sum
16. Sort an array of 0's 1's and 2's
17. Majority Element (>n/2 times)
18. Kadane’s Algorithm : Maximum Subarray Sum in an Array
19. print subarray with max subarray
20. Stock Buy And Sell
21. Rearrange Array Elements by Sign
22. next_permutation-find next lexicographically greater permutation
//Steps to find next permutation-
//1-Find the first pair index from behind which are in ascending order.
//2-if(index=-1)return the reversed array.
//3-Otherwise find the first element from behind which is greater than the
index and swap both the values and break the loop
//Finally reverse of this updated array from index+1 to end

23. Leaders in an Array

24. Longest Consecutive Sequence in an Array
25. Set Matrix Zero
26. Rotate Image by 90 degree
27. Spiral Traversal of Matrix
28. Count Subarray sum Equals K
29. Program to generate Pascal’s Triangle
30. Majority Elements(>N/3 times)
31. 3-Sum Problem
32. 4-Sum Problem
33. Largest Subarray with 0 Sum
34. Count the number of subarrays with given xor K
35. Merge Overlapping Sub-intervals
36. Merge two Sorted Arrays Without Extra Space
Without extra space-
Approach 1->
Time complexity-> if p=max(n,m)=> O(plogp)
void mergeTwoSortedArraysWithoutExtraSpace(vector<long long> &a, vector<long long>
&b){
int i=a.size()-1;
int j=0;
while(i>=0&&j<b.size()){
if(a[i]>b[j]){
swap(a[i],b[j]);
i--;
j++;
 }
else break;
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
}

Second approach->
Gap filling approach->
Time complexity-> if O((n+m)log(n+m))

int nextGap(int gap){

if(gap<=1)return 0;
return (gap / 2) + (gap % 2);
}
void mergeTwoSortedArraysWithoutExtraSpace(vector<long long> &a, vector<long long>
&b){
int m=a.size(),n=b.size();
int total_len=m+n;
int gap= ((total_len) / 2) + ((total_len) % 2);
while(gap>0){
int left=0;
int right=gap;
while(right<total_len){
if(right<m&&a[left]>a[right])swap(a[left],a[right]);
else if(left<m&&right>=m&&a[left]>b[right-m])swap(a[left],b[right-m]);
else if(left>=m&&right>=m&&b[left-m]>b[right-m])swap(b[left-m],b[right-m]);
left++;
right++;
}
gap=nextGap(gap);
}
}

37. Find the repeating and missing numbers

vector<int> findMissingRepeatingNumbers(vector < int > a) {
// Write your code here
 int n=a.size();
int res=0;
for(int i=1;i<=n;i++)res^=i;
for(int i=0;i<n;i++)res^=a[i];
int ind=0;
while(true){
if((res&(1<<ind))!=0)break;
else ind++;
}
int zero=0;
int one=0;
for(int i=1;i<=n;i++){
if((i&(1<<ind))!=0)one^=i;
else zero^=i;
}
for(int i=0;i<n;i++){
if((a[i]&(1<<ind))!=0)one^=a[i];
else zero^=a[i];
}
int counti=0;
for(auto i:a){
if(i==zero)counti++;
}
if(counti==2)return {zero,one};
return {one,zero};
}

38. Count Inversions->Similar to Reverse Pairs Just change 2 to 1 in county function

code-
int counti(int l,int mid,int h,vector<int>&nums){
int i=l;
int j=mid+1;
int tempans=0;
while(i<=mid&&j<=h){
if(nums[i]>1*(long long)nums[j]){
tempans+=(mid-i+1);
 j++;
}
else i++;
}
return tempans;
}

39. Reverse Pairs

If arr is and array-
vector<int> v1={arr+l, arr+m+1};
If arr is an vector-
vector<int> v1={arr.begin()+l, arr.begin()+m+1};
Left is inclusive but right is not and hence we add 1 to make it inclusive.

Before merging the two sorted arrays- Just count the pairs and update the
answer.
To update the answer, you can use the below count code-
int counti(int l,int mid,int h,vector<int>&nums){
int i=l;
int j=mid+1;
int tempans=0;
while(i<=mid&&j<=h){
if(nums[i]>2*(long long)nums[j]){
tempans+=(mid-i+1);
j++;
}
else i++;
}
return tempans;
}
40. Maximum Product Subarray
Initilize the answer by maximum element
Go from left and right by maintaining the maximum product and
simultaneously update the answer.
If at any point, you encounters with 0 then just update product with 1 and
do continue;

Binary Search:-
 1. Binary Search to find X in sorted array
2. Implement Lower Bound
3. Implement Upper Bound
4. Search insert position
5. Floor/Ceil in Sorted Array
6. First and Last Occurrences in Array
7. Count Occurrences in Sorted Array
8. Search in Rotated Sorted Array I
9. Search in Rotated Sorted Array II
10. Find minimum in Rotated Sorted Arra…
11. Minimum in rotated sorted array
12. Single element in a Sorted Array
13. Find peak element
14. Finding square root of a number in binary search
15. Nth root of a number in binary search
16. Koko Eating Bananas
17. Minimum days to make M bouquets
18. Find the smallest Divisor
19. Capacity to Ship Packages within D Days
20. Kth Missing Positive Number
21. Aggressive Cows
22. Book Allocation Problem
23. Split array - Largest Sum
24. Painter's partition
25. Minimise Maximum Distance between Gas Stations
26. Median of 2 sorted arrays
27. Kth element of 2 sorted arrays
28. Find the row with maximum number of 1’s
29. Search in a 2 D matrix
30. Find Peak Element (2D Matrix)
31. Matrix Median
32. Search in a row and column wise sorted matrix

Strings:-
1. Remove outermost parenthesis
2. Reverse Words in a String
3. Largest odd number in a string
4. Longest Common Prefix
5. Isomorphic String
6. check whether one string is a rotat…
7. Check if two Strings are anagrams of each other
8. Sort Characters by frequency
9. Maximum Nesting Depth of the Parentheses
10. Roman to Integer
11. Implement Atoi
12. Count Number of Substrings
 13. Longest Palindromic Substring
14. Sum of Beauty of all substring
15. Reverse Every Word in A String

Linkedlist:-
1. Inserting a node in LinkedList
2. Deleting a node in LinkedList
3. Find the Length of a Linked List
4. Search an element in a Linked List
5. Insert a node in DLL
6. Delete a node in DLL
7. Reverse a DLL
8. Find middle element in a Linked List
9. Reverse a LinkedList [Iterative]
10. Reverse a LL [Recursive]
11. Detect a loop in LL
12. Starting point of loop in a Linked List
13. Length of Loop in LL
14. Check if LL is palindrome or not
15. Segregate odd and even nodes in LL
16. Remove N-th node from the end of a Linked List
17. Delete the middle node of LL
18. Sort LL
19. Sort linked list of 0s 1s 2s
20. Find intersection of Two Linked Lists
21. Add one to a number represented as Linked List
22. Add 2 numbers in LL
23. Delete all occurrences of a given key in a doubly linked list
24. Find pairs with given sum in doubly linked list
25. Remove duplicates from a sorted Doubly Linked List
26. Reverse List In K Groups
27. Rotate a Linked List
28. Flattening a Linked List
29. Clone a Linked List with random pointers
Recursion:-
1. String to Integer (atoi)
2. Implement Pow(x,n) | X raised to the power N
This is also known as Binary Exponentation
Observation:

double myP(double x,long long n){

if(n==0)return 1.0;
if(n==1)return x;
if(n%2==0)return myP(x*x,n/2);
return x*myP(x,n-1);
}
TC- O(logn)

3. Count Good Numbers

4. Sort a stack using recursion
5. Reverse a stack using recursion
6. Generate all binary strings
7. Generate Paranthesis
The more optimized approach-
Must remember the recursion calling of this function as it’s confusing-
void f(int n,int open,int close,vector<string>&ans,string temp){
if(temp.size()==n){
ans.push_back(temp);
return;
}
if(open > close){
f(n, open, close + 1,ans, temp+')');
if(open < n/ 2){
f(n, open+1, close, ans,temp+'(');
}
}
else{
f(n, open+1, close, ans,temp+'(');
}
}

8. Power Set: Print all the possible

9. Distinct subsequences of the String-
To count number of distinct subsequences of a string use the given optimized
code- Very important to learn-
int func(string s, int n)
{
int count = 1;
unordered_map<char, int> m1;
for (int i = 0; i < n; i++)
{
if (m1[s[i]] == 0)
{
m1[s[i]] = count;
count *= 2;
}
else
{
int temp = m1[s[i]];
m1[s[i]] = count;
count *= 2;
count -= temp;
}
}
return count;
}

10. More subsequence-You are given two strings 'A' and

11. 'B' of length 'N' and 'M' respectively.
12. Return the string that has more distinct subsequences
13. Subarrays with Sum ‘k'
14. You are given an array 'A' of 'N' integers. You have to return true if there exists a
15. subset of elements of 'A' that sums up to 'K'
//The below given code is very easy to write but the line if(take)return true;
Has drastic power to save the TLE.

bool f(int i,int sum,vector<int>&a){

if(sum==0)return true;
if(sum<0||i==a.size())return false;
bool take=f(i+1,sum-a[i],a);
if(take)return true;
bool nottake=f(i+1,sum,a);
return take||nottake;
}

16. Combination Sum

17. Combination Sum II – Find all unique combinations
//See the highlighted line as it’s saving the time complexity and saving huge time.
void f(int i,vector<int>&a,int sum,set<vector<int>>&us,vector<int>&temp){
if(sum==0){
us.insert(temp);
return;
}
if(sum<0||i==a.size())return;
temp.push_back(a[i]);
f(i+1,a,sum-a[i],us,temp);
temp.pop_back();
//as here i have to do calling for notTake case-> Now If I have already called for some
//element this notTake case then why should I call again for it if it has repeated occurrences.
//Example- If a={1,1,1,2,3}
//So I will be just calling for first 1 and not for others the notTake case as it will mean same.

if(!(temp.size()!=0&&a[i]==temp.back()))f(i+1,a,sum,us,temp);
}

18. Subset Sum : Sum of all Subsets

19. Subset Sum-II| Print all the Unique Subsets
20. Combination Sum III
21. Letter combinations of a phone number
Most Important question-
This will be the recursive function for this question-
void f(int i,string &digits,vector<string>&mp,vector<string>&ans,string &temp){
 if(i==digits.size()){
if(temp.size())ans.push_back(temp);
return;
}
int num=digits[i]-'0';
string str=mp[num];
for(int ind=0;ind<str.size();ind++){
temp.push_back(str[ind]);
f(i+1,digits,mp,ans,temp);
temp.pop_back();
}
}

22. Palindrome Partitioning

void f(int i,string s,vector<vector<string>>&ans,vector<string>&temp){
if(i==s.size()){
ans.push_back(temp);
return;
}
for(int ind=i;ind<s.size();ind++){
string str=s.substr(i,ind-i+1);
string temp1=str;
reverse(temp1.begin(),temp1.end());
if(str==temp1){
temp.push_back(str);
f(ind+1,s,ans,temp);
temp.pop_back();
}
}
}
//Further optimization can be done in the above code by removing the reverse
function…. To do this we can precompute the dp which will tell us about the
palinrome or not for given start and and given end and this will take O(1) time
complexity to solve this problem-
The more optimized implementation is given below->
#include<bits/stdc++.h>
void generate(string &s,vector<vector<bool>>&dp){
 int n=s.size();
for(int i=0;i<n-1;i++)dp[i][i+1]=(s[i]==s[i+1]);
for(int d=2;d<=n-1;d++){
for(int i=0;i+d<n;i++){
dp[i][i+d]=dp[i+1][i+d-1]&&(s[i]==s[i+d]);
}
}
}
void f(int i,string s,vector<vector<string>>&ans,vector<string>&temp,vector<vector<bool>>&dp){
if(i==s.size()){
ans.push_back(temp);
return;
}
for(int ind=i;ind<s.size();ind++){
if(dp[i][ind]){
string str=s.substr(i,ind-i+1);
temp.push_back(str);
f(ind+1,s,ans,temp,dp);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>>ans;
vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),true));
vector<string>temp;
generate(s,dp);
f(0,s,ans,temp,dp);
return ans;
}

23. Word Search

24. N Queen
25. Rat in a Maze
void f(int i,int j,vector<vector<int>>&mat,vector<string>&ans,string temp,vector<vector<int>>&vis){
if(i==mat.size()-1&&j==mat.size()-1&&mat[i][j]){
ans.push_back(temp);
return;
}
if(i<0||i>=mat.size()||j<0||j>=mat.size()||mat[i][j]==0||vis[i][j])return;
vis[i][j]=1;
f(i-1,j,mat,ans,temp+'U',vis);
f(i,j-1,mat,ans,temp+'L',vis);
f(i+1,j,mat,ans,temp+'D',vis);
f(i,j+1,mat,ans,temp+'R',vis);
vis[i][j]=0;
}
vector<string> ratMaze(vector<vector<int>> &mat) {
int n=mat.size();
vector<vector<int>>vis(n,vector<int>(n,0));
vector<string>ans;
string temp="";
f(0,0,mat,ans,temp,vis);
return ans;
 }

26. Word Break

#include<bits/stdc++.h>
void f(int i,string &s,set<string>&us,vector<string>&ans,string &temp){
if(i==s.size()){
ans.push_back(temp);
return;
}
for(int ind=i;ind<s.size();ind++){
string str=s.substr(i,ind-i+1);
string new_str=temp+str;
if(us.find(str)!=us.end()){
if(ind!=s.size()-1)new_str+=" ";
f(ind+1,s,us,ans,new_str);
}
}
}
vector<string> getAllValidSentences(string &s, vector<string> &dict)
{
set<string>us(dict.begin(),dict.end());
vector<string>ans;
string temp="";
f(0,s,us,ans,temp);

return ans;
// write your code here.
}

27. M Coloring Problem

bool safe(int node,int col,vector<int>&color,vector<vector<int>>&mat){
for(int i=0;i<mat.size();i++){
if(i!=node&&mat[node][i]==1&&color[i]==col)return false;
}
return true;
}
bool f(int node,vector<int>&color,vector<vector<int>>&mat,int m){
if(node==mat.size())return true;
for(int col=1;col<=m;col++){
if(safe(node,col,color,mat)){
color[node]=col;
if(f(node+1,color,mat,m))return true;
color[node]=0;
}
}
return false;
}
string graphColoring(vector<vector<int>> &mat, int m){
vector<int>color(mat.size(),0);
if(f(0,color,mat,m))return "YES";
return "NO";
}

28. Sudoko Solver

bool possible(int i,int j,char k,vector<vector<char>>&board){
for(int temp=0;temp<9;temp++){
if(board[i][temp]==k)return false;
if(board[temp][j]==k)return false;
 if(board[3*(i/3)+temp/3][3*(j/3)+temp%3]==k)return false;
}
return true;
}
bool solve(vector<vector<char>>&board){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.'){
for(char k='1';k<='9';k++){
if(possible(i,j,k,board)){
board[i][j]=k;
if(solve(board))return true;
board[i][j]='.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}

Same code on coding ninjas is failing for last 5 test cases. Try to find out why in your
free time.
29. Expression Add Operators->
The multiplication recursive call is very important to understand->
// While doing the multiplication operation, we remove the previous operation and
update it with the multiplication operation
// This is done to follow the BODMAS rules for correct precedence

void f(int i,string sumPath,long sum,long prev,string num,int

target,vector<string>&result){
if(i==num.size()){
if(sum==target)result.push_back(sumPath);
return;
}
for(int j=i;j<num.size();j++){
if(j>i&&num[i]=='0')break;
long number=stol(num.substr(i,j-i+1));
string tempPath=num.substr(i,j-i+1);
if(i==0)f(j+1,tempPath,number,number,num,target,result);
else{

f(j+1,sumPath+'+'+tempPath,sum+number,number,num,target,result);

f(j+1,sumPath+'-'+tempPath,sum-number,-number,num,target,result);

f(j+1,sumPath+'*'+tempPath,sum-prev+(prev*number),prev*number,num,target
,result);
}
}
}
 vector<string> addOperators(string num, int target) {
vector<string>result;
f(0,"",0,0,num,target,result);
return result;
}

Stack and Queues:-

1. Implement Stack using Arrays
2. Implement Queue using Arrays
3. Implement Stack using Queue
These are the steps followed to push.
Other operations will be easy and will be done with the help of q1.front() only.
void push(int element) {
queue<int>q2;
q2.push(element);
while(!q1.empty()){
int ele=q1.front();
q1.pop();
q2.push(ele);
}
swap(q1,q2);
// Implement the push() function.
}

4. Implement Queue using Stack

Just try to think logically-> very easy to implement->

int pop() {

stack<int>s2;
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
int ele=s2.top();
s2.pop();
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
return ele;
}

int peek() {
stack<int>s2;
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
int ele=s2.top();
while(!s2.empty()){
 s1.push(s2.top());
s2.pop();
}
return ele;
}

5. Implement stack using Linkedlist

6. Implement queue using Linkedlist
7. Check for balanced paranthesis
8. Implement Min Stack
Very important mathematical question->
void push(int val) {
if(st.empty()){
mini=val;
st.push(mini);
}
else{
if(val<mini){
st.push(2LL*val-mini);
//PUSH 2X-M//
mini=val;
}
else{
st.push(val);
}
}
}

void pop() {
if(st.empty())return;
long long el=st.top();
st.pop();
if(el<mini){
mini=2LL*mini-el;
//M=2M-X
}

int top() {
if(st.empty())return -1;
long long el=st.top();
if(el<mini)return mini;
return el;
}

This is used to return mini in O(1).

9. Infix to Postfix
Mujhse >=precedence walo ko nikalkr ans mai add kro because I can’t sit on the
top of these elements in the stack.
int pre(char c){
if(c=='+'||c=='-')return 1;
else if(c=='*'||c=='/')return 2;
else if(c=='^')return 3;
return -1;
}
string infixToPostfix(string exp){
// Write your code here
 string ans="";
stack<char>st;
for(auto i:exp){
if((i>='a'&&i<='z')||(i>='A'&&i<='Z')||(i>='0'&&i<='9'))ans+=i;
else if(i=='(')st.push(i);
else if(i==')'){
while(st.size()!=0&&st.top()!='('){
ans+=st.top();
st.pop();
}
st.pop();
}
else{
while(st.size()!=0&&pre(i)<=pre(st.top())){
ans+=st.top();
st.pop();
}
st.push(i);
}
}
while(!st.empty()){
ans+=st.top();
st.pop();
}
return ans;
}

10. Prefix to Infix Conversion

First reverse and then use stack.
#include<stack>
bool op(char c){
if(c=='+'||c=='-'||c=='*'||c=='/')return true;
return false;
}
string prefixToInfixConversion(string &s){
// Write your code here.
string ans="";
stack<string>st;
reverse(s.begin(),s.end());
for(auto i:s){
 if(op(i)){
string a=st.top();
st.pop();
string b=st.top();
st.pop();
string ans='('+a+i+b+')';
st.push(ans);
}
else st.push(string(1,i));
}
return st.top();
}

11. Prefix to Postfix Conversion

Reverse the string and now think to use stack->
string preToPost(string s) {
// Write Your Code Here
reverse(s.begin(),s.end());
stack<string>st;
for(auto i:s){
if(i>='A'&&i<='Z')st.push(string(1,i));
else{
string s1=st.top();
st.pop();
string s2=st.top();
st.pop();
string s3=string(1,i);
string temp=s1+s2+s3;
st.push(temp);
}
}
string ans="";
while(!st.empty()){
ans+=st.top();
st.pop();
}
return ans;
}
 12. Postfix to Prefix Conversion

string postfixToPrefix(string &s){

// Write your code here.
stack<string>st;
for(auto i:s){
if(i=='+'||i=='-'||i=='*'||i=='/'){
string s1=st.top();
st.pop();
string s2=st.top();
st.pop();
st.push(i+s2+s1);
}
else{
st.push(string(1,i));
}
}
string ans="";
while(!st.empty()){
ans+=st.top();
st.pop();
}
return ans;
}

13. Postfix to Infix

string postToInfix(string postfix) {
// Write your code here.
stack<string>st;
for(auto i:postfix){
if((i>='A'&&i<='Z')||(i>='a'&&i<='z'))st.push(string(1,i));
else{
string s1=st.top();
st.pop();
string s2=st.top();
st.pop();
string s3=string(1,i);
string temp='('+s2+i+s1+')';
st.push(temp);
}
}
string ans=st.top();
 return ans;
}

14. Convert Infix To Prefix Notation

15. Next Greater Element

#include<bits/stdc++.h>
vector<int> nextGreaterElement(vector<int>& arr, int n)
{
//move from behind and agar mujhse >= stack mai then remove it
vector<int>ans(n);
stack<int>st;
for(int i=n-1;i>=0;i--){
while(!st.empty()&&st.top()<=arr[i])st.pop();
if(st.empty())ans[i]=-1;
else ans[i]=st.top();
st.push(arr[i]);
}
return ans;
}

16. Next Greater Element 2

vector<int> nextGreaterElements(vector<int>& nums) {
stack<int>st;
int n=nums.size();
vector<int>ans(n);
for(int i=2*n-1;i>=0;i--){
 while(!st.empty()&&st.top()<=nums[i%n])st.pop();
if(i<n){
if(st.empty())ans[i]=-1;
else ans[i]=st.top();
}
st.push(nums[i%n]);
}
return ans;
}

17. Next Smaller Element

VVVVV Important
vector<int> nextGreaterElement(vector<int>& arr, int n)
{
//move from behind and agar mujhse >= stack mai then remove it
vector<int>ans(n);
stack<int>st;
for(int i=n-1;i>=0;i--){
while(!st.empty()&&st.top()<=arr[i])st.pop();
if(st.empty())ans[i]=-1;
else ans[i]=st.top();
st.push(arr[i]);
}
return ans;
}

18. Number of NGEs to the right

19. Trapping Rainwater
From 0 to n-1 add->min(max(leftside),max(rightside))-heght[i]
int trap(vector<int>& height) {
int n=height.size();
vector<int>pre(n);
vector<int>suf(n);
pre[0]=height[0];
suf[n-1]=height[n-1];
for(int i=1;i<n;i++){
pre[i]=max(height[i],pre[i-1]);
 }
for(int i=n-2;i>=0;i--){
suf[i]=max(height[i],suf[i+1]);
}
int ans=0;
for(int i=0;i<n;i++){
ans+=(min(pre[i],suf[i])-height[i]);
}
return ans;
}
To do space optimization of the above code->
int trap(vector<int>& height) {
int n=height.size();
int ans=0;
int l=0;
int r=n-1;
int left_max=0;
int right_max=0;
while(l<=r){
if(height[l]<=height[r]){
if(left_max<=height[l])left_max=height[l];
else ans+=left_max-height[l];
l++;
}
else{
if(right_max<=height[r])right_max=height[r];
else ans+=right_max-height[r];
r--;
}
}
return ans;
}

20. Sum of subarray minimum

Important monotonic stack problem->
Based on next greater element and next smaller element.
int sumSubarrayMins(vector<int>& arr) {
// number of subarrays in which arr[i] is the minimum can be
calculated by (i - left[i]) * (right[i] - i).
long long mod=1e9+7;
int n=arr.size();
vector<int>left(n,-1);
vector<int>right(n,n);
 stack<int>st;
for(int i=0;i<n;i++){
while(!st.empty()&&arr[st.top()]>=arr[i])st.pop();//mujhse >= ko
pop kro
if(!st.empty())left[i]=st.top();
st.push(i);
}
for(auto i:left)cout<<i<<" ";
cout<<endl;
stack<int>st1;
for(int i=n-1;i>=0;i--){
while(!st1.empty()&&arr[st1.top()]>arr[i])st1.pop();//mujhse > ko
pop kro
if(!st1.empty())right[i]=st1.top();
st1.push(i);
}
for(auto i:right)cout<<i<<" ";
cout<<endl;
long long sum=0;
for(int i=0;i<n;i++){
sum+=(long long)((((i-left[i])*(right[i]-i)%mod)*arr[i])%mod);
sum%=mod;
}
return sum;
}

21. Asteroid Collision

//Use of while loop and Stack with maintaining i accordingly
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int i=0;
int n=asteroids.size();
stack<int>st;
while(i<n){
if(st.empty()){
st.push(asteroids[i]);
i++;
}
// else if(st.top()<0&&asteroids[i]>=0){
// if(abs(st.top())>asteroids[i]){
// i++;
// }
// else if(abs(st.top())<asteroids[i]){
// st.pop();
// }
 // else{
// st.pop();
// i++;
// }
// }
else if(st.top()>=0&&asteroids[i]<0){
if(st.top()>abs(asteroids[i]))i++;
else if(st.top()<abs(asteroids[i])){
st.pop();
}
else{
st.pop();
i++;
}
}
else{
st.push(asteroids[i]);
i++;
}
}
vector<int>ans;
while(!st.empty()){
ans.push_back(st.top());
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
};
22. Sum of subarray ranges
Using code of question number 20
long long subArrayRanges(vector<int>& nums) {
vector<int>temp(nums.begin(),nums.end());
for(int i=0;i<temp.size();i++)temp[i]=-1*temp[i];
int mini=sumSubarrayMins(nums);
int maxi=-1*sumSubarrayMins(temp);
return maxi-mini;
}

23. Remove k Digits

string removeKdigits(string num, int k) {
stack<char>st;
for(auto i:num){
if(k>0){
while(!st.empty()&&st.top()>i&&k>0){
st.pop();
k--;
}
}
 if(st.empty()&&i=='0')continue;
st.push(i);
}
while(!st.empty()&&k>0){
st.pop();
k--;
}
if(st.empty())return "0";
string ans="";
while(!st.empty()){
ans+=st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}

24. Largest rectangle in a histogram

Using the question 20 code->
Find the left index till which current i is minimum and finding the right index till which
current i is maximum and then calculating the area accordingly->
int largestRectangleArea(vector<int>& arr) {
int n=arr.size();
vector<int>left(n,-1);
vector<int>right(n,n);
stack<int>st;
for(int i=0;i<n;i++){
while(!st.empty()&&arr[st.top()]>=arr[i])st.pop();//mujhse >= ko pop kro
if(!st.empty())left[i]=st.top();
st.push(i);
}
stack<int>st1;
for(int i=n-1;i>=0;i--){
while(!st1.empty()&&arr[st1.top()]>arr[i])st1.pop();//mujhse > ko pop kro
if(!st1.empty())right[i]=st1.top();
st1.push(i);
}
int ans=INT_MIN;
for(int i=0;i<n;i++){
int area=(right[i]-left[i]-1)*arr[i];
ans=max(ans,area);
}
return ans;
}
 25. Maximal Rectangles
int largestRectangleArea(vector<int>& arr){
int n=arr.size();
vector<int>left(n,-1);
vector<int>right(n,n);
stack<int>st;
for(int i=0;i<n;i++){
while(!st.empty()&&arr[st.top()]>=arr[i])st.pop();//mujhse >= ko
pop kro
if(!st.empty())left[i]=st.top();
st.push(i);
}
stack<int>st1;
for(int i=n-1;i>=0;i--){
while(!st1.empty()&&arr[st1.top()]>arr[i])st1.pop();//mujhse > ko
pop kro
if(!st1.empty())right[i]=st1.top();
st1.push(i);
}
int ans=INT_MIN;
for(int i=0;i<n;i++){
int area=(right[i]-left[i]-1)*arr[i];
ans=max(ans,area);
}
return ans;
}
int maximalRectangle(vector<vector<char>>& m) {
vector<vector<int>>matrix(m.size(),vector<int>(m[0].size(),0));
for(int i=0;i<m.size();i++){
for(int j=0;j<m[0].size();j++){
matrix[i][j]=(m[i][j]-'0');
}
}

int answer=INT_MIN;
for(int i=1;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
matrix[i][j]=matrix[i][j]*(matrix[i-1][j]+matrix[i][j]);
//Multiplication of matrix[i][j] is done to reset the values if a zero if
found………. This is not very much intuitive and hence must remember this.
}
}
 for(int i=0;i<matrix.size();i++){
int temp=largestRectangleArea(matrix[i]);
answer=max(answer,temp);
}
return answer;
}

26. Sliding Window maximum

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>ans;
if(k>nums.size()){
ans.push_back(*max_element(nums.begin(),nums.end()));
return ans;
}
int i=0;
int j=0;
deque<int>q;
while(i<nums.size()&&j<nums.size()){
while(!q.empty()&&q.back()<nums[j])q.pop_back();
q.push_back(nums[j]);
if(j-i+1==k)ans.push_back(q.front());
while(i<nums.size()&&j-i+1>k){
if(!q.empty()&&nums[i]==q.front())q.pop_front();
i++;
if(j-i+1==k)ans.push_back(q.front());
}
j++;
}
return ans;

27. Stock span problem

28. The Celebrity Problem

int findCelebrity(int n) {
// Write your code here.
stack<int>st;
for(int i=0;i<n;i++)st.push(i);
while(st.size()>=2){
int a=st.top();
 st.pop();
int b=st.top();
st.pop();
if(knows(a,b)){
st.push(b);
}
else st.push(a);
}
int ans=st.top();
for(int i=0;i<n;i++){
if (i != ans) {
if (knows(i,ans) == 0 ||knows(ans, i) == 1)return -1;
}
}
return ans;
}

29. LRU cache (IMPORTANT)

30. LFU cache
Stack and Queues

31. Longest Substring Without Repeating Characters

32. Max Consecutive Ones III
33. Fruit into baskets
34. Longest Repeating Character Replacement
int characterReplacement(string s, int k) {
int i=0;
int j=0;
unordered_map<char,int>um;
int ans=0;
int n=s.size();
while(i<n&&j<n){
um[s[j]]++;
int temp=0;
for(auto i:um)temp=max(temp,i.second);
if((j-i+1-temp)<=k)ans=max(ans,j-i+1);
while(i<n&&(j-i+1-temp)>k){
um[s[i]]--;
i++;
// if((j-i+1-temp)<=k)ans=max(ans,j-i+1); this line is not
needed in this case as-> temp might change due to updates in map... but even
using this is not giving any error.
 }
j++;
}
return ans;
}

35. Binary subarray with sum

int countatmostgoal(vector<int>&nums,int goal){
if(goal<0)return 0;
int i=0;
int j=0;
int n=nums.size();
int sum=0;
int ans=0;
while(i<n&&j<n){
sum+=nums[j];
if(sum<=goal)ans+=(j-i+1);
while(i<n&&sum>goal){
sum-=nums[i];
i++;
if(sum<=goal)ans+=j-i+1;
}
j++;
}
return ans;
}
int numSubarraysWithSum(vector<int>& nums, int goal) {
return countatmostgoal(nums,goal)-countatmostgoal(nums,goal-1);
}

36. Count number of nice subarrays

int countatmost(vector<int>&nums,int k){
if(k<0)return 0;
int i=0;
int j=0;
int n=nums.size();
int counti=0;
int ans=0;
while(i<n&&j<n){
if(nums[j]==1)counti++;
if(counti<=k)ans+=(j-i+1);
while(i<n&&counti>k){
if(nums[i]==1)counti--;
 i++;
if(counti<=k)ans+=(j-i+1);
}
j++;
}
return ans;

}
int numberOfSubarrays(vector<int>& nums, int k) {
for(int i=0;i<nums.size();i++)nums[i]=nums[i]%2;
return countatmost(nums,k)-countatmost(nums,k-1);
}

37. Number of Substrings Containing All Three Characters

int numberOfSubstrings(string s) {
vector<int>letter={-1,-1,-1};
int counti=0;
for(int i=0;i<s.size();i++){
letter[s[i]-'a']=i;
if(letter[0]!=-1&&letter[1]!=-1&&letter[2]!=-1){
counti+=(1+min(letter[0],min(letter[1],letter[2])));
}
}
return counti;
}

Second one->
int numberOfSubstrings(string s) {
int i = 0;
int j = 0;
int cnt = 0;
unordered_map<int,int> mp;
while(j < s.length()){
mp[s[j]]++;
if(mp.size() == 3){
while(mp.size() == 3){
cnt += s.length()-j;//left se remove krenge so right wale
saare elements ko add krke bhi valid window bn skti
mp[s[i]]--;
if(mp[s[i]] == 0){
mp.erase(s[i]);
 }
i++;
}
}
j++;

}
return cnt;
}

38. Maximum Points You Can Obtain from Cards

39. Longest-substring-with-at-most-k-distinct-character
int kDistinctChars(int k, string &str)
{
int i=0;
int j=0;
int n=str.size();
int ans=0;
unordered_map<char,int>um;
while(i<n&&j<n){
um[str[j]]++;
if(um.size()<=k)ans=max(ans,j-i+1);
while(i<n&&um.size()>k){
um[str[i]]--;
if(um[str[i]]==0)um.erase(str[i]);
i++;
if(um.size()<=k)ans=max(ans,j-i+1);
}
j++;
}
return ans;
}

40. Subarray with k different integers

int atmost(vector<int>&nums,int k){
if(k<0)return 0;
int i=0;
int j=0;
int n=nums.size();
int counti=0;
unordered_map<int,int>um;
 while(i<n&&j<n){
um[nums[j]]++;
if(um.size()<=k)counti+=j-i+1;
while(i<n&&um.size()>k){
um[nums[i]]--;
if(um[nums[i]]==0)um.erase(nums[i]);
i++;
if(um.size()<=k)counti+=j-i+1;
}
j++;
}
return counti;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return atmost(nums,k)-atmost(nums,k-1);
}

41. Minimum Window Substring

string minWindow(string s, string t) {
int mini=1e9;
int startind=-1;
for(int i=0;i<s.size();i++){
unordered_map<char,int>um;
for(auto temp:t)um[temp]++;
int counti=0;
for(int j=i;j<s.size();j++){
if(um.find(s[j])!=um.end()&&um[s[j]]>0)counti++;
um[s[j]]--;
if(counti==t.size()){
// cout<<i<<" "<<j<<endl;
if(mini>j-i+1){
mini=j-i+1;
startind=i;
break;
}
}
}
}
string ans="";
if(startind!=-1)ans=s.substr(startind,mini);
return ans;
}
 Optimization using the sliding window->
string minWindow(string s, string t) {
int mini=1e9;
int startind=-1;
int i=0;
int j=0;
int n=s.size();
unordered_map<char,int>um;
int counti=0;
for(auto temp:t)um[temp]++;
while(i<n&&j<n){
if(um.find(s[j])!=um.end()&&um[s[j]]>0)counti++;
um[s[j]]--;
if(counti==t.size()){
if(mini>j-i+1){
mini=j-i+1;
startind=i;
}
}
while(i<n&&counti==t.size()){
um[s[i]]++;
if(um[s[i]]>0)counti--;
i++;
if(counti==t.size()){
if(mini>j-i+1){
mini=j-i+1;
startind=i;
}
}
}
j++;
}
string ans="";
if(startind!=-1)ans=s.substr(startind,mini);
return ans;
}

42. Minimum Window Subsequence

string minWindow(string s, string t)
{
 int i=0,j=0,k=0;
int res=INT_MAX;
string str;
while(i<s.size()&&j<s.size()&&k<t.size()){
if(s[j]==t[k])k++;
if(k==t.size()){
i=j;
k--;
while(i>=0&&k>=0){
if(s[i]==t[k])k--;
i--;
}
i++;
if(res>j-i+1){
res=j-i+1;
str=s.substr(i,res);
}
k=0;
j=i+1;
}
j++;
}
return str;
}
The above question code is not intuitive with sliding window for me. So, solve it
again and again by the same code and digest this code very deeply.

Bit Manipulation:-
1. You have a 32-bit unsigned integer called 'num' and
2. another integer called 'i'. You need to perform the
3. following operations on the 'num' integer based on the value of 'i':
4. Check whether K-th bit is set or not
5. You are given an integer 'N'.
6. Return 'odd' if the given number 'N' is odd, else return 'even'.
7. Power of Two
8. Count total set bits
This will help to find the number of set bits by continuously removing the
rightmost set bit.
In worst case it will take O(31) but as in most case all the bits of the number will
not be set bits and hence it will take O(log31) in average case.
int counti=0;
while(N){
 N=N&(N-1); //This is used here to unset the rightmost set bit of N
counti++;
}
return counti;
}
The above code is best when you need to find number of set bits in som particular
numbers but for the case of range total of 1 to N. Use below approach->
The more optimized approach to find total number of set bits from 1 to N->
int countSetBits(int n)
{
if(n==0)return 0;
int x=floor(log2(n));
int y=x*(1<<(x-1));
int z=n-(1<<x);
return y+z+1+countSetBits(z);
}

9. Set The Rightmost Unset Bit

To set the rightmost unset bit->
If you know the position of rightmost unset bit then use-> n|=(1<<i);
Other wise you can directly use-> n |=(n+1); This will set the rightmost unset bit but must
remember to consider the edge case when all the bits are already set.

10. Swap Two Numbers

a=a^b;
b=a^b;
a=a^b;
Or I can use->
a=a+b;
b=a-b;
a=a-b;
Both are correct.

11. Divide Two Integers

while(n>=d){
int cnt=0;
while(n>=d*pow(2,cnt+1))cnt++;
ans+=pow(2,cnt);
n-=d*pow(2,cnt);
 }

Without using even multiplication->

while(n>=d){
int cnt=0;
while(n>=(d<<(cnt+1)))cnt++;
ans+=1<<cnt;
n-=d<<cnt;
}

12. Flip Bits

Int res=A^B;
Now, just find out the number of setbits in res.
13. One Odd Occurring
14. Subsequences of String
Apart from the recursive solution of pick and not pick-> this is also a beautiful solution
using the bit manipulation->
Understood from the striver
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>>ans;
int n=nums.size();
int end=1<<n;
for(int i=0;i<end;i++){
vector<int>temp;
for(int k=0;k<n;k++){
if((i&(1<<k))!=0)temp.push_back(nums[k]);
}
ans.push_back(temp);
}
return ans;
}

15. L to R XOR
Very important question->
int findxor(int n){
if(n%4==1)return 1;
if(n%4==2)return n+1;
if(n%4==3) return 0;
return n;
}
int findXOR(int L, int R){
return findxor(L-1)^findxor(R);
}

16. Two Numbers With Odd Occurrences

17. Count Primes
This is the question to print the prime factors of given number n->
vector<int> countPrimes(int n)
{
vector<int>ans;
for(int i=2;i*i<=n;i++){
if (n % i == 0) {
ans.push_back(i);
while(n%i==0)n/=i;
}
}
if(n!=1)ans.push_back(n);
return ans;
}

18. Print all Divisors of a number

for(int i=1;i*i<=n;i++){
if (n % i == 0) {
arr[ind++] = i;
if(n/i!=i)arr[ind++]=n/i;
}
}
This is the optimized code to print all the divisors of a number n
19. Sieve of Eratosthenes
int countPrimes(int n) {
int counti=0;
vector<long long>temp(n,1);
for(long long i=2;i<n;i++){
if(temp[i]==1){
// cout<<i<<endl;
counti++;
for(long long k=i*i;k<n;k+=i){
temp[k]=0;
}
}
}
 return counti;
}
The array temp will contain the prime numbers where temp[i]==1. So, you can
easily print all the prime number. This code will work for <n and for ==n, you have
to increase the size of the array temp.
20. Power Of Numbers
long long mod=1e9+7;
long long be(long long x,long long n){
if(n==0)return 1;
if(n==1)return x;
if(n%2==0)return be((x*x)%mod,n/2);
else return (x*be(x,n-1))%mod;
}
int power(int n, int r){
return be(n,r);
}
This is also known as binary exponentian

Sliding Window:-
1. Longest Substring Without Repeating Characters
2. Max Consecutive Ones III
3. Fruit Into Baskets
4. Longest Repeating Substring
5. Count Subarrays With K Ones
6. Count number of nice subarrays
7. Count Substring With abc
8. Maximum Points From Cards
9. Longest Substring with At Most K Distinct Characters
10. Subarrays With ‘K’ Distinct Values
11. Minimum Window Substring
#include <bits/stdc++.h>
string smallestWindow(string s, string t)
{
unordered_map<char,int>um;
for(auto i:t)um[i]++;
int count=um.size();
string answer="";
int mini=1e9;
int i=0;
int j=0;
while(i<s.size()&&j<s.size()){
 if(um.find(s[j])!=um.end()){
um[s[j]]--;
if(um[s[j]]==0)count--;
}
if(count==0){
if(mini>j-i+1){
answer=s.substr(i,j-i+1);
mini=j-i+1;
}
}
if(count==0){
while(i<s.size()&&count!=1){
if(um.find(s[i])!=um.end()){
um[s[i]]++;
if(um[s[i]]>0){
count++;
if (mini > j - i + 1) {
answer = s.substr(i, j - i + 1);
mini = j - i + 1;
}
}
}
i++;
}
}
j++;
}
return answer;
// Write your code here.
}

12. Minimum Window Subsequence

Heaps:-
Min heap is used for sorting in Decreasing order.
Max heap is used for sorting in increasing order.
#include <bits/stdc++.h>
using namespace std;

void swap(int &a,int &b){

 int temp=a;
a=b;
b=temp;
}
void hepify(vector<int>&arr,int size,int i){
int index=i;
if(2*i+1<size&&arr[2*i+1]>arr[i])index=2*i+1;
if(2*i+2<size&&arr[2*i+2]>arr[index])index=2*i+2;
if(index!=i){
swap(arr[index],arr[i]);
hepify(arr,size,index);
}
}
void buildheap(vector<int>&arr,int size){
int p=(size/2)-1;
for(int i=p;i>=0;i--){
hepify(arr,size,i);
}
}
void sort(vector<int>&arr,int size){
size--;
swap(arr[0],arr[size]);
hepify(arr,size,0);
if(size>0)sort(arr,size);
}

int main()
{
vector<int>arr={1,2,6,4,3,8,9,75};
cout<<"Available array:";
for(int i=0;i<arr.size();i++)cout<<arr[i]<<" ";
cout<<endl;
buildheap(arr,arr.size());
cout<<"The array after building heap";
for(int i=0;i<arr.size();i++)cout<<arr[i]<<" ";
cout<<endl;
sort(arr,arr.size());
cout<<"The array after sorting is by using inplace sorting algorithm heap sort:"<<endl;
for(int i=0;i<arr.size();i++)cout<<arr[i]<<" ";
return 0;
}

1. Implement a priority queue

2. Min Heap Implementation
class minHeap {
public:
vector<int>heap;
// Constructor for the class.
int capacity;
minHeap(){

}
minHeap(int cap) {
capacity=cap;
// Write your code here.
}
void heapify(vector<int>&arr,int size,int i){
int index=i;
if(2*i+1<size&&arr[2*i+1]<arr[i])index=2*i+1;
if(2*i+2<size&&arr[2*i+2]<arr[index])index=2*i+2;
if(i!=index){
swap(arr[i],arr[index]);
heapify(arr, size, index);
}
}
void buildheap(vector<int>&arr,int size){
int p=(size/2)-1;
for(int i=p;i>=0;i--){
heapify(arr,size,i);
}
}
// Implement the function to remove minimum element.
int extractMinElement() {
if(heap.size()==0)return -1;
int ele=heap[0];
heap[0]=heap[heap.size()-1];
heap.pop_back();
heapify(heap,heap.size(),0);
return ele;
// Write you code here.
}

// Implement the function to delete an element.

void deleteElement(int ind) {
if(heap.size()<ind)return;
// Write you code here.
heap[ind]=heap[heap.size()-1];
heap.pop_back();
// buildheap(heap,heap.size()); No need of build heap here
heapify(heap,heap.size(),ind);
}
 // Implement the function to insert 'val' in the heap.
void insert(int val) {
heap.push_back(val);
buildheap(heap, heap.size());
// Write you code here.
}
};

3. check if an array represents a min heap or not

4. Convert min Heap to max Heap
5. K largest elements
6. Merge K Sorted Arrays
7. Sort K sorted array
8. Merge M sorted Lists
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummynode=new ListNode(0);
ListNode* temp=dummynode;
while(list1&&list2){
if(list1->val<list2->val){
temp->next=list1;
temp=list1;
list1=list1->next;
}
else{
temp->next=list2;
temp=list2;
list2=list2->next;
}
}
if(list1)temp->next=list1;
else if(list2)temp->next=list2;
return dummynode->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans=NULL;
for(int i=0;i<lists.size();i++){
ans=mergeTwoLists(ans,lists[i]);
}
return ans;
}
 9. Replace Each Element Of Array
10. With Its Corresponding Rank
11. Task Scheduler
int leastInterval(vector<char>& tasks, int n){
unordered_map<char,int>um;
for(auto i:tasks)um[i]++;
priority_queue<int>pq;
for(auto i:um)pq.push(i.second);
int ans=0;
while(!pq.empty()){
vector<int>temp;
int time=0;
for(int i=0;i<n+1;i++){
if(!pq.empty()){
temp.push_back(pq.top()-1);
pq.pop();
time++;
}
}
for(auto i:temp)if(i)pq.push(i);
if(pq.empty())ans+=time;
else ans+=n+1;
}
return ans;
}

12. Hands of Straights

bool isNStraightHand(vector<int>& hand, int groupSize) {
if(hand.size()%groupSize!=0)return false;
map<int,int>um;
for(auto i:hand)um[i]++;
for(auto i=um.begin();i!=um.end();){
if(i->second>0){
for(int k=0;k<groupSize;k++){
if(um[i->first+k]>0)um[i->first+k]--;
else return false;
}
}
else i++;
}
return true;
}
 13. Design twitter
14. Connect n ropes with minimum cost
15. Kth Largest Element In A Stream
16. Median in a stream
17. Find Median from Data Stream
18. K most frequent elements
Greedy:-
1. Assign Cookies
2. Fractional Knapsack Problem
3. Find minimum number of coins
4. Lemonade Change
5. Valid Paranthesis Checker
bool checkValidString(string s) {
int leftmin=0;
int leftmax=0;
for(auto i:s){
if(i=='(')leftmin++,leftmax++;
else if(i==')'){
if(leftmin>0)leftmin--;
leftmax--;
}
else{
if(leftmin>0)leftmin--;
leftmax++;
}
if(leftmax<0)return false;
}
if(leftmin!=0)return false;
return true;
}

6. N meetings in one room

Perform the one first which has lesser finishing time.-> If it’s finishing early
and not intersecting with the previous meeting then it can be included in
my answer.
bool intersect(pair<int,int>p1,pair<int,int>p2){
if(p1.first>=p2.second)return true;
return false;
}
int maxMeetings(int start[], int end[], int n)
{
vector<pair<int,int>>v;
for(int i=0;i<n;i++)v.push_back({end[i],start[i]});
 sort(v.begin(),v.end());
pair<int,int>pre=v[0];
int counti =1;
for(int i=1;i<v.size();i++){
pair<int,int>p=v[i];
if(!intersect(pre,p)){
counti++;
pre=p;
}
}
return counti;
// Your code here
}

7. Jump Game
Try to Reach from Backward
bool canJump(vector<int>& nums) {
int index=nums.size()-1;
for(int i=nums.size()-1;i>=0;i--){
if(nums[i]+i>=index)index=i;
}
if(index==0)return true;
return false;
}

8. Jump Game 2
This is also not intuitive so remember how to solve this problem->
int jump(vector<int>& nums) {
int jump=0;
int farthest=0;
int current=0;
for(int i=0;i<nums.size()-1;i++){
farthest=max(farthest,nums[i]+i);
if(i==current){
current=farthest;
jump++;
}
}
return jump;
}

9. Minimum Number of Platforms

What matters to us is that when the train is arriving and when the train is leaving the
platform and hence we can sort both the arrival time and departure time separately to
solve the problem.

int findPlatform(int arr[], int dep[], int n)

{
sort(arr,arr+n);
sort(dep,dep+n);
int counti=1;
int maxplatform=1;
int i=1;
int j=0;
while(i<n&&j<n){
if(arr[i]<=dep[j]){
counti++;
i++;
}
else{
counti--;
j++;
}
maxplatform=max(maxplatform,counti);
}
return maxplatform;
}

10. Job sequencing Problem

static bool compare(Job a,Job b){
return a.profit>b.profit;
}

vector<int> JobScheduling(Job arr[], int n)

{
sort(arr,arr+n,compare);
vector<int>v(n+1,1);
int prof=arr[0].profit;
int counti=1;
int deadline=arr[0].dead;
v[deadline]=0;
for(int i=1;i<n;i++){
int d=arr[i].dead;
int ind=-1;
for(int i=d;i>=1;i--){
if(v[i]==1){
ind=i;
break;
 }
}
if(ind!=-1){
v[ind]=0;
prof+=arr[i].profit;
counti++;
}
}
return {counti,prof};
// your code here
}

11. Candy
int candy(vector<int>& ratings) {
int n=ratings.size();
vector<int>left(n,1);
vector<int>right(n,1);
for(int i=1;i<n;i++){
if(ratings[i]>ratings[i-1])left[i]=1+left[i-1];
}
for(int i=n-2;i>=0;i--){
if(ratings[i]>ratings[i+1])right[i]=1+right[i+1];
}
int ans=0;
for(int i=0;i<n;i++){
ans+=max(left[i],right[i]);
}
return ans;
}

12. shortest job first scheduling algorithm.

The below given code is giving some error->
float sjf(int n, vector<int> &arrivalTime, vector<int> &burstTime)
{
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int,
int>>>> pq;
for(int i=0;i<n;i++){
pq.push({burstTime[i],{i,arrivalTime[i]}});
}
vector<int>completionTime(n);
int time=0;
while(!pq.empty()){
time++;
 auto current=pq.top();
pq.pop();
if(current.first==1){
completionTime[current.second.first]=time;
}
else pq.push({current.first-1,current.second});
}
// for(auto i:completionTime)cout<<i<<" ";
double waitingTime=0;
for(int i=0;i<n;i++){
waitingTime+=(completionTime[i]-arrivalTime[i]-burstTime[i]);
}
waitingTime/=1.0*n;
return waitingTime;
}

13. program for LRU

14. Insert Interval
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& n) {
vector<vector<int>>ans;
for(auto i:intervals){
if(i[0]>n[1]){
ans.push_back(n);
n=i;
}
else if(i[1]<n[0])ans.push_back(i);
else{
int left=min(i[0],n[0]);
int right=max(i[1],n[1]);
n={left,right};
}
}
ans.push_back(n);
return ans;
}

15. Merge Intervals

vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
vector<vector<int>>ans;
vector<int>n=intervals[0];
for(auto i:intervals){
 if(i[0]>n[1]){
ans.push_back(n);
n=i;
}
else if(i[1]<n[0])ans.push_back(i);
else{
int left=min(i[0],n[0]);
int right=max(i[1],n[1]);
n={left,right};
}
}
ans.push_back(n);
return ans;
}

16. Non-overlapping Intervals

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int counti=0;
int end=intervals[0][1];
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]<end){
counti++;
end=min(end,intervals[i][1]);
}
else end=intervals[i][1];
}
return counti;
}

Binary Trees:-
1. Introduction to Trees
2. Binary Tree Representation in C++
Array to Tree Building->
Node *buildtree (int i,vector<int>&arr,int size) {
Node *temp = NULL;
if(i>=size)return temp;
else if (arr[i]){
temp = new Node(arr[i]);
temp->left = buildtree(2*i+1,arr,size);
temp->right = buildtree(2*i+2,arr,size);
 }
else return temp;
}

3. Binary Tree Representation in Java

4. Tree Traversals
5. Preorder Traversal of Binary Tree
6. Inorder Traversal of Binary Tree
7. Post-order Traversal of Binary Tree
8. Level order Traversal
Using recursion and indexing of levels->
void f(TreeNode* root,int i,map<int,vector<int>>&um){
if(root){
um[i].push_back(root->val);
f(root->left,i+1,um);
f(root->right,i+1,um);
}
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>ans;
map<int,vector<int>>um;
f(root,0,um);
int i=0;
while(um.find(i)!=um.end()){
ans.push_back(um[i]);
i++;
}
return ans;
}
Using queue as taught by striver->
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>ans;
if(root==NULL)return ans;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
vector<int>level;
int size=q.size();
for(int i=0;i<size;i++){
TreeNode* temp=q.front();
q.pop();
if(temp->left!=NULL)q.push(temp->left);
 if(temp->right!=NULL)q.push(temp->right);
level.push_back(temp->val);
}
ans.push_back(level);
}
return ans;
}

9. Iterative Preorder Traversal

vector<int> preorderTraversal(TreeNode* root) {
vector<int>ans;
if(root==NULL)return ans;
stack<TreeNode*>st;
st.push(root);
while(!st.empty()){
TreeNode* node=st.top();
st.pop();
ans.push_back(node->val);
if(node->right)st.push(node->right);
if(node->left)st.push(node->left);
}
return ans;
}

10. Iterative Inorder Traversal

vector<int> inorderTraversal(TreeNode* root) {
vector<int>ans;
stack<TreeNode*>st;
TreeNode* node=root;
while(true){
if(node!=NULL){
st.push(node);
node=node->left;
}
else{
if(st.empty())break;
node=st.top();
st.pop();
ans.push_back(node->val);
node=node->right;
}
}
return ans;
}

11. Post-order Traversal of Binary Tree

Using one stack->
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
 stack<TreeNode*> todo;
TreeNode* last = NULL;
while (root || !todo.empty()) {
if (root) {
todo.push(root);
root = root -> left;
} else {
TreeNode* node = todo.top();
if (node -> right && last != node -> right) {
root = node -> right;
} else {
nodes.push_back(node -> val);
last = node;
todo.pop();
}
}
}
return nodes;
}

Using two stack->

Learn this also this can be easily converted using one stack as I have to use vector and
inplace of stack I can store in vector and finally reverse it to return the answer.
vector<int> postorderTraversal(TreeNode* root) {
vector<int>post;
if(root==NULL)return post;
stack<TreeNode*>st1,st2;
st1.push(root);
while(!st1.empty()){
root=st1.top();
st1.pop();
st2.push(root);
if(root->left)st1.push(root->left);
if(root->right)st1.push(root->right);
}
while(!st2.empty()){
post.push_back(st2.top()->val);
st2.pop();
}
return post;
}
 Using one stack in above code but it will take extra vector space to store the
answer->
vector<int> postorderTraversal(TreeNode* root){
vector<int>post;
if(root==NULL)return post;
stack<TreeNode*>st1,st2;
st1.push(root);
while(!st1.empty()){
root=st1.top();
st1.pop();
post.push_back(root->val);
if(root->left)st1.push(root->left);
if(root->right)st1.push(root->right);
}
reverse(post.begin(),post.end());
return post;
}

12. Inorder,Preorder and postorder traversal using single stack for all three->
vector<vector<int>> getTreeTraversal(TreeNode *root){
// Write your code here.
vector<int>pre;
vector<int>pos;
vector<int>ino;
stack<pair<TreeNode*,int>>st;
st.push({root,1});
vector<vector<int>>ans;
if(root==NULL)return ans;
while(!st.empty()){
auto it=st.top();
st.pop();
if(it.second==1){
pre.push_back(it.first->data);
it.second=2;
st.push(it);
if(it.first->left)st.push({it.first->left,1});
}
else if(it.second==2){
ino.push_back(it.first->data);
it.second=3;
st.push(it);
 if(it.first->right)st.push({it.first->right,1});
}
else pos.push_back(it.first->data);
}
ans.push_back(ino);
ans.push_back(pre);
ans.push_back(pos);
return ans;
}

13. Height of a Binary Tree

int height(TreeNode* root){
if(root==NULL)return 0;
return max(1+height(root->left),1+height(root->right));
}

14. Balanced Binary Tree

15. Diameter of Binary Tree
int diameter(TreeNode* root,int &d){
if(root==NULL)return 0;
int l=diameter(root->left,d);
int r=diameter(root->right,d);
d=max(d,l+r);
return 1+max(l,r);
}
16. Maximum path sum
int height(TreeNode* root,int &ans){
if(root==NULL)return 0;
int l=max(0,height(root->left,ans));
int r=max(0,height(root->right,ans));
ans=max(ans,root->val+l+r);
return root->val+max(l,r);
}
int maxPathSum(TreeNode* root) {
int ans=INT_MIN;
height(root,ans);
return ans;
}

17. Check if two trees are identical

bool f(TreeNode* p,TreeNode* q){
if(p==NULL&&q==NULL)return true;
 if(p==NULL||q==NULL)return false;
return (p->val==q->val&&f(p->left,q->left)&&f(p->right,q->right));
}

18. Zig Zag Traversal of Binary Tree

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>>ans;
if(root==NULL)return ans;
queue<TreeNode*>q;
q.push(root);
bool flag=true;
while(!q.empty()){
int size=q.size();
vector<int>temp;
for(int i=0;i<size;i++){
TreeNode* node=q.front();
q.pop();
temp.push_back(node->val);
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
if(flag==false)reverse(temp.begin(),temp.end());
ans.push_back(temp);
flag=!flag;
}
return ans;
}

19. Boundary Traversal of Binary Tree

#include<bits/stdc++.h>
void lef(TreeNode<int>* root,vector<int>&ans){
if(root==NULL)return;
if(root->left==NULL&&root->right==NULL)return;
ans.push_back(root->data);
if(root->left)lef(root->left,ans);
else lef(root->right,ans);
}
void level(TreeNode<int>*root,vector<int>&ans){
if(root==NULL)return;
if(root->left==NULL&&root->right==NULL){
ans.push_back(root->data);
 return;
}
level(root->left,ans);
level(root->right,ans);
}
void rig(TreeNode<int>* root,stack<int>&st){
if(root==NULL)return;
if(root->left==NULL&&root->right==NULL)return;
st.push(root->data);
if(root->right)rig(root->right,st);
else rig(root->left,st);
}
vector<int> traverseBoundary(TreeNode<int> *root)
{
vector<int>ans;
if(root==NULL)return ans;
if(root->left||root->right)ans.push_back(root->data);
// ans.push_back(root->data);
lef(root->left,ans);
level(root,ans);
stack<int>st;
rig(root->right,st);
while(st.size()!=0){
ans.push_back(st.top());
st.pop();
}
return ans;
// Write your code here.
}

20. Vertical Order Traversal of Binary

vector<vector<int>> verticalTraversal(TreeNode* root) {

map<int,map<int,multiset<int>>>um;
vector<vector<int>>ans;
queue<pair<TreeNode*,pair<int,int>>>q;
q.push({root,{0,0}});
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
 auto p=q.front();
TreeNode* node=p.first;
q.pop();
um[p.second.first][p.second.second].insert(node->val);

if(node->left)q.push({node->left,{p.second.first-1,p.second.second+1}});

if(node->right)q.push({node->right,{p.second.first+1,p.second.second+1}});
}
}

for(auto i:um){
vector<int>temp;
for(auto p:i.second){
temp.insert(temp.end(),p.second.begin(),p.second.end());
}
ans.push_back(temp);
}
return ans;
}

21. Top View of Binary Tree

vector<int> topView(Node *root)
{
map<int,int>um;
vector<int>ans;
if(root==NULL)return ans;
queue<pair<Node*,int>>q;
q.push({root,0});
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
Node* node=q.front().first;
int line=q.front().second;
q.pop();
if(um.find(line)==um.end())um[line]=node->data;
if(node->left)q.push({node->left,line-1});
if(node->right)q.push({node->right,line+1});
}
}
for(auto i:um)ans.push_back(i.second);
return ans;
//Your code here
}
 22. Bottom View of Binary Tree
vector <int> bottomView(Node *root) {
// Your Code Here
vector<int>ans;
if(root==NULL)return ans;
queue<pair<Node*,int>>q;
map<int,int>um;
q.push({root,0});
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
Node* node=q.front().first;
int level=q.front().second;
q.pop();
um[level]=node->data;
if(node->left)q.push({node->left,level-1});
if(node->right)q.push({node->right,level+1});
}
}
for(auto i:um)ans.push_back(i.second);
return ans;
}

23. Right/Left View of Binary Tree

Left view->
Only first element on each horizontal level->
vector<int> printLeftView(BinaryTreeNode<int>* root) {
// Write your code here.
vector<int>ans;
// f(root,ans);
if(root==NULL)return ans;
map<int,int>um;
queue<pair<BinaryTreeNode<int>*,int>> q;
q.push({root,0});
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
BinaryTreeNode<int>*node=q.front().first;
int level=q.front().second;
q.pop();
if(um.find(level)==um.end())um[level]=node->data;
if(node->left)q.push({node->left, level + 1});
 if(node->right)q.push({node->right, level + 1});
}
}
for(auto i:um)ans.push_back(i.second);
return ans;
}
Right view->
Just one line change for->
Only last element on each horizontal level->
vector<int> rightSideView(TreeNode* root) {
vector<int>ans;
if(root==NULL)return ans;
map<int,int>um;
queue<pair<TreeNode*,int>>q;
q.push({root,0});
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
TreeNode* node=q.front().first;
int level=q.front().second;
q.pop();
um[level]=node->val;
if(node->left)q.push({node->left,level+1});
if(node->right)q.push({node->right,level+1});
}
}
for(auto i:um)ans.push_back(i.second);
return ans;
}

24. Symmetric binary tree

bool f(TreeNode* root1,TreeNode* root2){
if(root1==NULL&&root2==NULL)return true;
if(root1==NULL||root2==NULL)return false;
return
(root1->val==root2->val)&&(f(root1->left,root2->right)&&f(root1->right,root2->l
eft));
}

25. Root to Node Path in Binary Tree

void f(TreeNode* root,vector<string>&ans,string s){
if(root==NULL)return;
 if(root->left==NULL&&root->right==NULL){
s=s+to_string(root->val);
ans.push_back(s);
return;
}
s=s+to_string(root->val);
s=s+"->";
f(root->left,ans,s);
f(root->right,ans,s);
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>ans;
string s="";
if(root==NULL)return ans;
f(root,ans,s);
return ans;
}

26. LCA in Binary Tree

TreeNode* lowestCommonAncestor(TreeNode* root,
TreeNode* p, TreeNode* q) {
if(root==NULL||root==p||root==q)return root;
TreeNode* l=lowestCommonAncestor(root->left,p,q);
TreeNode* r=lowestCommonAncestor(root->right,p,q);
if(l==NULL)return r;
if(r==NULL)return l;
return root;
}

27. Maximum width of a binary tree

Leetcode version->
int widthOfBinaryTree(TreeNode* root) {
if(root==NULL)return 0;
int ans=0;
queue<pair<TreeNode*,long long>>q;
q.push({root,0});
while(!q.empty()){
int s=q.size();
int mini=0;
int maxi=0;
for(int i=0;i<s;i++){
TreeNode* node=q.front().first;
 int ind=q.front().second;
if(i==0)mini=ind;
if(i==s-1)maxi=ind;
q.pop();
if(node->left)q.push({node->left,2LL*ind+1});
if(node->right)q.push({node->right,2LL*ind+2});
}
ans=max(ans,maxi-mini+1);
}
return ans;
}

28. Check for Children Sum Property

bool isParentSum(Node *root){
// Write your code here.
if(root==NULL)return true;
if(root->left==NULL&&root->right==NULL)return true;
int l=0,r=0;
if(root->left)l=root->left->data;
if(root->right)r=root->right->data;
return (root->data==l+r)&&(isParentSum(root->left))&&(isParentSum(root->right));
}

Striver version->
If you can increase value by one as many times as we want->
29. All Nodes Distance K in Binary Tree
void markparents(TreeNode* root,unordered_map<TreeNode*,TreeNode*>&um){
if(root==NULL)return;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
TreeNode* node=q.front();
q.pop();
if(node->left){
um[node->left]=node;
q.push(node->left);
}
if(node->right){
um[node->right]=node;
q.push(node->right);
}
}
}
 }
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
unordered_map<TreeNode*,TreeNode*>um;//this will store parents
markparents(root,um);

queue<TreeNode*>q;
q.push(target);//starting the traversal fromt the target node
unordered_map<TreeNode*,bool>vis;
vis[target]=true;
int level=0;
while(!q.empty()){
if(level++==k)break;
int s=q.size();
for(int i=0;i<s;i++){
TreeNode* node=q.front();
q.pop();
if(node->left&&!vis[node->left]){
q.push(node->left);
vis[node->left]=true;
}
if(node->right&&!vis[node->right]){
q.push(node->right);
vis[node->right]=true;
}
if(um[node]&&!vis[um[node]]){
q.push(um[node]);
vis[um[node]]=true;
}
}
}
vector<int>ans;
while(!q.empty()){
ans.push_back(q.front()->val);
q.pop();
}
return ans;
}

30. Minimum time taken to BURN the Binary tree

A proud moment for me->
I have solved this question by my own without any help just after solving the above
question.
This was entirely new question for me but I make it.
#include<bits/stdc++.h>
void
markparents(BinaryTreeNode<int>*root,unordered_map<BinaryTreeNode<int>*,BinaryTreeNode<int
>*>&um){
if(root==NULL)return;
queue<BinaryTreeNode<int>*>q;
q.push(root);
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
BinaryTreeNode<int>*node=q.front();
q.pop();
if(node->left){
q.push(node->left);
um[node->left]=node;
}
if(node->right){
q.push(node->right);
um[node->right]=node;
}
}
}
}
BinaryTreeNode<int>* tellnode(BinaryTreeNode<int>* root,int start){
if(root==NULL)return NULL;
if(root->data==start)return root;
BinaryTreeNode<int>* L=tellnode(root->left,start);
BinaryTreeNode<int>* R=tellnode(root->right,start);
if(L)return L;
if(R)return R;
return NULL;
}
int timeToBurnTree(BinaryTreeNode<int>* root, int start)
{
unordered_map<BinaryTreeNode<int>*,BinaryTreeNode<int>*>um;
markparents(root,um);
BinaryTreeNode<int>* startnode=tellnode(root,start);
unordered_map<BinaryTreeNode<int>*,bool>vis;
 queue<BinaryTreeNode<int>*>q;
int time=-1;
q.push(startnode);
vis[startnode]=true;
while(!q.empty()){
time++;
int s=q.size();
for(int i=0;i<s;i++){
BinaryTreeNode<int>*node=q.front();
q.pop();
if(node->left&&!vis[node->left]){
q.push(node->left);
vis[node->left]=true;
}
if(node->right&&!vis[node->right]){
q.push(node->right);
vis[node->right]=true;
}
if(um[node]&&!vis[um[node]]){
q.push(um[node]);
vis[um[node]]=true;
}
}
}
return time;
}

void markparents(TreeNode* root,unordered_map<TreeNode*,TreeNode*>&um){

if(root==NULL)return;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int s=q.size();
for(int i=0;i<s;i++){
TreeNode* node=q.front();
q.pop();
if(node->left){
um[node->left]=node;
q.push(node->left);
 }
if(node->right){
um[node->right]=node;
q.push(node->right);
}
}
}
}
TreeNode* findnode(TreeNode* root,int start){
if(root==NULL)return NULL;
if(root->val==start)return root;
TreeNode* L=findnode(root->left,start);
TreeNode* R=findnode(root->right,start);
if(L)return L;
if(R)return R;
return NULL;
}
int amountOfTime(TreeNode* root, int start){
unordered_map<TreeNode*,TreeNode*>um;
markparents(root,um);
TreeNode* targetnode=findnode(root,start);
queue<TreeNode*>q;
unordered_map<TreeNode*,bool>vis;
q.push(targetnode);
vis[targetnode]=true;
int time=-1;
while(!q.empty()){
time++;
int s=q.size();
for(int i=0;i<s;i++){
TreeNode* node=q.front();
q.pop();
if(node->left&&!vis[node->left]){
q.push(node->left);
vis[node->left]=true;
}
if(node->right&&!vis[node->right]){
q.push(node->right);
vis[node->right]=true;
}
if(um[node]&&!vis[um[node]]){
q.push(um[node]);
 vis[um[node]]=true;
}
}
}
return time;
}

31. Count Complete Tree Nodes

int f(BinaryTreeNode<int>*root){
if(root==NULL)return 0;
return 1+f(root->left)+f(root->right);
}
int countNodes(BinaryTreeNode<int> *root) {
// Write your code here.
return f(root);
}

It’s giving TLE so use the below give approach->

int leftheight(BinaryTreeNode<int>*root){
if(root==NULL)return 0;
return 1+leftheight(root->left);
}
int rightheight(BinaryTreeNode<int>*root){
if(root==NULL)return 0;
return 1+rightheight(root->right);
}

int countNodes(BinaryTreeNode<int> *root) {

// Write your code here.
int l=leftheight(root);
int r=rightheight(root);
if(l==r)return (1<<r)-1;//( 2 to the power h) minus 1 is the number of node is a full binary tree
return 1+countNodes(root->left)+countNodes(root->right);
}
Time Complexity is (logn)^2

32. Requirements needed to construct

Must have inorder with any one from preorder/postorder to get unique tree.
33. Construct Binary Tree from Preorder and Inorder Traversal
TreeNode* build(int prel,int prer,vector<int>&preoder,int inl,int
inr,vector<int>&inorder,map<int,int>&um){
 if(prel>prer||inl>inr)return NULL;
TreeNode* root=new TreeNode(preoder[prel]);
int indexroot=um[root->val];
int leftcount=indexroot-inl;

root->left=build(prel+1,prel+leftcount,preoder,inl,indexroot-1,inorder,um
);

root->right=build(prel+leftcount+1,prer,preoder,indexroot+1,inr,inorder,u
m);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
map<int,int>um;
for(int i=0;i<inorder.size();i++){
um[inorder[i]]=i;
}
return
build(0,preorder.size()-1,preorder,0,inorder.size()-1,inorder,um);
}

TreeNode<int>* build(vector<int>&inorder,int inl, int inr,vector<int>&preorder,int prel,int

prer,map<int,int>&um){
if(inl>inr||prel>prer)return NULL;
TreeNode<int>* root=new TreeNode<int>(preorder[prel]);
int rootindex=um[root->data];
int leftcount=rootindex-inl;
root->left=build(inorder, inl,rootindex-1, preorder, prel+1, prel+leftcount,um);
root->right=build(inorder, rootindex+1, inr,preorder,prel+leftcount+1,prer,um);
return root;
}
TreeNode<int> *buildBinaryTree(vector<int> &inorder, vector<int> &preorder)
{
map<int,int>um;
for(int i=0;i<inorder.size();i++)um[inorder[i]]=i;
return build(inorder,0,inorder.size()-1,preorder,0,preorder.size()-1,um);
// Write your code here
}
 34. Construct Binary Tree from Inorder and Postorder Traversal
TreeNode* build(vector<int>&inorder,int inl,int
inr,vector<int>&postorder,int posl,int posr,map<int,int>&um){
if(inl>inr||posl>posr)return NULL;
TreeNode* root=new TreeNode(postorder[posr]);
int rootindex=um[root->val];
int leftcount=rootindex-inl;

root->left=build(inorder,inl,rootindex-1,postorder,posl,posl+leftcount-1,um);

root->right=build(inorder,rootindex+1,inr,postorder,posl+leftcount,posr-1,um);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
map<int,int>um;
for(int i=0;i<inorder.size();i++)um[inorder[i]]=i;
return
build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1,um);
}
#include <map>
TreeNode<int>* build(vector<int>&postorder,int posl,int posr,vector<int>&inorder,int inl,int
inr,map<int,int>&um){
if(posl>posr||inl>inr)return NULL;
TreeNode<int>*root=new TreeNode<int>(postorder[posr]);
int rootindex=um[root->data];
int leftcount=rootindex-inl;
root->left=build(postorder,posl,posl+leftcount-1,inorder,inl,rootindex-1,um);
root->right=build(postorder,posl+leftcount,posr-1,inorder,rootindex+1,inr,um);
return root;
}
TreeNode<int>* getTreeFromPostorderAndInorder(vector<int>& postOrder, vector<int>& inOrder){
// Write your code here.
map<int,int>um;
for(int i=0;i<inOrder.size();i++)um[inOrder[i]]=i;
return build(postOrder,0,postOrder.size()-1,inOrder,0,inOrder.size()-1,um);

35. Serialize and Deserialize Binary Tree

Solved by me by using inorder and preorder traversal->
But it’s limitations are->
It will fail if any of the node value is repeated->This issue will always fails here.
It will fail if any of node has value greater than 9 i.e., only 0 to 9 values are
allowed in nodes. I can use , to deal with this issue.
void preorder(TreeNode* root,string &pre){
if(root==NULL)return;
pre+=to_string(root->val);
preorder(root->left,pre);
preorder(root->right,pre);
}
void inorder(TreeNode* root,string &ino){
if(root==NULL)return;
inorder(root->left,ino);
ino+=to_string(root->val);
inorder(root->right,ino);
}
string serialize(TreeNode* root) {
string pre="";
string ino="";
preorder(root,pre);
inorder(root,ino);
string ans=pre+'+'+ino;
return ans;
}

// Decodes your encoded data to tree.

TreeNode* build(int prel,int prer,vector<int>&preoder,int inl,int
inr,vector<int>&inorder,map<int,int>&um){
if(prel>prer||inl>inr)return NULL;
TreeNode* root=new TreeNode(preoder[prel]);
int indexroot=um[root->val];
int leftcount=indexroot-inl;

root->left=build(prel+1,prel+leftcount,preoder,inl,indexroot-1,inorder,um);

root->right=build(prel+leftcount+1,prer,preoder,indexroot+1,inr,inorder,um);
return root;
}
TreeNode* deserialize(string data) {
vector<int>preorder;
vector<int>inorder;
int ind=0;
 while(ind<data.size()&&data[ind]!='+'){
string temp=to_string(data[ind]);
int value=stoi(temp)-48;
preorder.push_back(value);
ind++;
}
ind++;
while(ind<data.size()){
string temp=to_string(data[ind]);
int value=stoi(temp)-48;
inorder.push_back(value);
ind++;
}
map<int,int>um;
for(int i=0;i<inorder.size();i++){
um[inorder[i]]=i;
}
return
build(0,preorder.size()-1,preorder,0,inorder.size()-1,inorder,um);
}

According to the approach told by striver using Modified level order traversal->
string serialize(TreeNode* root) {
if(!root)return "";
string s="";
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
TreeNode* node=q.front();
q.pop();
if(node==NULL)s.append("#,");
else s.append(to_string(node->val)+',');
if(node){
q.push(node->left);
q.push(node->right);
}
}
return s;
}

// Decodes your encoded data to tree.

 TreeNode* deserialize(string data) {
if(data.size()==0)return NULL;
stringstream s(data);
string str;
getline(s,str,',');
TreeNode* root=new TreeNode(stoi(str));
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
TreeNode* node=q.front();
q.pop();
getline(s,str,',');
if(str=="#")node->left=NULL;
else{
TreeNode *leftnode=new TreeNode(stoi(str));
node->left=leftnode;
q.push(leftnode);
}
getline(s,str,',');
if(str=="#")node->right=NULL;
else{
TreeNode* rightnode=new TreeNode(stoi(str));
node->right=rightnode;
q.push(rightnode);
}

}
return root;
}

36. Binary Tree Inorder Traversal Using Morris Traversal->

vector<int> inorderTraversal(TreeNode* root) {

TreeNode* curr=root;
vector<int>ans;
while(curr){
if(curr->left==NULL){
ans.push_back(curr->val);
curr=curr->right;
}
else{
TreeNode *temp=curr->left;
 while(temp->right&&temp->right!=curr){
temp=temp->right;
}
if(temp->right==NULL){
temp->right=curr;
curr=curr->left;
}
else{
temp->right=NULL;
ans.push_back(curr->val);
curr=curr->right;
}
}
}
return ans;
}

Morris Preorder Traversal->

vector<int> inorderTraversal(TreeNode* root) {
TreeNode* curr=root;
vector<int>ans;
while(curr){
if(curr->left==NULL){
ans.push_back(curr->val);
curr=curr->right;
}
else{
TreeNode *temp=curr->left;
while(temp->right&&temp->right!=curr){
temp=temp->right;
}
if(temp->right==NULL){
temp->right=curr;
ans.push_back(curr->val);
curr=curr->left;
}
else{
temp->right=NULL;
curr=curr->right;
}
}
 }
return ans;
}

37. Flatten Binary Tree to Linked List

Recursive->
TreeNode* pre=NULL;
void flatten(TreeNode* root) {
if(root==NULL)return;
flatten(root->right);
flatten(root->left);
root->right=prev;
root->left=NULL;
prev=root;
}
Iterative->
void flatten(TreeNode* root) {
if(root==NULL)return;
stack<TreeNode*>st;
st.push(root);
while(!st.empty()){
TreeNode* node=st.top();
st.pop();
if(node->right)st.push(node->right);
if(node->left)st.push(node->left);
if(!st.empty())node->right=st.top();
node->left=NULL;
}
}

38. Sum Tree GFG-> If root is the sum it’s left subtree nodes and right sub tree
nodes except the leaf nodes
int add(Node* root){
if(root==NULL)return 0;
return root->data+add(root->left)+add(root->right);
}
bool isSumTree(Node* root)
{
if(root==NULL)return true;
if(root->left==NULL&&root->right==NULL)return true;
int l=add(root->left);
int r=add(root->right);
return (root->data==l+r)&&isSumTree(root->left)&&isSumTree(root->right);
}
Binary Search Tree:-
1. Introduction to Binary Search Tree
Inorder traversal is always sorted-> L<Node<R in general
But if you want duplicates then either of two are the possibilities->
L<=Node<R more preferred over L<Node<=R
2. Search in a Binary Search Tree
TreeNode* searchBST(TreeNode* root, int val) {
if(root==NULL)return NULL;
if(root->val==val)return root;
if(root->val>val)return searchBST(root->left,val);
return searchBST(root->right,val);
}

3. Find Min/Max in BST

Find the leftmost or rightmost value in BST.
4. Ceil in a Binary Search Tree
Using Iterative method->
int findCeil(BinaryTreeNode<int> *node, int x){
// Write your code here.
int ans=-1;
while(node){
if(node->data==x){
ans=x;
break;
}
else if(node->data>x){
ans=node->data;
node=node->left;
}
else node=node->right;
}
return ans;
}

Using Recursion->
void f(BinaryTreeNode<int>*node,int x,int &ans){
if(node==NULL)return;
if(node->data==x){
ans=x;
 return;
}
else if(node->data>x){
ans=node->data;
f(node->left,x,ans);
}
else f(node->right,x,ans);
}
int findCeil(BinaryTreeNode<int> *node, int x){
int ans=-1;
f(node,x,ans);
return ans;
}

5. Floor in a Binary Search Tree

int Floor(BinaryTreeNode<int> *node, int input)
{

int ans=-1;
while(node){
if(node->data==input){
ans=node->data;
break;
}
else if(node->data<input){
ans=node->data;
node=node->right;
}
else node=node->left;
}
return ans;
}

6. Insert a given Node in Binary Search Tree

void insert(TreeNode* &root,int val){
if(root==NULL){
root=new TreeNode(val);
return;
}
 if(root->val>val){
if(root->left==NULL){
root->left=new TreeNode(val);
return;
}
else insert(root->left,val);

}
else{
if(root->right==NULL){
root->right=new TreeNode(val);
return;
}
else insert(root->right,val);
}
}
TreeNode* insertIntoBST(TreeNode* root, int val){
insert(root,val);
return root;
}

Iterative->
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==NULL){
root=new TreeNode(val);
return root;
}
TreeNode* temp=root;
while(temp){
if(temp->val>val){
if(temp->left==NULL){
temp->left=new TreeNode(val);
break;
}
else temp=temp->left;
}
else{
if(temp->right==NULL){
temp->right=new TreeNode(val);
break;
}
 else temp=temp->right;
}
}
return root;
}

7. Delete a Node in Binary Search Tree

Learning by solving this question->
root=root->right means we replace root node by root->right and hence all the links
pointing to root will point to root->right.

Studied during Data Structures in college->

Using recursion->
int maxi(TreeNode* root){
if(root->right==NULL)return root->val;
return maxi(root->right);
}
int mini(TreeNode* root){
if(root->left==NULL)return root->val;
return mini(root->left);
}
void deleteit(TreeNode* &root,int key){
if(root==NULL)return;
if(root->val==key){
if(root->left==NULL&&root->right==NULL){
root=NULL;
}
else if(root->left==NULL)root=root->right;
else if(root->right==NULL)root=root->left;
else{
// root->val=maxi(root->left);
// deleteit(root->left,root->val);

//OR I CAN USE BELOW ALSO

root->val=mini(root->right);
deleteit(root->right,root->val);
}
}
else if(root->val>key)deleteit(root->left,key);
else deleteit(root->right,key);
}
TreeNode* deleteNode(TreeNode* root, int key) {
deleteit(root,key);
 return root;
}

The above same code with these changes will also work->
int maxi(TreeNode* root){
if(root->right==NULL)return root->val;
return maxi(root->right);
}
int mini(TreeNode* root){
if(root->left==NULL)return root->val;
return mini(root->left);
}
void deleteit(TreeNode* &root,int key){
if(root==NULL)return;
if(root->val==key){
if(root->left==NULL&&root->right==NULL){
root=NULL;
}
else if(root->left==NULL)root=root->right;
else if(root->right==NULL)root=root->left;
else{
root->val=maxi(root->left);
deleteit(root->left,root->val);
}
}
else if(root->val>key)deleteit(root->left,key);
else deleteit(root->right,key);
}
TreeNode* deleteNode(TreeNode* root, int key) {
deleteit(root,key);
return root;
}

The below Iterative code of above code done by me are not working -> Try to
find out why it is not working->
int maxi(TreeNode* root){
if(root->right==NULL)return root->val;
 return maxi(root->right);
}
int mini(TreeNode* root){
if(root->left==NULL)return root->val;
return mini(root->left);
}
TreeNode* deleteNode(TreeNode* root1, int key) {
TreeNode* root=root1;
if(root1==NULL)return root1;
while(root){
if(root->val==key){
if(root->left==NULL&&root->right==NULL){
root=NULL;
}
else if(root->left==NULL){
root->val=mini(root->right);
root=root->right;
key=root->val;
}
else{
root->val=maxi(root->left);
root=root->left;
key=root->val;
}
}
else if(root->val>key)root=root->left;
else root=root->right;
}
return root1;
}
Also this below code is not working->
int maxi(TreeNode* root){
if(root->right==NULL)return root->val;
return maxi(root->right);
}
int mini(TreeNode* root){
if(root->left==NULL)return root->val;
return mini(root->left);
}

TreeNode* deleteNode(TreeNode* root1, int key) {

TreeNode* root=root1;
 if(root1==NULL)return root1;
while(root){
if(root->val==key){
if(root->left==NULL&&root->right==NULL){
root=NULL;
}
else if(root->left==NULL){
root=root->right;
break;
}
else if(root->right==NULL){
root=root->left;
break;
}
else{
root->val=maxi(root->left);
root=root->left;
key=root->val;
}
}
else if(root->val>key)root=root->left;
else root=root->right;
}
return root1;
}

Iterative->
Taught by striver but it is also using the recursive method->
Watch the video again and try to solve it by striver method->
This method is important as it’s deleting the node and not doing the task by just altering
the values.
8. Find K-th smallest/largest element
void inorder(TreeNode* root,vector<int>&pre){
if(root==NULL)return;
inorder(root->left,pre);
pre.push_back(root->val);
inorder(root->right,pre);
}
int kthSmallest(TreeNode* root, int k) {
vector<int>ino;
 inorder(root,ino);
return ino[k-1];
}
For kth largest->
You can solve for N-Kth smallest
OR
You can solve for getting the descending order traversal of BST which can be easily
obtained by changing/ swapping the recursive calls in the inorder function.
9. Check if a tree is a BST or BT
Use Range concept

bool check(TreeNode* root,long long l,long long r){

if(root==NULL)return true;
if(root->val>=r||root->val<=l)return false;
return
check(root->right,root->val,r)&&check(root->left,l,root->val);
}
bool isValidBST(TreeNode* root) {
long long l=-1e10;
long long r=1e10;
return check(root,l,r);
}

10. LCA in Binary Search Tree

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL||root==p||root==q)return root;
TreeNode* l=lowestCommonAncestor(root->left,p,q);
TreeNode* r=lowestCommonAncestor(root->right,p,q);
if(l==NULL)return r;
if(r==NULL)return l;
return root;
}
This is used in LCA in binary tree->
But it can optimized due the BST property->
My way->
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if(root==NULL||(p->val>=root->val&&q->val<=root->val)||(p->val<=root->val&&q->v
al>=root->val))return root;
if(p->val>root->val)return lowestCommonAncestor(root->right,p,q);
return lowestCommonAncestor(root->left,p,q);
}
Striver way->
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)return root;
if(root->val<p->val&&root->val<q->val)return
lowestCommonAncestor(root->right,p,q);
if(root->val>p->val&&root->val>q->val)return
lowestCommonAncestor(root->left,p,q);
return root;
}

11. Construct a BST from a preorder traversal

Using binary tree building method->
TreeNode* build(vector<int>&preorder,int prel,int
prer,vector<int>&inorder,int inl,int inr,map<int,int>&um){
if(prel>prer||inl>inr)return NULL;
TreeNode* root=new TreeNode(preorder[prel]);
int index=um[root->val];
int leftlength=index-inl;

root->left=build(preorder,prel+1,prel+leftlength+1,inorder,inl,index-1,um);

root->right=build(preorder,prel+leftlength+1,prer,inorder,index+1,inr,um);
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
vector<int>inorder=preorder;
sort(inorder.begin(),inorder.end());
map<int,int>um;
for(int i=0;i<inorder.size();i++)um[inorder[i]]=i;
return
build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1,um);
}

By using the property of BST->

By me but taking more time->
void insert(TreeNode* &root,int key){
if(root==NULL){
root=new TreeNode(key);
return;
}
if(root->val>key)insert(root->left,key);
else insert(root->right,key);
 }
TreeNode* bstFromPreorder(vector<int>& preorder) {
if(preorder.size()==0)return NULL;
TreeNode* root=NULL;
for(auto i:preorder)insert(root,i);
return root;
}

Striver optimized code->

TreeNode* build(int &i,int bound,vector<int>&preorder){
if(i==preorder.size()||preorder[i]>bound)return NULL;
TreeNode* root=new TreeNode(preorder[i++]);
root->left=build(i,root->data,preorder);
root->right=build(i,bound,preorder);
return root;

}
TreeNode *preOrderTree(vector<int> &preOrder)
{
int i=0;
return build(i,INT_MAX,preOrder);
// Write your code here.
}

Very good code.

12. Inorder Successor/Predecessor in BST
pair<int, int> predecessorSuccessor(TreeNode *root, int key)
{
int pre=-1;
int suc=-1;
TreeNode* temp=root;
while(temp){
if(temp->data>=key)temp=temp->left;
else{
pre=temp->data;
temp=temp->right;
}
}
while(root){
if(root->data<=key)root=root->right;
 else {
suc=root->data;
root=root->left;
}
}
return {pre,suc};
}

13. Merge 2 BST's

void inorder(TreeNode* root,vector<int>&nums){
if(root==NULL)return;
inorder(root->left,nums);
nums.push_back(root->data);
inorder(root->right,nums);
}
void merge(vector<int>&ans,vector<int>&nums1,vector<int>&nums2){
int i=0;
int j=0;
while(i<nums1.size()&&j<nums2.size()){
if(nums1[i]<=nums2[j]){
ans.push_back(nums1[i]);
i++;
}
else {
ans.push_back(nums2[j]);
j++;
}
}
while(i<nums1.size()){
ans.push_back(nums1[i]);
i++;
}
while(j<nums2.size()){
ans.push_back(nums2[j]);
j++;
}
}
vector<int> mergeBST(TreeNode *root1, TreeNode *root2)
{
vector<int>nums1;
 inorder(root1,nums1);
vector<int>nums2;
inorder(root2,nums2);

vector<int>nums3;
merge(nums3,nums2,nums1);
return nums3;
}

Binary Search Iterator:

class BSTIterator {
public:
stack<TreeNode*>st;
BSTIterator(TreeNode* root) {
while(root){
st.push(root);
root=root->left;
}
}

int next() {
int ans=st.top()->val;
TreeNode* temp=st.top()->right;
st.pop();
while(temp){
st.push(temp);
temp=temp->left;
}
return ans;
}

bool hasNext() {
return !st.empty();
}
};

14. Two Sum In BST

void inorder(TreeNode* root,vector<int>&ino){
if(root==NULL)return;
inorder(root->left,ino);
ino.push_back(root->val);
inorder(root->right,ino);
 }
bool findTarget(TreeNode* root, int k) {
vector<int>ino;
inorder(root,ino);
int i=0;
int j=ino.size()-1;
while(i<j){
if(ino[i]+ino[j]==k)return true;
else if(ino[i]+ino[j]<k)i++;
else j--;
}
return false;
}

Using Binary Search Iterator->

class BSTIterator {
public:
stack<TreeNode*>st;
bool reverse=true;
BSTIterator(TreeNode* root,bool rev) {
reverse=rev;
push(root);
}
void push(TreeNode* root){
while(root){
st.push(root);
if(reverse==false)root=root->left;
else root=root->right;
}
}
int next() {
TreeNode* temp=st.top();
st.pop();
if(!reverse)push(temp->right);
else push(temp->left);
return temp->val;
}

bool hasNext() {
return !st.empty();
}
};

class Solution {
public:
bool findTarget(TreeNode* root, int k) {
BSTIterator obj1(root,true);
BSTIterator obj2(root,false);
int val1=obj1.next();
int val2=obj2.next();
while(obj1.hasNext()&&obj2.hasNext()&&val1!=val2){
if(val1+val2==k)return true;
else if(val1+val2>k){
val1=obj1.next();
}
else val2=obj2.next();
}
return false;
}
};

15. Recover Binary Search Tree

class Solution {
public:
TreeNode*pre,*first,*middle,*last;
void inorder(TreeNode* root){
if(root==NULL)return;
inorder(root->left);
if(root->val<pre->val){
if(first==NULL){
first=pre;
middle=root;
}
else last=root;
}
pre=root;
inorder(root->right);
}
void recoverTree(TreeNode* root) {
first=NULL;
middle=NULL;
last=NULL;
pre=new TreeNode(INT_MIN);
 inorder(root);
if(last==NULL)swap(first->val,middle->val);
else swap(first->val,last->val);
}
};

16. Largest BST in Binary Tree

Use Post Order traversal for optimal approach->
Remaining to do
DP:-
1. Climbing Stars
2. Frog Jump(DP-3)
3. Dynamic Programming: Frog Jump with k Distances
4. Maximum sum of non-adjacent elements
5. House Robber (DP 6)
6. Ninja's Training (DP 7)
7. Grid Unique Paths : DP on Grids
8. Grid Unique Paths 2
9. Minimum Path Sum In a Grid
10. Minimum path sum in Triangular Grid
11. Minimum/Maximum Falling Path Sum
12. 3-d DP : Ninja and his friends
13. Subset Sum Equal To K
14. Partition Equal Subset Sum
15. Partition Set Into 2 Subsets With Min Absolute Sum Diff
16. Count Subsets with Sum K
17. Count Partitions with Given Difference
18. 0/1 Knapsack (DP - 19)
19. Minimum Coins (DP - 20)
20. Target Sum (DP - 21)
21. Coin Change 2 (DP - 22)
22. Unbounded Knapsack (DP - 23)
23. Rod Cutting Problem | (DP - 24)
24. Longest Common Subsequence
25. Print Longest Common Subsequence
26. Longest Common Substring
27. Longest Palindromic Subsequence
28. Minimum insertions to make string palindrome
29. Minimum Insertions/Deletions to Convert String
30. Shortest Common Supersequence
31. Distinct Subsequences
32. Edit Distance
33. Wildcard Matching
34. Stock Buy and Sell
35. Buy and Sell Stock - II|(DP-36)
36. Buy and Sell Stocks III|(DP-37)
 37. Buy and Stock Sell IV |(DP-38)
38. Buy and Sell Stocks With Cooldown
39. Buy and Sell Stocks With Transaction Fees
40. Longest Increasing Subsequence
41. Printing Longest Increasing Subsequence
42. Longest Increasing Subsequence
43. Longest Divisible Subset
44. Longest String Chain
45. Longest Bitonic Subsequence
46. Number of Longest Increasing Subsequences
47. Matrix Chain Multiplication
48. Matrix Chain Multiplication | Tabulation Method
49. Minimum cost to cut the stick
50. Burst Balloons
51. Evaluate Boolean Expression to True
52. Palindrome Partitioning – II | Front Partition
53. Partition Array for Maximum Sum | Front Partition
54. Maximum Rectangle Area with all 1’s | DP on Rectangles
55. Count Square Submatrices with All 1s | DP on Rectangles

Strings:-
1. Minimum Add to Make Parentheses Valid
2. Count and say
3. Hashing In Strings | Theory
4. Rabin Karp
5. Z-Function
6. KMP algo / LPS(pi) array
7. Shortest Palindrome
8. Longest happy prefix
9. Count palindromic subsequence

Graphs:-

Total degree =2* E

To find the total number of "undirected" graphs by N vertices
// can be acheived by 2^(N(N-1)/2);

1. Counting Graphs

2. Graph Representation in C++

3. Find the Number of Provinces
void bfs(int i,vector<vector<int>>&roads,vector<int>&vis){
vis[i]=1;
 for(int j=0;j<roads[i].size();j++){
if(i!=j&&roads[i][j]==1&&vis[j]==0){
bfs(j,roads,vis);
}
}
}
int findNumOfProvinces(vector<vector<int>>& roads, int n) {
// Write your code here.
int counti=0;
vector<int>vis(n,0);
for(int i=0;i<n;i++){
if (!vis[i]) {
bfs(i,roads, vis);
counti++;
}
}
return counti;
}

4. BFS in Graph
First make it visited before Putting it in queue.

vector<int> bfsOfGraph(int V, vector<int> adj[]) {

// Code here
vector<int>ans;
vector<int>vis(V,0);
queue<int>q;
q.push(0);
vis[0]=1;
while(!q.empty()){
int node=q.front();
ans.push_back(node);
q.pop();
for(auto i:adj[node]){
if(!vis[i]){
vis[i]=1;
q.push(i);
}
}
}
return ans;
}
5. Depth First Search (DFS)

void dfs(int i,vector<int>&vis,vector<int>adj[],vector<int>&ans){

vis[i]=1;
ans.push_back(i);
for(auto node:adj[i]){
if(!vis[node])dfs(node,vis,adj,ans);
}
}
vector<int> dfsOfGraph(int V, vector<int> adj[]) {
// Code here
vector<int>ans;
vector<int>vis(V,0);
dfs(0,vis,adj,ans);
return ans;
}

6. Number of provinces (leetcode)

7. Find the Number of Provinces
8. Rotten Oranges
int orangesRotting(vector<vector<int>>& g) {
queue<pair<int,int>>q;
for(int i=0;i<g.size();i++){
for(int j=0;j<g[i].size();j++){
if(g[i][j]==2)q.push({i,j});
}
}
int ans=0;
while(!q.empty()){
int s=q.size();
bool flag=false;
for(int t=0;t<s;t++){
int i=q.front().first;
int j=q.front().second;
q.pop();
if(i>0&&g[i-1][j]==1){
flag=true;
g[i-1][j]=2;
q.push({i-1,j});
}
if(j>0&&g[i][j-1]==1){
flag=true;
 g[i][j-1]=2;
q.push({i,j-1});
}
if(i<g.size()-1&&g[i+1][j]==1){
flag=true;
g[i+1][j]=2;
q.push({i+1,j});
}
if(j<g[0].size()-1&&g[i][j+1]==1){
flag=true;
g[i][j+1]=2;
q.push({i,j+1});
}
}
if(flag)ans++;
}
for(int i=0;i<g.size();i++){
for(int j=0;j<g[i].size();j++){
if(g[i][j]==1)return -1;
}
}
return ans;
}

9. Flood fill
Both are correct-> “Jb bhi queue mai daalo usse phle color kro” OR “Jb bhi queue se
pop kro tb color kro”

“Jb bhi queue mai daalo usse phle color kro”

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int

color) {
if(color==image[sr][sc])return image;
queue<pair<int,int>>q;
q.push({sr,sc});
int startingcolor=image[sr][sc];
image[sr][sc]=color;
while(!q.empty()){
int s=q.size();
for(int temp=0;temp<s;temp++){
int i=q.front().first;
int j=q.front().second;
q.pop();
 if(i>0&&image[i-1][j]==startingcolor){
image[i-1][j]=color;
q.push({i-1,j});
}
if(j>0&&image[i][j-1]==startingcolor){
image[i][j-1]=color;
q.push({i,j-1});
}
if(i<image.size()-1&&image[i+1][j]==startingcolor){
image[i+1][j]=color;
q.push({i+1,j});
}
if(j<image[0].size()-1&&image[i][j+1]==startingcolor){
image[i][j+1]=color;
q.push({i,j+1});
}

}
}
return image;
}

“Jb bhi queue se pop kro tb color kro”

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int
color) {
if(color==image[sr][sc])return image;
queue<pair<int,int>>q;
q.push({sr,sc});
int startingcolor=image[sr][sc];
while(!q.empty()){
int s=q.size();
for(int temp=0;temp<s;temp++){
int i=q.front().first;
int j=q.front().second;
image[i][j]=color;
q.pop();
if(i>0&&image[i-1][j]==startingcolor){
q.push({i-1,j});
}
if(j>0&&image[i][j-1]==startingcolor){
q.push({i,j-1});
}
 if(i<image.size()-1&&image[i+1][j]==startingcolor){
q.push({i+1,j});
}
if(j<image[0].size()-1&&image[i][j+1]==startingcolor){
q.push({i,j+1});
}

}
}
return image;
}

10. Detect Cycle in an Undirected Graph(using bfs)

If someone is visited and it did not come from it then there is a cycle in simpel
terms a node is visited but it is not equal to the parent node then there is a cycle.

bool bfs(int start,vector<int>adj[],vector<int>&vis){

queue<pair<int,int>>q;
q.push({start,-1});
vis[start]=1;
while(!q.empty()){
int node=q.front().first;
int camefrom=q.front().second;
q.pop();
for(auto i:adj[node]){
if (!vis[i]) {
q.push({i,node});
vis[i]=1;
} else if (i != camefrom) {
return true;
}
}
}
return false;
}
bool detectCycle(int V, vector<int> adj[]) {
// Write your code here.
vector<int>vis(V,0);
for(int i=0;i<V;i++){
if(!vis[i]&&bfs(i,adj,vis))return true;
}
 return false;
}

11. Detect Cycle in an Undirected Graph (using DFS)

If someone is visited and it did not come from it then there is a cycle in simpel
terms a node is visited but it is not equal to the parent node then there is a cycle.
bool dfs(int i,int camefrom,vector<int>&vis,vector<int>adj[]){
vis[i]=1;
for(auto node:adj[i]){
if (!vis[node]) {
if(dfs(node, i, vis, adj)) return true;
}
else if (node != camefrom)return true;
}
return false;
}
bool detectCycle(int V, vector<int> adj[]) {
vector<int>vis(V,0);
for(int i=0;i<V;i++){
if(!vis[i]&&dfs(i,-1,vis,adj))return true;
}
return false;
}

12. Distance Of Nearest Cell Having 0 In A Binary Matrix

This is giving TLE because I am doing bfs for each cell->
int bfs(int i,int j,vector<vector<int>>vis,vector<vector<int>>&mat){
int ans=INT_MAX;
queue<pair<pair<int,int>,int>>q;
q.push({{i,j},0});
while(!q.empty()){
int s=q.size();
for(int temp=0;temp<s;temp++){
int row=q.front().first.first;
int col=q.front().first.second;
vis[row][col]=1;
int tempans=q.front().second;
q.pop();
if(mat[row][col]==0){
ans=min(ans,tempans);
continue;
 }

if(row>0&&!vis[row-1][col])q.push({{row-1,col},tempans+1});

if(col>0&&!vis[row][col-1])q.push({{row,col-1},tempans+1});

if(row<mat.size()-1&&!vis[row+1][col])q.push({{row+1,col},tempans+1});

if(col<mat[0].size()-1&&!vis[row][col+1])q.push({{row,col+1},tempans+1})
;
}
}
return ans;
}
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
vector<vector<int>>vis(mat.size(),vector<int>(mat[0].size(),0));
for(int i=0;i<mat.size();i++){
for(int j=0;j<mat[0].size();j++){
if(mat[i][j]!=0)mat[i][j]=bfs(i,j,vis,mat);
}
}
return mat;
}

Strivers approach to do in one BFS ->

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int n=mat.size();
int m=mat[0].size();
vector<vector<int>>vis(n,vector<int>(m,0));
vector<vector<int>>ans(n,vector<int>(m,0));
queue<pair<pair<int,int>,int>>q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]==0){
vis[i][j]=1;
q.push({{i,j},0});
}
}
}
while(!q.empty()){
int s=q.size();
 // for(int temp=0;temp<s;temp++){
//Note that this for loop using has not affecting the BFS, this is
because Nikalna to FRONT se hi hai na ab chahe sbko nikaal ke ek baar
mai daalo ya ek ek krke daalo by outer while loop the order remains same
and hence this for loop is not affecting anything.
int row=q.front().first.first;
int col=q.front().first.second;
int tempans=q.front().second;
q.pop();
if(!vis[row][col])ans[row][col]=tempans;
vis[row][col]=1;
if(row>0&&!vis[row-1][col])q.push({{row-1,col},tempans+1});

if(col>0&&!vis[row][col-1])q.push({{row,col-1},tempans+1});

if(row<mat.size()-1&&!vis[row+1][col])q.push({{row+1,col},tempans+1});

if(col<mat[0].size()-1&&!vis[row][col+1])q.push({{row,col+1},tempans+1})
;
}
// }
return ans;
}

A different way using the method jb queue mai daalu usse phle visit mark
kr->
vector < vector < int > > nearest(vector < vector < int >> & mat, int n, int m) {
// Write your code here.
vector<vector<int>>ans(n,vector<int>(m,0));
vector<vector<int>>vis(n,vector<int>(m,0));
queue<pair<pair<int,int>,int>>q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]==1){
q.push({{i,j},0});
vis[i][j]=1;
}
}
}
while(!q.empty()){
 int i=q.front().first.first;
int j=q.front().first.second;
int tempans=q.front().second;
q.pop();
ans[i][j]=tempans;
if(i>0&&!vis[i-1][j]){
vis[i-1][j]=1;
q.push({{i - 1, j}, tempans + 1});
}
if(j>0&&!vis[i][j-1]){
vis[i][j-1]=1;
q.push({{i, j - 1}, tempans + 1});
}
if(i<n-1&&!vis[i+1][j]){
vis[i+1][j]=1;
q.push({{i + 1, j}, tempans + 1});
}
if(j<m-1&&!vis[i][j+1]){
vis[i][j+1]=1;
q.push({{i, j + 1}, tempans + 1});
}
}
return ans;
}

13. Surrounded Regions | Replace O’s with X’s

void dfs(int i,int j,vector<vector<char>>&board,vector<vector<int>>&vis){
vis[i][j]=1;
if(i>0&&!vis[i-1][j]&&board[i-1][j]=='O')dfs(i-1,j,board,vis);
if(j>0&&!vis[i][j-1]&&board[i][j-1]=='O')dfs(i,j-1,board,vis);

if(i<board.size()-1&&!vis[i+1][j]&&board[i+1][j]=='O')dfs(i+1,j,board,vis);

if(j<board[0].size()-1&&!vis[i][j+1]&&board[i][j+1]=='O')dfs(i,j+1,board,vis);
}
void solve(vector<vector<char>>& board) {
int m=board.size();
int n=board[0].size();
vector<vector<int>>vis(m,vector<int>(n,0));
 for(int i=0;i<m;i++){
if(!vis[i][0]&&board[i][0]=='O')dfs(i,0,board,vis);
if(!vis[i][n-1]&&board[i][n-1]=='O')dfs(i,n-1,board,vis);
}
for(int j=0;j<n;j++){
if(!vis[0][j]&&board[0][j]=='O')dfs(0,j,board,vis);
if(!vis[m-1][j]&&board[m-1][j]=='O')dfs(m-1,j,board,vis);
}
int counti=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j]=='O'&&!vis[i][j])board[i][j]='X';
}
}
}

14. Number of Enclaves

Similar to above problem->
void dfs(int i,int j,vector<vector<int>>&vis,vector<vector<int>>&grid){
vis[i][j]=1;
if(i>0&&!vis[i-1][j]&&grid[i-1][j]==1)dfs(i-1,j,vis,grid);
if(j>0&&!vis[i][j-1]&&grid[i][j-1]==1)dfs(i,j-1,vis,grid);
if(i<grid.size()-1&&!vis[i+1][j]&&grid[i+1][j]==1)dfs(i+1,j,vis,grid);

if(j<grid[0].size()-1&&!vis[i][j+1]&&grid[i][j+1]==1)dfs(i,j+1,vis,grid);
}
int numEnclaves(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
vector<vector<int>>vis(m,vector<int>(n,0));
for(int i=0;i<m;i++){
if(!vis[i][0]&&grid[i][0]==1)dfs(i,0,vis,grid);
if(!vis[i][n-1]&&grid[i][n-1]==1)dfs(i,n-1,vis,grid);
}
for(int j=0;j<n;j++){
if(!vis[0][j]&&grid[0][j]==1)dfs(0,j,vis,grid);
if(!vis[m-1][j]&&grid[m-1][j]==1)dfs(m-1,j,vis,grid);
}
int ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1&&!vis[i][j])ans++;
 }
}
return ans;
}
I can also use BFS in the above problems.
15. Word ladder - 1
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
set<string>us(wordList.begin(),wordList.end());
queue<pair<string,int>>q;
q.push({beginWord,1});
while(!q.empty()){
auto p=q.front();
string s=p.first;
int number=p.second;
if(s==endWord)return number;

q.pop();
for(int i=0;i<s.size();i++){
for(char c='a';c<='z';c++){
string temps=s;
temps[i]=c;
if(us.find(temps)!=us.end()){
q.push({temps,number+1});
us.erase(temps);
}
}
}
}
return 0;
}

16. Word ladder - 2

vector<vector<string>> findLadders(string beginWord, string endWord,
vector<string>& wordList) {
vector<vector<string>>ans;
set<string>us(wordList.begin(),wordList.end());
queue<vector<string>>q;
q.push({beginWord});
vector<string>used={beginWord};
while(!q.empty()){
for(auto str:used)us.erase(str);
int si=q.size();
 for(int i=0;i<si;i++){
vector<string>temp1=q.front();
q.pop();
string word=temp1.back();
if(word==endWord){
ans.push_back(temp1);
continue;
}
for(int j=0;j<word.size();j++){
for(char c='a';c<='z';c++){
string canmake=word;
canmake[j]=c;
if(us.find(canmake)!=us.end()){
temp1.push_back(canmake);
q.push(temp1);
used.push_back(canmake);
temp1.pop_back();
}
}
}
}
}
return ans;
}

17. Number of Islands/ Distinct Islands

#include<bits/stdc++.h>
void dfs(int i,int j,int **arr,int n,int m,vector<pair<int,int>>&temp,vector<vector<int>>&vis,int
baserow,int basecol){
vis[i][j]=1;
temp.push_back({i-baserow,j-basecol});//This will make it to store unique pairs in temp
if(i>0&&arr[i-1][j]==1&&!vis[i-1][j]&&arr[i-1][j]==1)dfs(i-1,j,arr,n,m,temp,vis,baserow,basecol);
if(j>0&&arr[i][j-1]==1&&!vis[i][j-1]&&arr[i][j-1]==1)dfs(i,j-1,arr,n,m,temp,vis,baserow,basecol);
if(i<n-1&&arr[i+1][j]==1&&!vis[i+1][j]&&arr[i+1][j]==1)dfs(i+1,j,arr,n,m,temp,vis,baserow,basecol);
if(j<m-1&&arr[i][j+1]==1&&!vis[i][j+1]&&arr[i][j+1]==1)dfs(i,j+1,arr,n,m,temp,vis,baserow,basecol);
}
int distinctIslands(int** arr, int n, int m)
{
//Write your code here
set<vector<pair<int,int>>>us;
vector<vector<int>>vis(n,vector<int>(m,0));
 for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if (!vis[i][j] && arr[i][j] == 1) {
vector<pair<int,int>>temp;
dfs(i, j, arr, n, m, temp, vis,i,j);
us.insert(temp);
}
}
}
return us.size();
}

18. Bipartite Graph (DFS)

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that
every edge in the graph connects a node in set A and a node in set B.
First Observation->
In simple words a graph is called a bipartite graph if it can be colored with exactly two colors such
that no two adjacent nodes have same colors.
This approach is giving TLE->
bool safe(int i,vector<vector<int>>&graph,vector<int>&color,int col){
for(auto node:graph[i]){
if(color[node]==col)return false;
}
return true;
}
bool f(int i,vector<vector<int>>&graph,vector<int>&color){
if(i>graph.size()-1)return true;
if(safe(i,graph,color,1)){
color[i]=1;
if(f(i+1,graph,color))return true;
color[i]=0;
}
if(safe(i,graph,color,2)){
color[i]=2;
if(f(i+1,graph,color))return true;
color[i]=0;
}
return false;
}
bool isBipartite(vector<vector<int>>& graph) {
vector<int>color(graph.size(),0);
bool ans=true;
for(int i=0;i<graph.size();i++){
 if(color[i]==0)ans&=f(i,graph,color);
}
return ans;
}

Second Observation->
If a graph has an odd length cycle then it’s not a bipartite graph.
Or simply run a dfs and if the new node is already colored with the same color then return false;

bool dfs(int i,int col,vector<int>&color,vector<vector<int>>&graph){

color[i]=col;
for(auto node:graph[i]){
if(color[node]==-1){
if(dfs(node,!col,color,graph)==false)return false;
}
else if(color[node]==col)return false;
}
return true;

}
bool isBipartite(vector<vector<int>>& graph) {
vector<int>color(graph.size(),-1);
for(int i=0;i<graph.size();i++){
if(color[i]==-1){
if(dfs(i,0,color,graph)==false)return false;
}
}
return true;
}

19. Detect Cycle in a Directed Graph

Use two vectors for visited and path visited(visited for corresponding path-> must
unchange it after dfs call)
If visited and pathvisited then return true else return false;
bool dfs(int i, vector<int>adj[],vector<int>&vis,vector<int>&pathvis){
vis[i]=1;
pathvis[i]=1;
for(auto node:adj[i]){
if(!vis[node]){
if(dfs(node,adj,vis,pathvis)==true)return true;
}
else if(pathvis[node])return true;
 }
pathvis[i]=0;
return false;
}
bool isCyclic(vector<vector<int>>& edges, int v, int e)
{
vector<int>vis(v,0);
vector<int>pathvis(v,0);
vector<int>adj[v];
for(auto i:edges){
adj[i[0]].push_back(i[1]);
}
for(int i=0;i<v;i++){
if(!vis[i]){
if(dfs(i,adj,vis,pathvis)==true)return true;
}
}
return false;
// Write your code here
}

20. Topo Sort->ONLY VALID FOR DAG(DIRECTED ACYCLIC GRAPH)

linear ordering of vertices such that for every directed edge u-v, vertex u comes before v

Maintain a stack and put into the stack when you go back.

USING DFS->
#include<stack>
void dfs(int i,vector<int>&vis,vector<int>adj[],stack<int>&st){
vis[i]=1;
for(auto node:adj[i]){
if(!vis[node])dfs(node,vis,adj,st);
}
st.push(i);
}
vector<int> topologicalSort(vector<vector<int>> &graph, int edges, int nodes) {
// Write your code here!
 vector<int>adj[nodes];
for(auto i:graph){
adj[i[0]].push_back(i[1]);
}
stack<int>st;
vector<int>vis(nodes,0);
for(int i=0;i<nodes;i++){
if(!vis[i])dfs(i,vis,adj,st);
}
vector<int>ans;
while(!st.empty()){
ans.push_back(st.top());
st.pop();
}
return ans;
}

21. Kahn's Algorithm-> SAME AS TOPO SORT BUT USING BFS WITH INDEGREE
QUEUE->
#include<queue>
vector<int> topologicalSort(vector<vector<int>> &graph, int edges, int nodes) {
// Write your code here!
vector<int>adj[nodes];
for(auto i:graph){
adj[i[0]].push_back(i[1]);
}

vector<int>indegree(nodes,0);
for(int i=0;i<nodes;i++){
for(auto node:adj[i])indegree[node]++;
}
vector<int>ans;
queue<int>q;
for(int i=0;i<nodes;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
ans.push_back(node);
 for (auto it : adj[node]) {
indegree[it]--;
if (indegree[it] == 0)
q.push(it);
}
}
return ans;
}

22. Detect Cycle In A Directed Graph

If topo sort has N elements then there is no cycle else there is cycle.

#include<queue>
int detectCycleInDirectedGraph(int nodes, vector < pair < int, int >> & edges) {
vector<int>adj[nodes+1];
for(auto i:edges){
adj[i.first].push_back(i.second);
}

vector<int>indegree(nodes+1,0);
for(int i=0;i<nodes+1;i++){
for(auto node:adj[i])indegree[node]++;
}
int counti=0;
queue<int>q;
for(int i=0;i<nodes+1;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
counti++;
for (auto it : adj[node]) {
indegree[it]--;
if (indegree[it] == 0)
q.push(it);
}
 }
if(counti==nodes+1)return 0;
return 1;
}

23. Course Schedule I

bool canFinish(int nodes, vector<vector<int>>& edges) {
vector<int>adj[nodes];
for(auto i:edges){
adj[i[1]].push_back(i[0]);
}

vector<int>indegree(nodes,0);
for(int i=0;i<nodes;i++){
for(auto node:adj[i])indegree[node]++;
}
int counti=0;
queue<int>q;
for(int i=0;i<nodes;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
counti++;
for (auto it : adj[node]) {
indegree[it]--;
if (indegree[it] == 0)
q.push(it);
}
}
if(counti==nodes)return true;
return false;
}

24. Course Schedule II

vector<int> findOrder(int nodes, vector<vector<int>>& edges) {
vector<int>adj[nodes];
for(auto i:edges){
adj[i[1]].push_back(i[0]);
}
 vector<int>indegree(nodes,0);
for(int i=0;i<nodes;i++){
for(auto node:adj[i])indegree[node]++;
}
vector<int>ans;
queue<int>q;
for(int i=0;i<nodes;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
ans.push_back(node);
for (auto it : adj[node]) {
indegree[it]--;
if (indegree[it] == 0)
q.push(it);
}
}
if(ans.size()==nodes)return ans;
return {};
}

25. Find eventual safe states

Using Topo sort->
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int n=graph.size();
vector<int>adj[n];
vector<int>indegree(n,0);

for(int i=0;i<n;i++){
for(auto it:graph[i]){
adj[it].push_back(i);
indegree[i]++;
}
}
queue<int>q;
for(int i=0;i<n;i++){
if(indegree[i]==0)q.push(i);
}
vector<int>ans;
while(!q.empty()){
 int node=q.front();
q.pop();
ans.push_back(node);
for(auto i:adj[node]){
indegree[i]--;
if(indegree[i]==0)q.push(i);
}
}
sort(ans.begin(),ans.end());
return ans;
}

26. Alien dictionary

#include<bits/stdc++.h>
vector<int> topo(vector<int>adj[],int n){
vector<int>ans;
vector<int>indegree(n,0);
for(int i=0;i<n;i++){
for(auto temp:adj[i]){
indegree[temp]++;
}
}
queue<int>q;
for(int i=0;i<n;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
ans.push_back(node);
for(auto i:adj[node]){
indegree[i]--;
if(indegree[i]==0)q.push(i);
}
}
return ans;
}
string getAlienLanguage(vector<string> &dictionary, int k)
{
// Write your code here.
 vector<int>adj[k];
for(int i=0;i<dictionary.size()-1;i++){
string s1=dictionary[i];
string s2=dictionary[i+1];
int len=min(s1.size(),s2.size());
for(int j=0;j<len;j++){
if(s1[j]!=s2[j]){
adj[s1[j]-'a'].push_back(s2[j]-'a');
break;
}
}
}
vector<int>ans=topo(adj,k);
string answer="";
for(auto i:ans){
answer+=char(i+'a');
}
return answer;
}

27. Single Source Shortest Path

vector<int> shortestPath(int n, vector<vector<int>>&edges, int src) {
// Write your code here.
vector<int>adj[n];
for(auto i:edges){
adj[i[0]].push_back(i[1]);
adj[i[1]].push_back(i[0]);
}
vector<int>dis(n,1e9);
dis[src]=0;
queue<int>q;
q.push(src);
while(!q.empty()){
int node=q.front();
q.pop();
for(auto it:adj[node]){
if (dis[node] + 1 < dis[it]) {
dis[it] = dis[node] + 1;
q.push(it);
}
 }
}
vector<int>ans;
for(auto i:dis){
if(i!=1e9)ans.push_back(i);
else ans.push_back(-1);
}

return ans;
}

28. Shortest Path in DAG

Use topo sort and then apply the distance finding logic.
Use of topo sort will reduce the time complexity as it ensures that all the previous guys
are already reached through which you can reach me.

void dfs(int i,vector<pair<int,int>>adj[],vector<int>&vis,stack<int>&st){

vis[i]=1;
for(auto node:adj[i]){
if(!vis[node.first])dfs(node.first,adj,vis,st);
}
st.push(i);
}
vector<int> shortestPathInDAG(int n, int m, vector<vector<int>> &edges)
{
// Write your code here
vector<pair<int,int>>adj[n];
for(auto i:edges){
adj[i[0]].push_back({i[1], i[2]});
}
stack<int>st;
vector<int>vis(n,0);
for(int i=0;i<n;i++){
if(!vis[i])dfs(i,adj,vis,st);
}
vector<int>dis(n,1e9);
dis[0]=0;//as starting from node 0
while(!st.empty()){
int node=st.top();
st.pop();
 for(auto i:adj[node]){
if(dis[node]+i.second<dis[i.first])dis[i.first]=dis[node]+i.second;
}
}
vector<int>ans;
for(auto i:dis){
if(i==1e9)ans.push_back(-1);
else ans.push_back(i);
}
return ans;
}

29. Djisktra's Algorithm

To just find out the distance->
#include<bits/stdc++.h>
using namespace std;
vector<int> dijkstra(vector<vector<int>> &edge, int v, int edges, int source)
{
vector<pair<int,int>>adj[v];
for(auto i:edge){
adj[i[0]].push_back({i[1], i[2]});
adj[i[1]].push_back({i[0], i[2]});
}
vector<int>dis(v,1e9);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({0,source});
dis[source]=0;
while(!pq.empty()){
auto p=pq.top();
pq.pop();
int d=p.first;
int node=p.second;
for(auto i:adj[node]){
int adjnode=i.first;
int adjdis=i.second;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
pq.push({dis[adjnode],adjnode});
 }
}
}
return dis;
}

To find out the source to destination path also->

If you want to find out the path then make a parent array in which store the parents of
each node and finally you can get path as given below->
GFG version->
vector<int> shortestPath(int n, int m, vector<vector<int>>& vec) {
// Code here
vector<pair<int,int>>adj[n+1];
for(auto i:vec){
adj[i[0]].push_back({i[1],i[2]});
adj[i[1]].push_back({i[0],i[2]});
}
vector<int>dis(n+1,1e9);
vector<int>parent(n+1);
for(int i=0;i<=n;i++)parent[i]=i;
dis[1]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({0,1});
while(!pq.empty()){
auto p=pq.top();
pq.pop();
int node=p.second;
int d=p.first;
for(auto i:adj[node]){
int adjdis=i.second;
int adjnode=i.first;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
pq.push({dis[adjnode],adjnode});
parent[adjnode]=node;
}
}
}
// return dis;
if(dis[n]==1e9)return {-1};
vector<int>ans;
int node=n;
while(parent[node]!=node){
ans.push_back(node);
node=parent[node];
}
 ans.push_back(1);
ans.push_back(dis[n]);
reverse(ans.begin(),ans.end());
return ans;
}

30. Dijkstra's shortest path

Using set->
#include<bits/stdc++.h>
using namespace std;
vector<int> dijkstra(vector<vector<int>> &edge, int v, int edges, int source)
{
vector<pair<int,int>>adj[v];
for(auto i:edge){
adj[i[0]].push_back({i[1], i[2]});
adj[i[1]].push_back({i[0], i[2]});
}
vector<int>dis(v,1e9);
set<pair<int,int>>us;
us.insert({0,source});
dis[source]=0;
while(us.size()>0){
auto p=*(us.begin());
us.erase(p);
int d=p.first;
int node=p.second;
for(auto i:adj[node]){
int adjnode=i.first;
int adjdis=i.second;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
us.insert({dis[adjnode],adjnode});
}
}
}
return dis;
}

31. Dijkstra’s Algorithm – Using Priority Queue

#include<bits/stdc++.h>
using namespace std;
vector<int> dijkstra(vector<vector<int>> &edge, int v, int edges, int source)
{
vector<pair<int,int>>adj[v];
for(auto i:edge){
adj[i[0]].push_back({i[1], i[2]});
adj[i[1]].push_back({i[0], i[2]});
}
vector<int>dis(v,1e9);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({0,source});
dis[source]=0;
while(!pq.empty()){
auto p=pq.top();
pq.pop();
int d=p.first;
int node=p.second;
for(auto i:adj[node]){
int adjnode=i.first;
int adjdis=i.second;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
pq.push({dis[adjnode],adjnode});
}
}
}
return dis;
}

32. Shortest Distance in a Binary Maze

Coding ninja version->

#include<bits/stdc++.h>
int shortestPathBinaryMatrix(vector<vector<int>> &matrix, pair<int, int> src, pair<int, int> dest)
{
// Write your code here
if(matrix[src.first][src.second]==0)return -1;
int n=matrix.size();
int m=matrix[0].size();
 vector<vector<int>>dis(n,vector<int>(m,1e9));
//
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>
pq;
//No need to use priority key as we are exploring, the distance is increasing by 1 only and not
randomly and hence in queue the distance will always lie in sorted order.
queue<pair<int,pair<int,int>>>pq;
pq.push({0,src});
dis[src.first][src.second]=0;
while(!pq.empty()){
auto p=pq.front();
pq.pop();
int d=p.first;
int r=p.second.first;
int c=p.second.second;
if(r>0&&matrix[r-1][c]==1&&dis[r-1][c]>d+1){
dis[r-1][c]=d+1;
pq.push({d+1,{r-1,c}});
}
if(c>0&&matrix[r][c-1]==1&&dis[r][c-1]>d+1){
dis[r][c-1]=d+1;
pq.push({d+1,{r,c-1}});
}
if(r<n-1&&matrix[r+1][c]==1&&dis[r+1][c]>d+1){
dis[r+1][c]=d+1;
pq.push({d+1,{r+1,c}});
}
if(c<m-1&&matrix[r][c+1]==1&&dis[r][c+1]>d+1){
dis[r][c+1]=d+1;
pq.push({d+1,{r,c+1}});
}
}
if(dis[dest.first][dest.second]==1e9)return -1;
return dis[dest.first][dest.second];
}

33. Shortest Distance in a Binary Maze-> Leetcode version

//To traverse in 8 directions in a matrix->
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int k = 0; k < 8; ++k) {
int x = i + dx[k];
int y = j + dy[k];
// Check if (x, y) is within bounds
if (x >= 0 && x < rows && y >= 0 && y < cols) {
cout << "Neighbor: " << x << ", " << y << " Value: " <<
matrix[x][y] << endl;
// Do whatever you want with the neighbor cell value
}
}

Using the above thing to solve this problem easily for leetcode version->
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n=grid.size();
if(grid[0][0]==1||grid[n-1][n-1]==1)return -1;
vector<vector<int>>dis(n,vector<int>(n,1e9));
queue<pair<int,pair<int,int>>>q;
dis[0][0]=1;
q.push({1,{0,0}});
while(!q.empty()){
auto p=q.front();
q.pop();
int d=p.first;
int i=p.second.first;
int j=p.second.second;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int k=0;k<8;++k){
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < n
&&grid[x][y]==0&&dis[x][y]>d+1) {
dis[x][y]=d+1;
q.push({d+1,{x,y}});
}
}
}
if(dis[n-1][n-1]==1e9)return -1;
return dis[n-1][n-1];
}
 34. Path with minimum effort->
Very interesting and very important twisted version of Dijkstra algorithm.
#include<bits/stdc++.h>
int minimumTimeTakingPath(vector<vector<int>> &heights)
{
int n=heights.size();
int m=heights[0].size();
vector<vector<int>>dis(n,vector<int>(m,1e9));
dis[0][0]=0;

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>
pq;
pq.push({0, {0, 0}});
int dr[] ={-1,0,1,0};
int dc[]={0,1,0,-1};
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int d = p.first;
int i = p.second.first;
int j = p.second.second;

for(int k=0;k<4;k++){
int r=i+dr[k];
int c=j+dc[k];
if(r>=0&&c>=0&&r<n&c<m){
int effort=max(d,abs(heights[i][j]-heights[r][c]));
if(effort<dis[r][c]){
dis[r][c]=effort;
pq.push({effort, {r, c}});
}
}
}
}
if(dis[n-1][m-1]==1e9)return -1;
return dis[n-1][m-1];
}
A twisted line to save time->
int minimumEffortPath(vector<vector<int>>& heights) {
int n=heights.size();
int m=heights[0].size();
vector<vector<int>>dis(n,vector<int>(m,1e9));
dis[0][0]=0;

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<
pair<int,pair<int,int>>>>pq;
pq.push({0, {0, 0}});
int dr[] ={-1,0,1,0};
int dc[]={0,1,0,-1};
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int d = p.first;
int i = p.second.first;
int j = p.second.second;
if(i==n-1&&j==m-1)return d;
for(int k=0;k<4;k++){
int r=i+dr[k];
int c=j+dc[k];
if(r>=0&&c>=0&&r<n&c<m){
int effort=max(d,abs(heights[i][j]-heights[r][c]));
if(effort<dis[r][c]){
dis[r][c]=effort;
pq.push({effort, {r, c}});
}
}
}
}
return -1;
}

35. Cheapest flights within k stops

Normal dijkstra can not be used as it will work by considering distance only and not the
steps and hence might choose wrong path by ignoring the larger distance.
So, the modified dijkstra will use steps as deciding factor in priority queue.
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,
int k) {
vector<pair<int,int>>adj[n];
for(auto i:flights){
 adj[i[0]].push_back({i[1],i[2]});
}
vector<int>dis(n,1e9);
queue<pair<int,pair<int,int>>>q;
dis[src]=0;
q.push({0,{src,0}});
while(!q.empty()){
auto p=q.front();
q.pop();
int steps=p.first;
if(steps>k)continue;
int node=p.second.first;
int d=p.second.second;
for(auto i:adj[node]){
int adjnode=i.first;
int adjdis=i.second;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
q.push({steps+1,{adjnode,dis[adjnode]}});
}
}
}
if(dis[dst]==1e9)return -1;
return dis[dst];
}

36. Network Delay time

In leetcode version->
Using n+1 because node numbering is starting from 1 but if you want the node
numbering from 0 so use source-1 in place of source.
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int source) {
vector<pair<int,int>>adj[n+1];
for(auto i:times){
adj[i[0]].push_back({i[1],i[2]});
}
vector<int>dis(n+1,INT_MAX);

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>
>q;
dis[source]=0;
q.push({0,source});
 while(!q.empty()){
auto p=q.top();
q.pop();
int node=p.second;
int d=p.first;
for(auto i:adj[node]){
int adjnode=i.first;
int adjdis=i.second;
if(d+adjdis<dis[adjnode]){
dis[adjnode]=d+adjdis;
q.push({dis[adjnode],adjnode});
}
}
}
int mx=*max_element(dis.begin()+1,dis.end());
return mx==INT_MAX?-1:mx;

}
};

37. Number Of Ways

int countPaths(int n, vector<vector<int>>& roads) {
vector<pair<ll,ll>>adj[n];
for(auto i:roads){
adj[i[0]].push_back({i[1],i[2]});
adj[i[1]].push_back({i[0],i[2]});
}
vector<ll>dis(n,LONG_MAX),ways(n,0);
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
dis[0]=0;
ways[0]=1;
pq.push({0,0});
int mod=(int)(1e9+7);
while(!pq.empty()){
auto p=pq.top();
pq.pop();
ll d=p.first;
ll node=p.second;
for(auto i:adj[node]){
ll adjnode=i.first;
ll adjdis=i.second;
if(d+adjdis<dis[adjnode]){
 dis[adjnode]=d+adjdis;
ways[adjnode]=ways[node];
pq.push({dis[adjnode],adjnode});

}
else if(d+adjdis==dis[adjnode]){
ways[adjnode]=(ways[adjnode]%mod+ways[node])%mod;
}
}
}
return ways[n-1]%mod;
}
Check why coding ninja version is giving wrong answer.

38. Number of Ways to Arrive at Destination

39. Minimum Multiplications to Reach End

#include<bits/stdc++.h>
int minimumOperations(int n, int start, int end, vector<int> &a)
{
// queue<pair<int,int>>q;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push({0,start});
vector<int>dis(1000,1e9);
dis[start]=0;
int mod=1000;
while(!q.empty()){
int node=q.top().second;
int steps=q.top().first;
q.pop();
if(node==end)return dis[node];
for(auto i:a){
int num=(i*node)%mod;
if(steps+1<dis[num]){
dis[num]=steps+1;
q.push({steps+1,num});
}
}
}
return -1;
}
 40. Bellman Ford Algorithm-> Single source shortest Path algorithm
Do n-1 iteration in Directed Graph.
If on nth iteration the relaxation is done and the distance array still got updated hence
there is a cycle with negative edge.
vector<int> bellmonFord(int n, int m, int src, vector<vector<int>> &edges) {
// Write your code here.
vector<int>dis(n+1,1e8);
dis[src]=0;
for(int i=0;i<n-1;i++){
for(auto edge:edges){
int u=edge[0];
int v=edge[1];
int w=edge[2];
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
}
}
}
return dis;
}

Now if you run for(auto) loop once again and the if condition is satisfied then it means
the directed graph has a cycle with negative edge.
41. Floyd Warshal Algorithm-> Multi source shortest path algorithm->

42. Find the City With the Smallest Number

43. of Neighbours at a Threshold Distance
44. Minimum Spanning Tree
Spanning Tree->
Have N nodes, N-1 edges and all the nodes are connected with eachother.
MST-> ST with min sum
45. Prim's Algorithm
#include<bits/stdc++.h>
int minimumSpanningTree(vector<vector<int>>& edges, int n)
{
vector<pair<int,int>>adj[n];
for(auto i:edges){
adj[i[0]].push_back({i[1],i[2]});
adj[i[1]].push_back({i[0],i[2]});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,0});
int sum=0;
vector<int>vis(n,0);
while(!pq.empty()){
int wt=pq.top().first;
int node=pq.top().second;
pq.pop();
if(vis[node]==1)continue;
sum+=wt;
vis[node]=1;
for(auto i:adj[node]){
if(!vis[i.first]){
pq.push({i.second,i.first});
}
}
}
return sum;
}

46. Disjoint Set [Union by Rank]

47. Disjoint Set [Union by Size]
48. Kruskal's Algorithm
49. Number of Operations to Make Network Connected
50. Most Stones Removed with Same Row or Column
51. Accounts merge
52. Number of island II
53. Making a Large Island
54. Swim in rising water
55. Bridges in Graph
56. Articulation Point
57. Kosaraju's Algorithm

Tries:-
1. Trie Implementation
2. Implement Trie - 2 (Prefix Tree)
3. Number of Distinct Substrings in a String Using Trie
4. Bitwise Basic Operations
5. Maximum XOR of Two Numbers in an Array
6. Maximum Xor Queries | Trie
Extra questions other than sheet->