class Solution {

public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int,int>> a;
for(int i=0;i<nums.size();i++)
{
a.push_back({nums[i],i});
}
sort(a.begin(),a.end());
int s=0,e=nums.size()-1;
while(s<e)
{
if(a[s].first+a[e].first==target)
return {a[s].second,a[e].second};
else if(a[s].first+a[e].first>target)
e--;
else
s++;
}
return {-1,-1};

}
};

--------------------------------------------------------
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minpri=INT_MAX;
int prof=0;

for(int i=0;i<prices.size();i++)
{
minpri=min(prices[i],minpri);
prof=max(prof,prices[i]-minpri);

}
return prof;

}
};

------------------------------------------------------------------------------

class Solution {
public:
 vector<int> plusOne(vector<int>& digits) {

for(int i=digits.size()-1;i>=0;i--)
{
if(digits[i]<9)
{
digits[i]++;
return digits;
}
else
{
digits[i]=0;
}
}

digits.push_back(0);
digits[0]=1;

return digits;

}
};

class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i=0;

for(int j=0;j<nums.size();j++)
{
if(nums[j]!=0)
{
nums[i]=nums[j];
i++;
}
}
while(i<nums.size())
{
nums[i]=0;
i++;
}

}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int pro=0;
for(int i=1;i<prices.size();i++)
{
if(prices[i]>prices[i-1])
pro+=(prices[i]-prices[i-1]);
}
return pro;
}
};

class Solution {
public:
vector<int> runningSum(vector<int>& nums) {

vector<int> ans;
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
ans.push_back(sum);

}
return ans;

}
};

class Solution {
public:
int fib(int n) {
if(n<=1)
return n;
int a=0;
int b=1;
int sum=0;
for(int i=2;i<=n;i++)
{
sum=a+b;
a=b;
b=sum;
 }
return b;

}
};

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans(numRows);
for(int i=0;i<numRows;i++)
{
ans[i].resize(i+1);
ans[i][0]=1;
ans[i][i]=1;

for(int pos=1;pos<i;pos++)
{
ans[i][pos]=ans[i-1][pos]+ans[i-1][pos-1];
}
}
return ans;

}
};

class Solution {
public:
int majorityElement(vector<int>& nums) {
int item=nums[0];
int count=0;
for(auto x:nums)
{
if(count==0)
item=x;
if(x==item)
count++;
else
count--;
}

return item;

}
};
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<=1)
return intervals;

sort(intervals.begin(),intervals.end());
vector<vector<int>> output;

output.push_back(intervals[0]);

for(int i=1;i<intervals.size();i++)
{
if(output.back()[1]>=intervals[i][0])
output.back()[1]=max(output.back()[1],intervals[i][1]);
else
output.push_back(intervals[i]);
}

return output;

}
};

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j !=
k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>>set;
int n=nums.size();
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i=0;i<n-2;i++)
{
int l=i+1,r=n-1;
while(l<r)
{
if(nums[i]+nums[l]+nums[r]==0)
{
 set.insert({nums[i],nums[l],nums[r]});
l++;
r--;
}
else if(nums[i]+nums[l]+nums[r]>0)
r--;
else
l++;

}
}

for(auto x:set)
{
ans.push_back(x);
}
return ans;

}
};

Given an array arr[] of N integers, the task is to count number of triplets (i, j, k) in the array such
that a[k] < a[i] < a[j] and i < j < k.

int CountTriplets(int a[], int n)

{

// To store count of total triplets

int ans = 0;

for (int i = 0; i < n; i++) {

// Initialize count to zero

int cnt = 0;

for (int j = i + 1; j < n; j++) {

// If a[j] > a[i] then,

// increment cnt
if (a[j] > a[i])
cnt++;

// If a[j] < a[i], then

// it mean we have found a[k]
// such that a[k] < a[i] < a[j]
 else
ans += cnt;
}

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> left(n);
left[0]=1;
for(int i=1;i<n;i++)
{
left[i]=left[i-1]*nums[i-1];
}
int r=1;
for(int i=n-1;i>=0;i--)
{
left[i]=left[i]*r;
r=r*nums[i];
}
return left;

}
};

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {

unordered_map<int,int> map;
int c=0;
int sum=0;
int n=nums.size();
int i=0;
while(i<n)
{
sum+=nums[i];
if(sum==k)
c++;
if(map.find(sum-k)!=map.end())
c+=map[sum-k];
map[sum]+=1;
i++;
}
 return c;

}
};

class Solution {
public:
void nextPermutation(vector<int>& nums) {

int idx=-1;
int n=nums.size();
for(int i=n-1;i>0;i--)
{
if(nums[i]>nums[i-1])
{
idx=i;
break;

}
if(idx==-1)
{
return reverse(nums.begin(),nums.end());
}
else
{
int prev=idx;
for(int i=idx+1;i<n;i++)
{
if(nums[i]>nums[idx-1] && nums[i]<=nums[prev])
{
prev=i;
}
}
swap(nums[prev],nums[idx-1]);
reverse(nums.begin()+idx,nums.end());
}

}
};

class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int t=0,b=matrix.size()-1;
int l=0,r=matrix[0].size()-1;
vector<int>ans;
int dir=0;

while(t<=b && l<=r)

{
if(dir==0)
{
for(int i=l;i<=r;i++)
{
ans.push_back(matrix[t][i]);

}
t++;

}
else if(dir==1)
{
for(int i=t;i<=b;i++)
{
ans.push_back(matrix[i][r]);

}
r--;

}
else if(dir==2)
{
for(int i=r;i>=l;i--)
{
ans.push_back(matrix[b][i]);

}
b--;

}
else if(dir==3)
{
for(int i=b;i>=t;i--)
{
ans.push_back(matrix[i][l]);

}
l++;

}
 dir=(dir+1)%4;
}

return ans;

}
};

class Solution {
public:
void rotate(vector<vector<int>>& matrix) {

int r=matrix.size();
int c=matrix[0].size();

for(int i=0;i<r;i++)
{
for(int j=0;j<i;j++)
{
swap(matrix[i][j],matrix[j][i]);
}
}

for(int i=0;i<r;i++)
reverse(matrix[i].begin(),matrix[i].end());

}
};

class Solution {
public:
bool safe(int i, int j, int r, int c) {
return (i >= 0 && i < r && j >= 0 && j < c);
}

void gameOfLife(vector<vector<int>>& board) {

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {0, -1, 1, -1, 1, -1, 0, 1};
 int r = board.size();
int c = board[0].size();

for (int i = 0; i < r; ++i) {

for (int j = 0; j < c; ++j) {
int count = 0;
for (int k = 0; k < 8; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (safe(ni, nj, r, c) && (board[ni][nj] == 1 || board[ni][nj] ==
3)) {
++count;
}
}
if (board[i][j] == 0 && count == 3) {
board[i][j] = 2; // Dead to live
} else if (board[i][j] == 1 && (count < 2 || count > 3)) {
board[i][j] = 3; // Live to dead
}
}
}

for (int i = 0; i < r; ++i) {

for (int j = 0; j < c; ++j) {
if (board[i][j] == 2) {
board[i][j] = 1; // 2 signifies the cell is now alive
} else if (board[i][j] == 3) {
board[i][j] = 0; // 3 signifies the cell is now dead
}
}
}
}
};

class Solution {
public:

class Solution {
public:
bool safe(int r, int c, int i, int j) {
return !(i < 0 || j < 0 || i >= r || j >= c);
}
 bool solve(vector<vector<char>>& board, int i, int j, int r, int c, string &word,
int idx) {

if (idx == word.size())
{
return true;
}

if (!safe(r, c, i, j) || board[i][j] != word[idx]) return false;

char temp = board[i][j];

board[i][j] = '#';

bool found = solve(board, i, j + 1, r, c, word, idx + 1) ||

solve(board, i + 1, j, r, c, word, idx + 1) ||
solve(board, i - 1, j, r, c, word, idx + 1) ||
solve(board, i, j - 1, r, c, word, idx + 1);

board[i][j] = temp;

return found;
}

bool exist(vector<vector<char>>& board, string word) {

int r = board.size(), c = board[0].size();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (board[i][j] == word[0] && solve(board, i, j, r, c, word, 0))
return true;
 }
}
return false;
}
};

Input: nums = [-1,2,1,-4], target = 1

Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int min=INT_MAX;
int ans=0;
sort(nums.begin(),nums.end());

for(int i=0;i<nums.size()-2;i++)
{
int sum=0;
int j=i+1,k=nums.size()-1;
while(j<k)
{
sum=nums[i]+nums[j]+nums[k];
if(sum==target)
{
return sum;
}
else if(sum>target)
k--;
else
j++;

if(abs(sum-target)<min)
{
ans=sum;
min=abs(sum-target);
}
}

}
 return ans;

}
};

class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
int r=0;
for(int i=0;i<n;i++)
{
if(r<i)
return false;

r=max(r,i+nums[i]);
}
return true;

}
};

class Solution {
public:
int findDuplicate(vector<int>& nums) {

int slow = nums[0];

int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

fast = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;

}
};

class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
vector<int> left(n);
vector<int> right(n);
left[0]=0;
right[n-1]=0;
int lmax=height[0];
int rmax=height[n-1];
int ans=0;
for(int i=1;i<n;i++)
{
left[i]=lmax;
lmax=max(lmax,height[i]);

}
for(int i=n-2;i>0;i--)
{
right[i]=rmax;
rmax=max(rmax,height[i]);
}
for(int i=1;i<n-1;i++)
{
if(height[i]<left[i] && height[i]<right[i])
ans=ans+min(left[i],right[i])-height[i];
}

return ans;

}
};

class Solution {
public:
int dfs(vector<vector<int>> &grid,int i,int j)
{
int r=grid.size();
int c=grid[0].size();
if(i<0 || i>=r || j<0 || j>=c || grid[i][j]!=1)
return 0;
grid[i][j]=0;
return 1+dfs(grid,i+1,j)+dfs(grid,i,j+1)+dfs(grid,i-1,j)+dfs(grid,i,j-1);

}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int r=grid.size();
int c=grid[0].size();
 int ans=0;

for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(grid[i][j]==1)
ans=max(ans,dfs(grid,i,j));

}
}
return ans;

}
};

class Solution {
public:
int findPairs(vector<int>& nums, int k) {
unordered_map<int,int> map;
int ans=0;
for(int i=0;i<nums.size();i++)
{
map[nums[i]]++;
}
for(auto it=map.begin();it!=map.end();it++)
{
if((k==0 && it->second>1) || (k>0 && map.find(it->first+k)!=map.end()))
ans++;

}
return ans;

}
};

class Solution {
public:
int reverse(int x) {
long r=0;
int temp=x;
while(temp)
{
r=r*10+temp%10;
temp=temp/10;
}
 if(r>INT_MAX || r<INT_MIN)
return 0;
return int(r);

}
};

class Solution {
public:
string addBinary(string a, string b) {
int n1=a.length()-1,n2=b.length()-1;
int c=0,base=2;
string ans="";

while(n1>=0 || n2>=0)
{
int sum=0;
if(n1>=0)
sum+=a[n1--]-'0';
if(n2>=0)
sum+=b[n2--]-'0';

sum+=c;
if(sum>=base)
{
c=1;
sum=sum-base;
}
else
{
c=0;
}
ans+=to_string(sum);

}
if(c==1)
ans+='1';

reverse(ans.begin(),ans.end());
return ans;

}
};
class Solution {
public:
bool isPalindrome(int x) {
if(x<0)
return false;

int temp=x;
int r=0;
while(temp)
{
r=r*10+temp%10;
temp=temp/10;
}
if(r==x)
return true;
else
return false;
}
};

class Solution {
public:
bool isHappy(int n) {
if(n==1)
return true;

int temp=n;
unordered_set<int> s;
while(1)
{
int val=0;
while(temp)
{
int t=temp%10;
val+=t*t;
temp=temp/10;
}
if(val==1)
return true;
if(s.find(val)!=s.end())
return false;

s.insert(val);
temp=val;
}

return false;
 }
};

--

class Solution {
public:
string convertToTitle(int columnNumber) {
string ans="";
int n=columnNumber;
while(n)
{
char a='A'+(n-1)%26;
ans=a+ans;
n=(n-1)/26;
}
return ans;

}
};

class Solution {
public:
int minMoves(vector<int>& nums) {
int min=INT_MAX;
int ans=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]<min)
min=nums[i];
}
for(int i=0;i<nums.size();i++)
{
ans+=nums[i]-min;
}
return ans;

}
};
class Solution {
public:
double angleClock(int hour, int minutes) {
 double ans=(double)(30*hour)-(double)(5.5*minutes);

if(ans>180.0 && ans<360.0)

return abs(360.0-ans);
else if(ans<0)
return abs(ans);

return ans;

}
};

class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0)
return false;

if(ceil(log2(n))==floor(log2(n)))
return true;
else
return false;

}
};

class Solution {
public:
int myAtoi(string s) {
//Check if the string is empty and return zero if yes.
if(s.size()==0)
return 0;
int i=0;
//Check for leading white spaces and if present ignore and hence i++
while(i<s.size()&& s[i]==' ')
{
i++;
}
//suppose the string contains only spaces and in this case return 0
if(i>=s.size())
return 0;
//trim the string to remove whitespaces using substr()
s=s.substr(i);//i--->s.length()-1
//check for + or - sign.
int sign= 1;
long ans =0;
 if(s[0]=='-')//if'-' sign then turn sign to -1
sign=-1;
i=(s[0]=='+'|| s[0]=='-')? 1:0;
while(i<s.size())
{
if(s[i]==' ' || !isdigit(s[i]))
break;
ans=ans*10+s[i]-'0';
if(sign==1 && ans>INT_MAX)
return INT_MAX;
if(sign==-1 && -1*ans<INT_MIN)
return INT_MIN;
i++;

}
return (int)sign*ans;
}
};

class Solution {
public:
string multiply(string num1, string num2) {
if(num1[0]=='0' || num2[0]==0)
return to_string(0);

int a1=0;
int l1=num1.length();
int i=0;
while(i<l1)
{
a1=a1*10+num1[i]-'0';
i++;
}

int a2=0;
int l2=num2.length();
int j=0;
while(j<l2)
{
a2=a2*10+num2[j]-'0';
j++;
}
int c=a1*a2;
return to_string(c);

}
};
class Solution {
public:

class Solution {
public:
vector<int> dp;

Solution() {
dp = vector<int>(59, 0);
}

int integerBreak(int n) {

if (n == 2)
return 1;

if (dp[n] != 0)
return dp[n];

int ans = 0;

for (int i = 1; i < n; i++) {

int prod = i * max(n - i, integerBreak(n - i));
ans = max(ans, prod);
}

dp[n] = ans;
return dp[n];
}
};
class Solution {
public:
int sideSquare(vector<int>& a, vector<int>& b) {

int side=0;
side=((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]));

return side;
}

bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

vector<int> sides;

sides.push_back(sideSquare(p1, p2));
sides.push_back(sideSquare(p2, p3));
sides.push_back(sideSquare(p3, p4));
sides.push_back(sideSquare(p4, p1));
sides.push_back(sideSquare(p1, p3));
sides.push_back(sideSquare(p2, p4));

sort(sides.begin(), sides.end());

return (sides[0]>0 && sides[0]==sides[3] && sides[4]==sides[5]);

}
};

class Solution {
public:
int kthFactor(int n, int k) {

for(int i=1;i<sqrt(n);i++)
{
if(n%i==0)
{
k--;

}
if(k==0)
return i;
}
for(int i=sqrt(n);i>=1;i--)
{
if(n%i==0)
{
k--;
 if(k==0)
return n/i;
}
}
return -1;

}
};

class Solution {
public:
double myPow(double x, int n) {
if(n<0)
{x=1/x;
n=abs(n);}
if(n==0)
return 1;
if(n%2==0)
return myPow(x*x,n/2);
else
return x*myPow(x*x,(n-1)/2);}

};

class Solution {
public:
int romanToInt(string s) {
int ans=0;
unordered_map <char,int> mp{
{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};

for(int i=0;i<s.size();i++){
if(mp[s[i]]<mp[s[i+1]]){
//for cases such as IV,CM, XL, etc...
ans=ans-mp[s[i]];
}
else{
ans=ans+mp[s[i]];
}
}
return ans;
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
sort(strs.begin(), strs.end());
if (strs.size() == 1) {
return strs[0];
}
if (strs[0] == strs[strs.size() - 1]) {
return strs[0];
}
for (int i = 0; i < strs[0].length(); i++) {
if (strs[strs.size() - 1][i] != strs[0][i]) {
return strs[0].substr(0, i);
}
}
return strs[0];
}
};

class Solution {
public:
string addStrings(string num1, string num2) {
int i=num1.length()-1;
int j=num2.length()-1;
string ans;
int carry=0;
while(i>=0 || j>=0 || carry>0)
{
int x=(i>=0)?num1[i]-'0':0;
int y=(j>=0)?num2[j]-'0':0;
int sum=x+y+carry;
carry=sum/10;
int digit=sum%10;
ans=to_string(digit)+ans;
i--;
j--;
}
return ans;

}
};

class Solution {
public:
 int lengthOfLongestSubstring(string s) {
unordered_map<char,int>mp;
int n = s.length();
int ans = 0,curr=0;
for(int i = 0;i<n;i++){
if(mp.find(s[i])!=mp.end()){

curr=max(mp[s[i]]+1,curr);
}
mp[s[i]] = i;
ans = max(ans,i-curr+1);
}
return ans;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int>mp;
int n = s.length();
int ans = 0,curr=0;
for(int i = 0;i<n;i++){
if(mp.find(s[i])!=mp.end()){

curr=max(mp[s[i]]+1,curr);
}
mp[s[i]] = i;
ans = max(ans,i-curr+1);
}
return ans;
}
};

class Solution {
public:
// time/space: O(nklogk)/O(nk)
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// build a map with `sorted words as the key` and `anagrams as values (vector)`
unordered_map<string, vector<string>> hash;
for (auto& s : strs) {
string t = s;
sort(t.begin(), t.end());
hash[t].push_back(s);
}

// convert the hash map to the result

vector<vector<string>> result;
for (auto& [k, v] : hash) result.push_back(v);
 return result;
}
};

class Solution {
public:
string intToRoman(int num) {
string Roman = "";

vector<pair<int, string>> storeIntRoman = {{1000, "M"}, {900, "CM"}, {500,

"D"}, {400, "CD"}, {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9,
"IX"}, {5, "V"}, {4, "IV"}, {1, "I"}};

for (int i = 0; i < storeIntRoman.size(); i++) {

while (num >= storeIntRoman[i].first) {
Roman += storeIntRoman[i].second;
num -= storeIntRoman[i].first;
}
}
return Roman;
}
};

class Solution {
public:
vector<string>ans;
void recursion(string s,int n, int open ,int close){
if(s.length()==2*n){
ans.push_back(s);
return;
}
if(open<n){
recursion(s+'(',n,open+1,close);
}
if(close<open){
recursion(s+')',n,open,close+1);
}

}
vector<string> generateParenthesis(int n) {
recursion("",n,0,0);
return ans;
}
};
`
.

class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int>ans;
stack<int> st;

for(int i=0;i<nums1.size();i++)
{
while(!st.empty() && nums1[st.top()]<nums[i])
{
ans[st.top()]=nums[i];
st.pop();

}
st.push(i);

}
};

class MyStack {
public:
MyStack() {

}
queue<int> q;
void push(int x) {
int size = q.size();
q.push(x);
for (int i=0;i<size; i++){
q.push(q.front());
q.pop();
}

int pop() {
int ans = q.front();
q.pop();
return ans;
}

int top() {
 return q.front();
}

bool empty() {
return q.empty();
}
};

class MyQueue {
public:
stack<int> s1, s2;
void push(int x) {
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
s1.push(x);
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
}

int pop() {
if(s1.empty()) return -1;
int d = s1.top();
s1.pop();
return d;
}

int peek() {
return s1.top();
}

bool empty() {
return s1.empty();
}
};

class Solution {
public:
 string removeDuplicates(string s, int k) {
vector<pair<char,int>> S;

for(auto c:s)
{
if(S.size()==0 || S.back().first != c)
S.push_back({c,1});
else
{

S.back().second++;
}
if(S.back().second==k)
S.pop_back();
}
string ret;
for(auto p: S)
{
ret.append(p.second, p.first); //appends p.second, p.first many times
}
return ret;
}
};

class Solution {
public:
std::vector<int> dailyTemperatures(std::vector<int>& temps) {
std::vector<int> results(temps.size());
std::stack<int> stack;

for (int i = 0; i < temps.size(); i++) {

while (!stack.empty() && temps[stack.top()] < temps[i]) {
results[stack.top()] = i - stack.top();
stack.pop();
}
stack.push(i);
}

return results;
}
};

class Solution {
public:
int evalRPN(vector<string>& tokens) {
int n = tokens.size();
 stack<int>st;
for(int i=0;i<n;i++){
if(tokens[i] == "+" or tokens[i] == "-" or tokens[i] == "*" or tokens[i] == "/"){
int num1 = st.top(); st.pop();
int num2 = st.top(); st.pop();
int newNum = 0;
if(tokens[i] == "+") newNum = num2+num1;
else if(tokens[i] == "-") newNum = num2-num1;
else if(tokens[i] == "*") newNum = num2*num1;
else newNum = num2/num1;
st.push(newNum);
}
else st.push(stoi(tokens[i]));
}
return st.top();
}
};

class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> pq;

for (int i = 0; i < heights.size() - 1; ++i) {

int diff = heights[i + 1] - heights[i];

if (diff > 0) {
pq.push(diff);

if (pq.size() > ladders) {

int smallest_diff = pq.top();
pq.pop();
bricks -= smallest_diff;

if (bricks < 0) {
return i;
}
}
}
}
return heights.size() - 1;
}
};

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
 int m=matrix.size();
int n=matrix[0].size();
int start=0;
int end=m*n-1;

while(start<=end)
{
int mid=(start+end)/2;
int mid_ele=matrix[mid/n][mid%n];

if(target==mid_ele)
return true;
else if(target>mid_ele)
start=mid+1;
else
end=mid-1;
}

return false;

}
};

/*

1 3 5 7 10 11 16 20 23 30 34 60
00 01 02 03 10 11 12 13 20 21 22 23

tar=3

mid=6

row=6/4->1

col=6%4->2

*/

class Solution {
public:
 // count of number of elements smaller than current possible candidate for answer
bool possible(vector<vector<int>>& grid, int k, int val){
int n=grid.size();

int i=0, j=n-1;

int c=0;
while(i<n && j>=0){
if(grid[i][j]>val){
j--;
}else{
c+=j+1;
i++;
}
}
return (c>=k);
}
int kthSmallest(vector<vector<int>>& grid, int k) {
int n=grid.size();
int l=grid[0][0], r=grid[n-1][n-1]; // minimum and maximum values possible
in grid

while(l<r){
int m=l+(r-l)/2;
if(possible(grid,k,m)){
r=m;
}else{
l=m+1;
}
}
return l;
}
};

class Solution {
public:
int nthUglyNumber(int& n) {
vector<int> dp(n,0);
dp[0] = 1;
int i = 0, j = 0, k = 0;
for(int z = 1; z < n; z++){
dp[z] = min(dp[i]*2,min(dp[j]*3,dp[k]*5));
if(dp[z]==dp[i]*2)i++;
if(dp[z]==dp[j]*3)j++;
if(dp[z]==dp[k]*5)k++;
// cout<<dp[z]<<" ";
}
 return dp[n-1];
}
};

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
stack<int>s;
vector<int>v;
int K=nums.size()-k;
for(int i=0;i<nums.size();i++){
if(s.size()==0){
s.push(nums[i]);
}
else{
while(!s.empty() && nums[i]<s.top() && K){
s.pop();
K--;
}
s.push(nums[i]);
}
}
while(K--){
s.pop();
}
while(!s.empty()){
v.push_back(s.top());
s.pop();
}
reverse(v.begin(),v.end());
return v;
}
};

class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int maxsat=0,existsat=0,curChange=0,maxChange=0;

for(int i=0;i<customers.size();i++)
{
if(!grumpy[i])
existsat+=customers[i];

if(grumpy[i])
curChange+=customers[i];

if(i>=X && grumpy[i-X])

 curChange-=customers[i-X];

maxChange=max(maxChange,curChange);

}
maxsat=existsat+maxChange;

return maxsat;

}
};

class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0, res = 0, cnt = 0, size = nums.size();
while(right<size)
{
if(nums[right]==0){
cnt++;
}
while(cnt>k){
if(nums[left]==0)
cnt--;
left++;
}
right++;
res = max(res, right-left);
}
return res;
}
};

longest-repeating-character-replacement

class Solution {
public:
// implement function same as "Max consecutive ones III "
int slidingChar(char c,string s,int k){
int ans=1;
int left=0;
int differ=0;
for(int right=0;right<s.size();right+=1){
if(s[right]!=c) differ+=1;
while(differ>k){
if(s[left++]!=c) differ-=1;
 }
ans=max(ans,right-left+1);
}
return ans;
}
int characterReplacement(string s, int k) {
// using set for get distinct character from string
set<char>se;
for(auto x:s) se.insert(x);
int ans=1;
for(auto x:se){
// choose one character in string to be "1" in problem Max consecutive
ones III
ans=max(ans,slidingChar(x,s,k));
}
return ans;
}
};

class Solution {
public:
int maxScoreSightseeingPair(vector<int>& arr) {
int aiplusi= arr[0]+0, ans= INT_MIN;

for(int j=1;j<arr.size();j++){
ans= max(ans, aiplusi+arr[j]-j);
aiplusi= max(aiplusi, arr[j]+j);
}

return ans;
}
};

/*

[8,1,5,2,6]
[8,8,8,8,10]
[_,0,3,-1,2]

*/
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {

unordered_map<int,int> map;
int c=0;
int sum=0;
int n=nums.size();
int i=0;
while(i<n)
{
sum+=nums[i];
if(sum==k)
c++;
if(map.find(sum-k)!=map.end())
c+=map[sum-k];
map[sum]+=1;
i++;
}
return c;

}
};

class Solution {
public:

#define DPSolver ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

vector<vector<int>> kClosest(vector<vector<int>> &points, int k)

{
DPSolver;
priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<>> pq;

for (auto point : points){

double dis = sqrt(pow(point[0], 2)+ pow(point[1], 2));
pq.push({dis, {point[0], point[1]}});
}
vector<vector<int>> res;
while (k-- && pq.size())
{
res.push_back({pq.top().second.first, pq.top().second.second});
pq.pop();
}
return res;
}
};

class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> q;
for (int i = 0; i < nums.size(); i++) {
q.push(nums[i]);
}
for(int i = 1; i < k; i++) {
q.pop();
}
return q.top();
}
};

class Solution {
public:
int mySqrt(int x) {
int start = 1, end = x, answer = 0;
while (start<=end)
{
int mid = start + (end-start)/2;
if(mid== x/mid) return mid;
else if(mid>x/mid) end = mid-1;
else{
answer = mid;
start = mid+1;
}
}
return answer;
}
};

class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int count = 0;
for(int i=0; i<grid.size(); i++) {
count += upper_bound(grid[i].rbegin(), grid[i].rend(), -1) -
grid[i].rbegin();
}
return count;
}
};

class Solution {
public:
 int peakIndexInMountainArray(vector<int>& arr) {
int start=0,end=arr.size()-1;
int mid=(start+end)/2;
while(start<end){
mid=(start+end)/2;
if(arr[mid]<arr[mid+1]){
start=mid+1;
}
else{
end=mid;
}

}
return start;
}
};

class Solution {
public:

private:
int helper(vector<int>& arr, int target, int start, int end) {
if(start > end)
return -1;

int mid = start + (end - start) / 2;

if(arr[mid] == target)
return mid;

if(arr[start] <= arr[mid]) {

// left sorted part
if(target >= arr[start] && target <= arr[mid]) {
// if target lies in this sorted range, search in this only, discard
right part, by end = mid - 1
end = mid - 1;
} else {
// means, it does not lies here, so discard this part, by, start =
mid + 1
start = mid + 1;
}
} else {
// arr[start] > arr[mid]
if(target >= arr[mid] && target <= arr[end]) {
// target is in this range, so discard left part (start = mid + 1),
now search in this
start = mid + 1;
 } else {
// else, it's not in that range, so search in left part now
end = mid - 1;
}
}
// recursive call
return helper(arr, target, start, end);
}

public:
int search(vector<int>& nums, int target) {
// return what we are getting from helper function
return helper(nums, target, 0 , nums.size() - 1);
// we made helper, so that, we can pass start and end after computing, in
another recursion calls
}

};

class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l=0, r=nums.size()-1;
int n=nums.size();
while(l < r)
{
int mid = (l + r )/ 2;
if(nums[mid]>nums[mid+1])
r=mid;
else
l=mid+1;

}
return l;
}
};

class Solution {
public:
vector<int> partitionLabels(string s) {

unordered_map<char , int> map;

// filling of map
for(int i =0; i < s.length(); i++){
map[s[i]] = i;
 }

// Declaration of array and variables

vector<int> result;
int previous = -1;
int maximum = -1;

for(int i = 0; i < s.length(); i++){

maximum = max(maximum , map[s[i]]);

if(maximum == i){
int ans = maximum-previous;
previous = maximum;
result.push_back(ans);
}
}
return result;
}

};

class Solution {
public:
void sortColors(vector<int>& nums) {

int low = 0;
int high = nums.size() - 1;
int mid = 0;

while(mid <= high)

{
if(nums[mid] == 0)
{
swap(nums[mid], nums[low]);
low++;
mid++;
}
else if(nums[mid] == 1)
{
mid++;
}
else if(nums[mid] == 2){
swap(nums[mid], nums[high]);
high--;
 }

}
};

Given an array of intervals intervals where intervals[i] = [starti, end i], return the minimum number of
intervals you need to remove to make the rest of the intervals non-overlapping.

class Solution {
public:

int eraseOverlapIntervals(vector<vector<int>>&v)
{
int n=v.size();
sort(v.begin(), v.end()); // sort on the basis of start points
int count=0;
int i=0, j=1;

while(j<n)
{
if(v[i][1] <= v[j][0]) // Non-overlapping case(Case 1)
{
i=j;
j++;
}
else if(v[i][1] <= v[j][1]) // Case 2
{
count++;
j++;
}
else if(v[i][1] > v[j][1]) // Case 3
{
count++;
i = j;
j++;
}
}
return count;
}
};

class Solution {
public:
 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int tank = 0;
int pos = 0;
int total = 0;

//if total fuel at the end is positive there exist a solution

//each time we run out of fuel we know that we can't make it from say
//A(start) , B(end) then we start from B+1 index until fuel runs out if
//at the end total fuel is positive we return the last index from where if
start
//we don't run out of fuel
for(int i=0;i<n;i++){
if((tank = tank+gas[i]-cost[i])<0){
pos = i+1;
total += tank;
tank = 0;
}
}

return (total+tank>=0)?pos:-1;

}
};

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<=1)
return intervals;

sort(intervals.begin(),intervals.end());
vector<vector<int>> output;

output.push_back(intervals[0]);

for(int i=1;i<intervals.size();i++)
{
if(output.back()[1]>=intervals[i][0])
output.back()[1]=max(output.back()[1],intervals[i][1]);
else
output.push_back(intervals[i]);
}

return output;
 }
};

bool comp(vector<int>&a,vector<int>&b){
if(a[1] == b[1])
return a[0] < b[0];
return a[1] < b[1];
}
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(), comp);
int n = events.size();
int maxevents = 0;
set<int>s;
for(int i= 1; i <= 100000; i++){
s.insert(i);
}
for(int i = 0; i < n; i++){
int start = events[i][0], en = events[i][1];
auto it = s.lower_bound(start);
if(it == s.end() || *it > en){
continue;
}
else{
maxevents++;
s.erase(it);
}
}
return maxevents;
}
};

Minimum Deletion Cost to Avoid Repeating Letters

Input: s = "aabaa", cost = [1,2,3,4,1]

Output: 2

public int minCost(String s, int[] cost) {

int mincost=0;
for(int i=1;i<s.length();i++)
{
if(s.charAt(i)==s.charAt(i-1))
{
if(cost[i-1]<cost[i])
{
 mincost+=cost[i-1];
}

else
{
mincost+=cost[i];
cost[i]=cost[i-1];
}
}
}
return mincost;
}

Input: str1 = "ABCABC", str2 = "ABC"

Output: "ABC"

class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) {
return "";
}
int gcdStr = gcd(str1.size(), str2.size());

return str1.substr(0, gcdStr);

}
};

Bfs:

class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {

vector<bool> v(rooms.size(),false);
queue<int>q;
q.push(0);
vector<int>ans(rooms.size());

while(!q.empty())
{
int curr=q.front();
ans[curr]=true;
ans.push_back(curr);
q.pop();

for(auto x:rooms[curr])
 {
if(ans[x]==false)
q.push(x);
}
}

for(int i=0;i<rooms.size();i++)
{
if(ans[i]!=true)
return false;
}

return true;

}
};

iven an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j <
k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10 9 + 7.

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output: 20
Explanation:
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

class Solution {
public:
int threeSumMulti(vector<int>& A, int target) {
int mod=1e9+7;
vector<long> count(101,0);
for(auto x:A){
count[x]+=1;
}
long res=0;
for(int i=0;i<=target;i++){
for(int j=i;j<=target;j++){
int k=target-i-j;
if(k<j || k>=count.size()) continue;
if(count[i]==0 || count[j]==0 || count[k]==0) continue;
if(i==j && j==k && count[i]>=3){
res=(res+count[i]*(count[i]-1)*(count[i]-2)/6)%mod;
 }
else if(i==j && i!=k && count[i]>=2){
res=(res+count[k]*count[i]*(count[i]-1)/2)%mod;
}

else if(j==k && i!=k && count[j]>=2){

res=(res+count[i]*(count[j]-1)*count[k]/2)%mod;
}

else if(i!=j && j!=k && i!=k){

res=(res+count[i]*count[j]*count[k])%mod;
}
}
}

return res;
}
};

chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

class Solution {
public:
int compress(vector<char>& chars) {
int i=0,n=chars.size();
int k=0;
while(i<n)
{
int j=i;
while(j<n && chars[j]==chars[i])
{
j++;
}
chars[k++]=chars[i];
if(j-i>1)
{
for(char c:to_string(j-1))
{
chars[k++]=c;
}
 }
i=j;
}
return k;
}
};

nums = [1,2,3,4]
Output: [2,4,4,4]

class Solution {
public:
vector<int> decompressRLElist(vector<int>& nums) {
vector<int> v;
for(int i=0;i<nums.size();i+=2){
while(nums[i]>0){
v.push_back(nums[i+1]);
nums[i]--;
}
}
return v;
}
};

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {
public:
vector<string> ans;

unordered_map<char, string> dict{

{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8',"tuv"},
{'9', "wxyz"}
};

void dfs(string& digits, string str, int i)

{
 if (i == digits.size())
{
ans.push_back(str);
return;
}
for (auto each : dict[digits[i]])
{
dfs (digits, str + each, i + 1);
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) return ans;
dfs (digits, "", 0);
return ans;
}
};

Input: graph = [[1,2],[3],[3],[]]

Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

class Solution {
public:
void dfs(int root,vector<int>& curr,vector<bool>& vis,vector<vector<int>>& g,
vector<vector<int>>& ans){
if(vis[root]) return ;
vis[root]=true;
curr.push_back(root);
if(root==g.size()-1) ans.push_back(curr);
for(auto x:g[root]) dfs(x,curr,vis,g,ans);
curr.pop_back();
vis[root]=false;
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<bool> vis(graph.size(),false);
vector<int> curr;
dfs(0,curr,vis,graph,ans);
return ans;
}
};

Input: s = "3[a2[c]]"
Output: "accaccacc"
class Solution {
public:
string recurse(string &s, int &index)
{
string ret;
while(index<s.length() && s[index]!=']')
{
if(!isdigit(s[index]))
ret+=s[index++];
else
{
int k=0;
while(index<s.length()&&isdigit(s[index]))
k = k*10 + s[index++]-'0';
index++; //because digit always accompained by '['
string dec = recurse(s, index);
index++; //and accompanied by a closing ']' too
while(k-- > 0)
ret+=dec;
}
}
return ret;
}
string decodeString(string s) {
int index = 0;
return recurse(s, index);

}
};

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]

class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j) {
// boundary checking
int n = grid.size();
int m = grid[0].size();
if(i < 0 || i >= n || j < 0 || j >= m)
return;
// return if current position is of water or is already visited
if(grid[i][j] == '2' || grid[i][j] == '0')
return;
 // mark the current as visited
grid[i][j] = '2';

// do DFS in all 4 directions

dfs(grid, i+1, j);
dfs(grid, i, j-1);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
}

int numIslands(vector<vector<char>>& grid) {

// We can treat the matrix grid as a grid. Each Island is a
// connected component. The task is to find no. of disconnectedd components
// in the graph.

int islands = 0;
// We make each 1 as 2 in when it is visited
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++) {
// do DFS in case has not been visited and there is land
if(grid[i][j] == '1') {
dfs(grid, i, j);
++islands;
}
}
}
return islands;
}
};

 Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
 A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j
< k < n).
 Input: rating = [2,5,3,4,1]
 Output: 3
 Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

class Solution {
public:
Solution(){
ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
}
int numTeams(vector<int>& rating) {
int n=rating.size(),res=0,rightLess,rightGreat,leftLess,leftGreat;
if(n<3)return 0;
 for(int i=1;i<n-1;i++){
rightLess=0;rightGreat=0; leftLess=0; leftGreat=0;
for(int j=0;j<i;j++){
if(rating[j]<rating[i])leftLess++;
else leftGreat++;
}
for(int j=i+1;j<n;j++){
if(rating[j]>rating[i])rightGreat++;
else rightLess++;
}
res=res+leftLess*rightGreat + leftGreat*rightLess;
}
return res;
}
};

BACKTRACKING:

https://leetcode.com/problems/permutations/solutions/18239/A-general-approach-to-backtracking-
questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)/

N-queens

class Solution {
public:
bool issafe(int row,int col,vector<string> &v,int n){
int duprow =row;
int dupcol =col;

while(row>=0 && col >= 0){

if(v[row][col] == 'Q')return false;
row--;
col--;
}

row =duprow;
col =dupcol;
while(col >=0){
if(v[row][col] == 'Q')return false;
// row--;
col--;
 }
row =duprow;
col =dupcol;
while(row <n && col >= 0){
if(v[row][col] == 'Q')return false;
row++;
col--;
}

return true;

}
void solve(int col, vector<string> &v, vector<vector<string>>&res,int n){

if(col ==n){
res.push_back(v);
return;
}

for(int row =0 ;row<n;row++){

if(issafe(row,col,v,n)){
v[row][col] ='Q';
solve(col+1,v,res,n);
v[row][col] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> v(n);
string s(n,'.');
for(auto i =0 ;i<n ;i++){
v[i] =s;
}

solve(0,v,res,n);

return res;

}
};

Bit manipulation:

https://leetcode.com/problems/sum-of-two-integers/solutions/84278/A-summary:-how-to-use-bit-
manipulation-to-solve-problems-easily-and-efficiently/
count inversions:

#include <bits/stdc++.h>
using namespace std;

int merge(vector<int> &arr, int low, int mid, int high) {

vector<int> temp; // temporary array
int left = low; // starting index of left half of arr
int right = mid + 1; // starting index of right half of arr

//Modification 1: cnt variable to count the pairs:

int cnt = 0;

//storing elements in the temporary array in a sorted manner//

while (left <= mid && right <= high) {

if (arr[left] <= arr[right]) {
temp.push_back(arr[left]);
left++;
}
else {
temp.push_back(arr[right]);
cnt += (mid - left + 1); //Modification 2
right++;
}
}

// if elements on the left half are still left //

while (left <= mid) {

temp.push_back(arr[left]);
left++;
}

// if elements on the right half are still left //

while (right <= high) {
temp.push_back(arr[right]);
right++;
}

// transfering all elements from temporary to arr //

for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
 return cnt; // Modification 3
}

int mergeSort(vector<int> &arr, int low, int high) {

int cnt = 0;
if (low >= high) return cnt;
int mid = (low + high) / 2 ;
cnt += mergeSort(arr, low, mid); // left half
cnt += mergeSort(arr, mid + 1, high); // right half
cnt += merge(arr, low, mid, high); // merging sorted halves
return cnt;
}

int numberOfInversions(vector<int>&a, int n) {

// Count the number of pairs:

return mergeSort(a, 0, n - 1);
}

int main()
{
vector<int> a = {5, 4, 3, 2, 1};
int n = 5;
int cnt = numberOfInversions(a, n);
cout << "The number of inversions are: "
<< cnt << endl;
return 0;
}

Lru cache:

class LRUCache {
public:
class Node {
public:
int key, val;
Node *next, *prev;
Node(int KEY, int VAL) {
key=KEY; val=VAL;
}
};
int cap;
unordered_map<int, Node*> mp;
Node *head=new Node(-1, -1);
Node *tail=new Node(-1, -1);
LRUCache(int capacity) {
cap=capacity;
head->next=tail;
tail->prev=head;
}
void addNode(Node *newNode) {
Node *temp=head->next;
newNode->next=temp;
newNode->prev=head;
head->next=newNode;
temp->prev=newNode;
}
void deleteNode(Node *delNode) {
Node *delPrev=delNode->prev;
Node *delNext=delNode->next;
delPrev->next=delNext;
delNext->prev=delPrev;
}
int get(int key) {
if(mp.find(key) != mp.end()) {
Node *resNode=mp[key];
int res=resNode->val;

mp.erase(key);
deleteNode(resNode);

addNode(resNode);
mp[key]=head->next;
return res;
}
return -1;
}

void put(int key, int value) {

if(mp.find(key) != mp.end()) {
Node *existingNode=mp[key];
mp.erase(key);
deleteNode(existingNode);
}
if(mp.size() == cap) {
mp.erase(tail->prev->key);
deleteNode(tail->prev);
}
addNode(new Node(key, value));
mp[key]=head->next;
 }
};

struct Node
{
int key,value,cnt;
Node *next;
Node *prev;
Node(int _key,int _value)
{
key=_key;
value=_value;
cnt=1;
}
};

struct List
{
int size;
Node *head;
Node *tail;
List()
{
head= new Node(0,0);
tail=new Node(0,0);
head->next=tail;
tail->prev=head;
size=0;
}

void addfront(Node *node)

{
Node *temp=head->next;
node->next=temp;
node->prev=head;
head->next=node;
temp->prev=node;
size++;
}

void removenode(Node *delnode)

{
Node *delprev=delnode->prev;
Node *delnext=delnode->next;
delprev->next=delnext;
delnext->prev=delprev;
 size--;
}
};

class LFUCache {
map<int,Node*>keynode;
map<int,List*>freqlistmap;
int maxsizecache;
int minfreq;
int cursize;
public:
LFUCache(int capacity)
{
maxsizecache=capacity;
minfreq=0;
cursize=0;

}
void updatefreqlistmap(Node *node)
{
keynode.erase(node->key);
freqlistmap[node->cnt]->removenode(node);
if(node->cnt==minfreq and freqlistmap[node->cnt]->size==0)
{
minfreq++;
}
List *nexthigherfreqlist=new List();
if(freqlistmap.find(node->cnt+1)!=freqlistmap.end())
{
nexthigherfreqlist=freqlistmap[node->cnt+1];
}
node->cnt+=1;
nexthigherfreqlist->addfront(node);
freqlistmap[node->cnt]=nexthigherfreqlist;
keynode[node->key]=node;
}

int get(int key)

{
if(keynode.find(key)!=keynode.end())
{
Node *node=keynode[key];
int val=node->value;
updatefreqlistmap(node);
return val;
}
 return -1;

void put(int key, int value)

{
if(maxsizecache==0)
return;
if(keynode.find(key)!=keynode.end())
{
Node *node=keynode[key];
node->value=value;
updatefreqlistmap(node);
}
else
{
if(cursize==maxsizecache)
{
List *list=freqlistmap[minfreq];
keynode.erase(list->tail->prev->key);
freqlistmap[minfreq]->removenode(list->tail->prev);
cursize--;
}
cursize++;
minfreq=1;
List *listfreq=new List();
if(freqlistmap.find(minfreq)!=freqlistmap.end())
{
listfreq=freqlistmap[minfreq];
}
Node *node=new Node(key,value);
listfreq->addfront(node);
keynode[key]=node;
freqlistmap[minfreq]=listfreq;
}

}
};

/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

class BrowserHistory {
public:
list<string> history;
list<string> :: iterator it;
BrowserHistory(string homepage) {
history.push_back(homepage);
it=history.begin();
}

void visit(string url) {

auto del=it;
del++;
history.erase(del,history.end());
history.push_back(url);
it++;
}

string back(int steps) {

while(it!=history.begin() && steps--){
it--;
}
return *it;
}

string forward(int steps) {

while(it!=--history.end() && steps--){
it++;
}
return *it;
}
};

/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/

class MedianFinder {
public:
priority_queue<int>first_half;
priority_queue<int, vector<int>, greater<int>>second_half;

MedianFinder() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
 }

void addNum(int num) {

first_half.push(num);
int fqsize = first_half.size(), sqsize = second_half.size();
int total = fqsize + sqsize;
while((fqsize - sqsize) != ((total) & 1) && fqsize >= sqsize){
second_half.push(first_half.top()); first_half.pop();
fqsize = first_half.size(), sqsize = second_half.size();
}
if(fqsize && sqsize){
int ftop = first_half.top(), stop = second_half.top();
if(ftop > stop){
first_half.pop(), second_half.pop();
first_half.push(stop), second_half.push(ftop);
}
}
}

double findMedian() {
int fqsize = first_half.size(), sqsize = second_half.size();
if((fqsize + sqsize) & 1) return first_half.top() * 1.0;
else{
double sum = first_half.top() * 1.0 + second_half.top() * 1.0;
return sum / 2.0;
}
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/

https://leetcode.com/problems/maximum-depth-of-binary-tree/

int maxDepth(TreeNode* root) {

if(root==NULL)
return 0;

int l=maxDepth(root->left)+1;
int r=maxDepth(root->right)+1;
if(l>r)
 return l;
else
return r;

class Solution {
public:
int singleNumber(vector<int>& nums) {
int x=0;
for(auto e:nums)
{
x=x^e;
}
return x;

}
};

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size() != postorder.size())
return NULL;

unordered_map<int,int> map;
for(int i=0;i<inorder.size();i++)
map[inorder[i]]=i;

return call(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1,map);

}
 TreeNode * call(vector<int> &inorder,int is,int ie,vector<int> &postorder,int
ps,int pe,unordered_map<int,int> map)
{
if(ps>pe || is>ie)
return NULL;
TreeNode* root=new TreeNode(postorder[pe]);
int l=map[postorder[pe]];
int lc=l-is;
root->left=call(inorder,is,l-1,postorder,ps,ps+lc-1,map);
root->right=call(inorder,l+1,ie,postorder,ps+lc,pe-1,map);

return root;
}
};

class Solution {
public:

bool check(TreeNode* p,TreeNode* q)

{
if((p==NULL && q!=NULL) || (q==NULL && p!=NULL))
return false;
if(p==NULL && q==NULL)
return true;

if(p->val != q->val)
return false;

return check(p->left,q->right) && check(p->right,q->left);

}
bool isSymmetric(TreeNode* root) {

return check(root->left,root->right);

}
};

class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size();
if(n==1)
return nums[0];
 int l=0,r=n-1;
while(l<r)
{
int mid=l+(r-l)/2;
if(mid>0 && nums[mid]<nums[mid-1])
return nums[mid];
else if(nums[l]<=nums[mid] && nums[mid]>=nums[r])
l=mid+1;
else
r=mid-1;

}
return nums[l];

}
};

class Solution {
public int[] sortedSquares(int[] nums) {
int i=0,j=nums.length-1;
int ans[]=new int[nums.length];
for(int k=nums.length-1;k>=0;k--)
{
if(Math.abs(nums[i])<Math.abs(nums[j]))
{
ans[k]=nums[j]*nums[j];
j--;
}
else
{
ans[k]=nums[i]*nums[i];
i++;
}

}
return ans;

}
}

class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
int i=0,j=n;
int c=0;
 vector<int> ans(2*n);
while(j<2*n)
{
ans[c]=nums[i];
ans[c+1]=nums[j];
i++;
j++;
c+=2;

}
return ans;

}
};

class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 || j==0)
dp[i][j]=1;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];

}
};

class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==NULL)
return root;

TreeNode* temp=invertTree(root->left);
invertTree(root->right);
root->left=root->right;
root->right=temp;

return root;
 }
}

https://leetcode.com/problems/longest-increasing-subsequence/

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size());
dp[0]=1;

for(int i=1;i<nums.size();i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j] && dp[i]<dp[j]+1)
dp[i]=dp[j]+1;
}

return *max_element(dp.begin(),dp.end());

}
};

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

class Solution {
public:

TreeNode* helper(vector<int> & nums,int s,int e)

{
if(s>e)
return NULL;

int mid=(s+e)/2;
TreeNode *root=new TreeNode(nums[mid]);
root->left=helper(nums,s,mid-1);
root->right=helper(nums,mid+1,e);
 return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums,0,nums.size()-1);

}
};

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur=head;

while(cur && cur->next)

{
if(cur->val==cur->next->val)
{
cur->next=cur->next->next;
}
else
{
cur=cur->next;
}

return head;

}
};

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *res=new ListNode();
res->next=head;

ListNode *s=res;
ListNode *f=res;

for(int i=1;i<=n;i++)
{
f=f->next;
 }
while(f->next!=NULL)
{
s=s->next;
f=f->next;

s->next=s->next->next;

return res->next;
}
};

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {

vector<int> row(matrix[0].size(),0);
vector<int> col(matrix.size(),0);

for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j]==0)
{
row[j]=1;
col[i]=1;
}
}
}

for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(row[j]==1 || col[i]==1)
matrix[i][j]=0;
}
}
}
};

class Solution {
public:
int countPrimes(int n) {

vector<bool> dp(n,true);

for(int i=2;i<sqrt(n);i++)
{
if(dp[i])
{
for(int j=i*i ;j<n;j=j+i)
{
dp[j]=false;
}

}
}
int c=0;
for(int i=2;i<n;i++)
{
if(dp[i])
c++;
}
return c;

}
};

class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *s=head;
ListNode *f=head;

while(f && f->next)

{
s=s->next;
f=f->next->next;
}
return s;
}
};

class Solution {
public:
static bool compare(pair<int,string> &a,pair<int,string> &b)
{
 if(a.first==b.first)
return a.second<b.second;
else
return a.first>b.first;
}
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> map;
for(auto x:words)
{
map[x]++;
}
vector<pair<int,string>> vec;
for(auto it=map.begin();it!=map.end();it++)
{
vec.push_back({it->second,it->first});
}
sort(vec.begin(),vec.end(),compare);
vector<string>ans;

for(int i=0;i<k;i++)
{
ans.push_back(vec[i].second);

}
return ans;

}
};

class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head==NULL || head->next==NULL)
return head;

ListNode *odd=head;
ListNode *even=head->next;
ListNode *temp=even;

while(even && even->next)

{
odd->next=odd->next->next;
even->next=even->next->next;
odd=odd->next;
even=even->next;
}
 odd->next=temp;

return head;

}
};

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

[0,0,1,1,1,2,2,3,3,4]

class Solution {
public:
int removeDuplicates(vector<int>& nums) {

int index=1;
for(int i=1;i<nums.size();i++)
{
if(nums[i-1]!=nums[i])
nums[index++]=nums[i];
}
return index;
}
};

https://leetcode.com/problems/find-all-anagrams-in-a-string/

class Solution {
public:
bool check(vector<int> c1,vector<int> c2)
{
for(int i=0;i<26;i++)
{
if(c1[i]!=c2[i])
return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
int n1=p.size();
int n2=s.size();
vector<int> c1(26,0);
vector<int> c2(26,0);

vector<int>ans;

for(int i=0;i<n1;i++)
 {
c1[p[i]-'a']++;
}
for(int i=0;i<n2;i++)
{
if(i<n1)
{
c2[s[i]-'a']++;
}
else
{
if(check(c1,c2))
{
ans.push_back(i-n1);
}
c2[s[i-n1]-'a']--;
c2[s[i]-'a']++;
}

}
if(check(c1, c2))
{
ans.push_back(n2 - n1);
}

return ans;

}
};

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL){
return NULL;
}

if(root->val < p->val && root->val < q->val)

//recusion call
return lowestCommonAncestor(root->right,p,q);
if(root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left,p,q);

return root;
 }
};

https://leetcode.com/problems/minimum-size-subarray-sum/

class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
long long su = 0;
int n = nums.size();
int i = 0, j = 0;
int m = INT_MAX;

while (j < n) {
su += nums[j];
while (su >= target) {
m = min(m, j - i + 1);
su -= nums[i];
i++;
}
j++;
}

return (m == INT_MAX) ? 0 : m;
}
};

class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
if(n==1)
return nums[0];
vector<int> dp(n);
dp[0]=nums[0];
if(n>=2)
dp[1]=max(nums[0],nums[1]);

for(int i=2;i<n;i++)
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);

return dp[n-1];

}
};
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int r=obstacleGrid.size();
int c=obstacleGrid[0].size();

vector<vector<int>> dp(r,vector<int>(c));
bool fr=false,fc=false;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(i==0 || j==0)
{
dp[i][j]=1;
if(obstacleGrid[0][j]!=0 || fr)
{

dp[0][j]=0;
fr=true;

}
if(obstacleGrid[i][0]!=0 || fc)
{

dp[i][j]=0;
fc=true;

}
else
{
if(obstacleGrid[i][j]==0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
else
dp[i][j]=0;
}
}
}
return dp[r-1][c-1];
}
};
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1=m-1;
int p2=n-1;
int i=m+n-1;

while(p2>=0)
{
if(p1>=0 && nums1[p1]>nums2[p2])
nums1[i--]=nums1[p1--];
else
nums1[i--]=nums2[p2--];
}

}
};

class Solution {
public:
bool isPalindrome(ListNode* head) {

if(head->next==NULL)
return true;
stack<int> s;

ListNode *temp=head;

while(temp)
{
s.push(temp->val);
temp=temp->next;
}

temp=head;

while(temp)
{
if(temp->val != s.top())
return false;

s.pop();
temp=temp->next;
}
 return true;

}
};

class Solution {
public:

void ans(TreeNode* root,vector<int>&r){

if(!root) return ;
if(!root->left && !root->right){
r.push_back(root->val);
return;
}
ans(root->left,r);
ans(root->right,r);
}
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int>r1;
vector<int>r2;

ans(root1,r1);
ans(root2,r2);

return r1==r2;

}
};

https://leetcode.com/problems/bulls-and-cows/

class Solution {
public:
string getHint(string secret, string guess) {
int countBull=0;
unordered_map<char,int>guessMap;
int n=secret.length();
for (int i=0;i<n;i++) {
if(secret[i]==guess[i]) {
countBull++;
}
else{
guessMap[guess[i]]++;
}
}
 int countCow=0;
for (int i=0;i<n;i++) {
if (secret[i] != guess[i] && guessMap[secret[i]]>0){
countCow++;
guessMap[secret[i]]--;
}
}
string ans=to_string(countBull)+"A" +to_string(countCow)+"B";
return ans;
}
};

class Solution {
public:
bool reachingPoints_recursive(int sx, int sy, int tx, int ty)
{
if (sx > tx || sy > ty)
{
return false;
}

if (sx == tx && sy == ty)

{
return true;
}

bool canReach = reachingPoints_recursive(sx, sx+sy, tx, ty);

if (!canReach)
{
canReach = reachingPoints_recursive(sx+sy, sy, tx, ty);
}

return canReach;
}

bool reachingPoints(int sx, int sy, int tx, int ty) {

return reachingPoints_recursive(sx, sy, tx, ty);
}
};

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

class Solution {
public:
 int find_total(vector<int>& nums, int mid){
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=ceil((double)nums[i]/(double)mid);
}
return sum;
}

int smallestDivisor(vector<int>& nums, int threshold) {

int high=*max_element(nums.begin(),nums.end());
int low=1;
while(low<=high) {
int mid=low+(high-low)/2;
if(find_total(nums,mid)<=threshold) {
high=mid-1;
} else{
low=mid+1;
}
}
return low;

}
};

class FreqStack {
private:
priority_queue<pair<int, pair<int, int>> > pq;
unordered_map<int, int> hash;
int indexAtVal;

public:
FreqStack() {
indexAtVal = 0;
}

void push(int val) {

// increase the frequency of element

hash[val]++;

// insert it to priority_queue by {freq, {index_of_element, element}}

// so priority_queue will maintain the order of most_frequent element at top
pq.push({hash[val], {indexAtVal++, val}});
}

int pop() {
 // pop the top element from the priority_queue
int val = pq.top().second.second;
pq.pop();

// reduce its frequency

hash[val]--;

return val;
}
};

/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {

ListNode *dummy=new ListNode(0);

dummy->next=head;

ListNode *prev=dummy;

ListNode *curr=head;

while(curr)
{
if(curr->next && curr->val == curr->next->val)
{
while(curr->next && curr->val == curr->next->val)
{
curr=curr->next;
}
prev->next=curr->next;
}
else
prev=prev->next;

curr=curr->next;
}
return dummy->next;;
}
};
https://leetcode.com/problems/largest-number/description/

class Solution {
public:
static bool cmp(int a,int b)
{
return (to_string(a)+to_string(b))>(to_string(b)+to_string(a));

}
string largestNumber(vector<int>& nums) {
sort(nums.begin(),nums.end(),cmp);

string s="";
for(auto x:nums)
{
s=s+to_string(x);
}
if(s[0]=='0')
return "0";
else
return s;
}
};

class Solution {
public:
bool isValid(string s) {
stack<char> st ;
int i , n = s.length() ;
for(i=0;i<n;i++)
{
if(s[i]=='('){
st.push(')') ;
}
else if(s[i]=='['){
st.push(']') ;
}
else if(s[i]=='{'){
st.push('}') ;
}
else{
if(st.empty() || s[i]!=st.top()){
return false ;
}
st.pop();
}
 }
return st.empty() ;
}
};

class Solution {
public:
void Reverse(int i,int j,string &s){
while(i<=j)swap(s[i++],s[j--]);
}
string solve(string &s) {
reverse(s.begin(),s.end());
s.push_back(' ');
int j=0;
for(int i=0;i<s.size();i++){
if(s[i]==' '){
Reverse(j,i-1,s);
j=i+1;
}
}
s.pop_back();
return s;
}
string reverseWords(string s) {
int n=s.size(),i=0,j=n-1,k=0;
while(s[i]==' ')i++;
while(s[j]==' ')j--;
string ans;
k=i;
while(k<=j){
while(s[k]==' ')k++;
ans.push_back(s[k++]);
if(s[k]==' '&&k<=j)ans.push_back(s[k++]);
}
return solve(ans);
}
};

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root)
return NULL;

if(root->val ==p->val || root->val==q->val)

 return root;
TreeNode *l=lowestCommonAncestor(root->left,p,q);
TreeNode *r=lowestCommonAncestor(root->right,p,q);

if(l && r)
return root;
if(l)
return l;
else
return r;

}
};

class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
per(nums,ans,0);
return ans;

}
void per(vector<int> &nums,vector<vector<int>> &ans,int index)
{
if(index==nums.size())
{
ans.push_back(nums);
return;
}
for(int i=index;i<nums.size();i++)
{
swap(nums[i],nums[index]);
per(nums,ans,index+1);
swap(nums[i],nums[index]);
}
return;

}
};

class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> ds;
findCombination(0,candidates,target,ans,ds);
 return ans;
}
void findCombination(int index,vector<int>& arr,int target,vector<vector<int>>
&ans,vector<int> &ds){
//base Condition
if(index == arr.size()){
if(target == 0)
ans.push_back(ds);
return;
}

// Pick Condition
if(arr[index]<= target){
ds.push_back(arr[index]);
findCombination(index,arr, target-arr[index],ans,ds);
ds.pop_back();
}
findCombination(index+1, arr, target, ans, ds);
}
};

class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int>ans(n, 0);
vector<int>prefix(n);
for(auto i:bookings){

int first = i[0];

int last = i[1];
int seats = i[2];

ans[first-1] += seats;
if(last<ans.size()) ans[last] -= seats;

prefix[0]=ans[0];

for(int i =1 ; i<ans.size(); i++){

prefix[i]=prefix[i-1]+ans[i];
}

return prefix;
}
};

class Solution {
public:

bool isPowerOfThree(int n) {
if(n==0){
return false;
}
while(n%3 == 0){
n /= 3;
}
return n==1;
}
};

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
if(n1>n2) return findMedianSortedArrays(nums2,nums1);

int low = 0, high = n1;

while(low<=high){
int cut1 = (low+high)/2;
int cut2 = (n1+n2+1)/2 - cut1;

int left1 = cut1==0 ? INT_MIN : nums1[cut1-1];

int left2 = cut2==0 ? INT_MIN : nums2[cut2-1];

int right1 = cut1==n1 ? INT_MAX : nums1[cut1];

int right2 = cut2==n2 ? INT_MAX : nums2[cut2];

if(left1 <= right2 && left2 <= right1){

if((n1+n2)%2==0)
return (max(left1,left2)+min(right1,right2))/2.0;
else return max(left1,left2);
}
else if(left1 > right2) high = cut1-1;
else low = cut1+1;
}
return 0.0;
}
};
https://leetcode.com/problems/container-with-most-water/

class Solution {
public:
int maxArea(vector<int>& h) {
// Initialise the two pointers.
int L = 0;
int R = h.size() - 1;

// Variable to store the max_amt possible.

int max_amt = 0;

while(L < R) {
// Calculate the area of the current container.
int area = (R - L) * (min(h[L], h[R]));

// Update max_amt.
max_amt = max(max_amt, area);

// Increment L if h[L] is less than or equal to h[R].

if (h[L] <= h[R]) {
L += 1;
}
// Otherwise decrement R.
else {
R -= 1;
}
}

// Return the maximum area of the container.

return max_amt;
}
};

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {

int r=grid.size();
int c=grid[0].size();

int dp[r][c];
int sum=0;
for(int i=0;i<c;i++)
 {
sum+=grid[0][i];
dp[0][i]=sum;

}
sum=0;
for(int i=0;i<r;i++)
{
sum+=grid[i][0];
dp[i][0]=sum;
}

for(int i=1;i<r;i++)
{
for(int j=1;j<c;j++)
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];

}
}

return dp[r-1][c-1];

}
};

https://leetcode.com/problems/robot-return-to-origin/description/

class Solution {
public:
bool judgeCircle(string moves) {
int hor=0,ver=0;
for(auto i:moves)
{
if(i=='U')
ver++;
else if(i=='D')
ver--;
else if(i=='R')
hor++;
else
hor--;
}
return hor==0 && ver==0;
}
};
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
unordered_set <char> st;
int cnt = 0;
for (auto j : jewels) st.insert(j);
for (auto s : stones) {
if (st.find(s) != st.end()) cnt++;
}
return cnt;
}
};

https://leetcode.com/problems/nim-game/description/

class Solution {
public:
bool canWinNim(int n) {
if(n%4==0)
return false;
else
return true;

}
};

https://leetcode.com/problems/zigzag-conversion/description/

class Solution {
public:
string convert(string s, int numRows) {
vector<vector<char>> arr(numRows);
string m;
int c=0;
int i=0;
int j=0;
int z=0;
while(c<s.size()){
for(;i<numRows && c<s.size();i++){
arr[i].push_back(s[z]);
z++;
c++;
}
for(i=numRows-2;i>0 && c<s.size();i--){
 arr[i].push_back(s[z]);
z++;
c++;
}
i=0;
}
for(i=0;i<numRows;i++){
for(j=0;j<arr[i].size();j++){
m+=arr[i][j];
}
}
return m;
}
};

https://leetcode.com/problems/burst-balloons/

class Solution {
public:

int solve(int i,int j ,vector<int>& nums,vector<vector<int>>&dp)

{
if(i>j) return 0;

if(dp[i][j]!=-1) return dp[i][j];

int mincost = INT_MIN;

for(int indx = i;indx<=j;indx++)
{
int cost = nums[i-1]*nums[indx]*nums[j+1]+solve(i,indx-
1,nums,dp)+solve(indx+1,j,nums,dp);
mincost = max(mincost,cost);
}
return dp[i][j] = mincost;

int maxCoins(vector<int>& nums) {

int n = nums.size();
nums.push_back(1);
 nums.insert(nums.begin(),1);

//vector<vector<int>>dp(n+2,vector<int>(n+2,-1));
//return solve(1,n,nums,dp);

vector<vector<int>>dp(n+2,vector<int>(n+2,0));

for(int i=n;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
if(i>j) continue;
int mincost = INT_MIN;
for(int indx = i;indx<=j;indx++)
{
int cost = nums[i-1]*nums[indx]*nums[j+1]+dp[i][indx-1]+ dp[indx+1][j];
mincost = max(mincost,cost);
}
dp[i][j] = mincost;
}
}
return dp[1][n];
}
};

https://leetcode.com/problems/water-bottles/description/?envType=daily-question&envId=2024-07-07

int numWaterBottles(int nb, int ne) {

int drink = nb;
while(nb>=ne){
drink += nb/ne;
nb = nb/ne + nb%ne;
}
return drink;}

class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
int n=numBottles;
int k=numExchange;
return n+(n-1)/(k-1);

}
};
class Solution {
public:
bool threeConsecutiveOdds(vector<int>& arr) {

if(arr.size()<=2)
return 0;

for(int i=0;i<arr.size()-2;i++)
{
if(arr[i]%2!=0&&arr[i+1]%2!=0&&arr[i+2]%2!=0)
return 1;
}
return 0;
}
};

https://leetcode.com/problems/h-index/

class Solution {
public:
int hIndex(vector<int>& citations) {
if (citations.size() == 1) {
if (citations[0] >= 1) {return 1;}
}
sort(citations.begin(), citations.end());
int left = 1, right = citations.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (citations[citations.size() - mid] >= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left - (citations[citations.size() - left] >= left ? 0 : 1);
}
};

https://leetcode.com/problems/h-index-ii/

class Solution {
public:
 int hIndex(vector<int>& citations) {

int left=0;
int right=citations.size()-1;
int ans=0;
int n=citations.size();

while(left<=right)
{
int mid=left+(right-left)/2;
int idx=citations.size()-mid;
if(citations[mid]==0)
{
left=mid+1;
}
else
{
if(citations[mid]<=idx)
{left=mid+1;
ans=max(ans,citations[mid]);
}
else{
right=mid-1;
ans=max(ans,n-mid);
}
}
}

return ans;

}
};

https://leetcode.com/problems/bitwise-and-of-numbers-range/

class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int count = 0;
while (left != right) {
left >>= 1;
 right >>= 1;
count++;
}
return (left << count);
}
};

https://leetcode.com/problems/self-dividing-numbers/

class Solution {
public:
vector<int> selfDividingNumbers(int left, int right) {
vector<int>res;
for(int i=left; i<=right; i++){
int y = i;
bool flag =1;
while(y > 0){
int n = y % 10;
if(!n || i % n !=0){
flag = 0;
break;
}
y = y / 10;
}
if(flag) res.push_back(i);
}
return res;
}
};

https://leetcode.com/problems/count-and-say/

class Solution {
public:
string countAndSay(int n) {
if( n==1)return "1";
if( n==2)return "11";
string s="11";
for( int i=3;i<=n;i++){
string t="";
s=s+"-";
int c=1;
for( int j=1;j<s.length();j++){
if(s[j]!=s[j-1]){
t=t+to_string(c);
t=t+s[j-1];
c=1;
 }
else c++;

}
s=t;
}
return s;
}
};

https://leetcode.com/problems/stone-game/description/

https://leetcode.com/problems/knight-probability-in-chessboard/

https://leetcode.com/problems/cherry-pickup/description/

https://leetcode.com/problems/brick-wall/description/

https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/?envType=daily-
question&envId=2024-07-08

class Solution
{
public:
int findTheWinner(int n, int k)
{
if (n == 1)
return 1;
return (findTheWinner(n - 1, k) + k - 1) % n + 1;
}
};

class Solution {
public:
int findTheWinner(int n, int k) {
queue<int> q;
for(int i=1;i<=n;i++)
q.push(i);
while(q.size() > 1){
int i = 0;
while(i < k-1){
int top = q.front();
q.pop();
q.push(top);
i++;
 }
q.pop();
}
return q.front();
}
};

class Solution {
public:
bool wordPattern(string pattern, string s) {
map<string,int> mp;
vector<string> v;
string str="";
for(int i=0; i<s.size(); i++){
if(i==s.size()-1) str+=s[i];
if(i==s.size()-1 || s[i]==' '){
v.push_back(str);
str="";
}
else str+=s[i];

}
if(v.size()!=pattern.size()) return false;
map<char,int> p;
for(int i=0; i<pattern.size(); i++){
p[pattern[i]] =i;
}
for(int i=0; i<v.size(); i++){
mp[v[i]] = i;
}
if(p.size()!=mp.size()) return false;
map<char,string> match;
for(int i=0; i<pattern.size(); i++){
if(match.find(pattern[i])!=match.end()){
if(match[pattern[i]]!=v[i]) return false;
}
match[pattern[i]] = v[i];
}
return true;
}
};

class Solution {
bool valid(vector<vector<int>>& image,int i,int j,int curr){
int m=image.size(),n=image[0].size();
if(i<m && j<n && i>=0 && j>=0 && curr==image[i][j]) return true;
return false;
}
public:
vector<vector<int>> dfs(vector<vector<int>>& image,int i,int j,int curr,int color){
image[i][j]=color;
if(valid(image,i+1,j,curr)) dfs(image,i+1,j,curr,color);

if(valid(image,i-1,j,curr)) dfs(image,i-1,j,curr,color);

if(valid(image,i,j+1,curr)) dfs(image,i,j+1,curr,color);

if(valid(image,i,j-1,curr)) dfs(image,i,j-1,curr,color);

return image;
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color){

int i=sr,j=sc;
int m=image.size(),n=image[0].size();

if(image[sr][sc]==color) return image;

int curr=image[sr][sc];

return dfs(image,i,j,curr,color);
}
};

class Solution {
public:
void rotate(vector<int>& nums, int k) {
k=k%nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());

}
};

class Solution {
public:
bool backspaceCompare(string s, string t) {
 string s_temp;
string t_temp;
for (auto c : s)
{
if (c == '#')
{
if (!s_temp.empty())
s_temp.pop_back();
}
else
s_temp.push_back(c);
}

for (auto c : t)
{
if (c == '#')
{
if (!t_temp.empty())
t_temp.pop_back();
}
else
t_temp.push_back(c);
}

return s_temp == t_temp;

}
};

class Solution {
public:
void solve(unordered_map<int,Employee*> &mp,int &s,int &sum){
sum += mp[s]->importance;
for(auto &i: mp[s]->subordinates){
solve(mp,i,sum);
}
}
int getImportance(vector<Employee*> &emp, int &id) {
unordered_map<int,Employee*> mp;
for(auto &i: emp){
mp[i->id] = i;
}
int sum = 0;
solve(mp,id,sum);
return sum;
}
};
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];

// x2 <= x3 when R1 is on the left of R2 and they do not intersect

// x4 <= x1 when R2 is on the left of R1 and they do not intersect
if(x2 <= x3 || x4 <= x1)
return false;

// y2 <= y3 when R2 is above R1 and they do not intersect

// y4 <= y1 when R1 is above R2 and they do not intersect
if (y2 <= y3 || y4 <= y1)
return false;

// Pathetic conditions added for when the rectangle is just a line

if(x1 == x2 || x3 == x4 || y1 == y2 || y3 == y4)
return false;

return true;
}
};

class Solution {
public:

int height(TreeNode* root){

if(root == nullptr) return 0;

int l = height(root->left);
int r = height(root->right);

if(l == -1 || r == -1) return -1;

if(abs(l-r) > 1) return -1;

return 1 + max(l,r);
}

bool isBalanced(TreeNode* root) {

if(root == nullptr) return true;

int a = height(root);

if(a == -1) return false;

 return true;

}
};

class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> map;
for(auto e:magazine)
map[e]++;

for(auto i:ransomNote)
{
if(map[i]>0)
{
map[i]--;
}
else
return false;
}
return true;
}
};

class Solution {
public:
bool rotateString(string s, string goal) {
if(s.length() != goal.length()) {
return false;
}
string rotated = s + s;
return rotated.find(goal)!=string::npos;
}
};

class Solution {
public:
vector<int> ans;
void call(TreeNode * root)
{
if(!root)
return;
 call(root->left);
ans.push_back(root->val);
call(root->right);

}
bool findTarget(TreeNode* root, int k) {

if(root==NULL || root->left==NULL && root->right==NULL)

return false;

call(root);

int r=ans.size()-1;
int l=0;
while(l<r)
{
int temp=ans[l]+ans[r];
if(temp==k)
return true;
else if(temp>k)
r--;
else
l++;
}
return false;

}
};

class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {

if(!root)
return 0;

if(root->val >= low && root->val <= high )

return root->val+rangeSumBST(root->left,low,high)+rangeSumBST(root-
>right,low,high);

if(root->val < low)

return rangeSumBST(root->right,low,high);

return rangeSumBST(root->left,low,high);

}
};
class Solution {
public:
string mostCommonWord(string paragraph, vector<string>& banned) {
unordered_set<string>ban;
for(auto it:banned){
ban.insert(it);
}
unordered_map<string,int>freq;
string ans=""; int max_freq=0;

for(int i=0;i<paragraph.size();i++){
string word="";
while(i<paragraph.size() && isalpha(paragraph[i])){
word+=(tolower(paragraph[i]));

i++;
}
if(ban.find(word)==ban.end() && !word.empty()){
freq[word]++;

if(freq[word]>max_freq){
ans=word;
max_freq=freq[word];
}
}
}
return ans;
}
};

class Solution {
public:
int removeElement(vector<int>& nums, int val) {

int k=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=val)
{
nums[k]=nums[i];
k++;
}
}
return k;
 }
};

https://leetcode.com/problems/max-consecutive-ones/

class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {

int i=0,j=0,n=nums.size(),c=0,ans=0;

while(j<n)
{
if(nums[j]==1)
{
c++;
}
else
{
ans=max(ans,c);
c=0;

}
j++;

return max(ans,c);

};

class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {

if(p==NULL && q==NULL)

return true;
else if(p==NULL || q==NULL)
return false;
 else if(p->val !=q->val)
return false;
else
return (isSameTree(p->left,q->left) && isSameTree(p->right,q->right));

}
};

class Solution {
public:
int minDepth(TreeNode* root) {
if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else if(root->left==NULL)
return 1+minDepth(root->right);
else if(root->right==NULL)
return 1+minDepth(root->left);
else
return 1+min(minDepth(root->left),minDepth(root->right));
}
};

class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
map<char, char> hash;
for(int i=0; i<26; i++){
char c = 'a'+i;
hash[order[i]] = c;

}
string prev = "";

for(auto w: words){
string curr = "";
for(char c: w){
curr += hash[c];
}

if(prev > curr){

return false;
}
prev = curr;
}
 return true;
}
};

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> st;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
{
st.push(i);
}
else if(s[i]==')')
{
if( !st.empty() && s[st.top()]=='(' )
{
st.pop();
}
else
st.push(i);
}

while(!st.empty())
{
s.erase(st.top(),1);
st.pop();
}
return s;
}
};

https://leetcode.com/problems/perfect-squares/

class Solution {
public:
int numSquares(int n) {

vector<int> dp(n+1);
 if(n<=3)
return n;

dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=3;

for(int i=4;i<=n;i++)
{
dp[i]=i;

for(int j=1;j*j <= n;j++)

{
if((i-j*j)>=0)
dp[i]=min(dp[i],1+dp[i-j*j]);
}
}
return dp[n];

}
};

https://leetcode.com/problems/unique-binary-search-trees/

class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0]=1,dp[1]=1;

for(int i=2;i<=n;i++)
{
dp[i]=0;
for(int j=0;j<i;j++)
{
dp[i]+=dp[j]*dp[i-j-1];
}
}
return dp[n];

}
};

https://leetcode.com/problems/permutations-ii/

class Solution {
public:
void cal(vector<int> &nums,vector<vector<int>> &ans,int index)
{
 if(index==nums.size())
{
ans.push_back(nums);
return ;
}
unordered_set<int> s;
for(int i=index ;i<nums.size();i++)
{
if(s.find(nums[i])==s.end())
{
s.insert(nums[i]);
swap(nums[i],nums[index]);
cal(nums,ans,index+1);
swap(nums[i],nums[index]);
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans ;

cal(nums,ans,0);

return ans;

}
};

https://leetcode.com/problems/counting-bits/description/

class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n+1);
ans[0]=0;
for(int i=1;i<=n;i++)
{
if(i%2==0)
{
ans[i]=ans[i/2];
}
else
ans[i]=1+ans[i/2];

return ans;
 }
};

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {

int N=nums.size();

int sum=0;
for(int i=0;i<N;i++)
sum+=nums[i];

int tar=(sum+target)/2;

if(sum<target || (sum+target)%2!=0)
return 0;

int a[N+1][tar+1];

for(int i=0;i<=N;i++)
a[i][0]=1;
for(int j=1;j<=tar;j++)
a[0][j]=0;

for(int i=1;i<=N;i++)
{
for(int j=1;j<=tar;j++)
{
if(j<nums[i-1])
a[i][j]=a[i-1][j];
else
a[i][j]=a[i-1][j]+a[i-1][j-nums[i-1]];
}
}

return a[N][tar];

}
};
https://leetcode.com/problems/subsets/

class Solution {
public:
void cal(vector<int> &nums,vector<vector<int>> & ans, vector<int> tmp,int index)
{
ans.push_back(tmp);

for(int i=index;i<nums.size();i++)
{
tmp.push_back(nums[i]);
cal(nums,ans,tmp,i+1);
tmp.pop_back();

}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> tmp;
cal(nums,ans,tmp,0);
return ans;

}
};

class Solution {

public:
set<vector<int>> st;
void cal(vector<int> &nums,vector<int> &tmp,int index)
{
st.insert(tmp);
if(index>=nums.size())
return;

for(int i=index;i<nums.size();i++)
{
tmp.push_back(nums[i]);
cal(nums,tmp,i+1);
tmp.pop_back();

}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ans;
 vector<int> tmp;
cal(nums,tmp,0);

for(auto i:st)
ans.push_back(i);

return ans;
}
};

class NumArray {
public:
vector<int> prefix;
NumArray(vector<int>& nums) {
prefix.resize(nums.size(),0);

prefix[0]=nums[0];
for(int i=1;i<nums.size();i++)
{
prefix[i]=nums[i]+prefix[i-1];
}
}

int sumRange(int left, int right) {

if(left==0)
return prefix[right];

else
return prefix[right]-prefix[left-1];

}
};

https://leetcode.com/problems/unique-email-addresses/description/

class Solution {
public:
int numUniqueEmails(vector<string>& emails) {
unordered_set<string> st;
for(string &email : emails) {
string cleanEmail;
for(char c : email) {
if(c == '+' || c == '@') break;
if(c == '.') continue;
 cleanEmail += c;
}
cleanEmail += email.substr(email.find('@'));
st.insert(cleanEmail);
}
return st.size();
}
};

https://leetcode.com/problems/factorial-trailing-zeroes/description/

class Solution {
public:
int trailingZeroes(int n) {
int res=0;
for(int i=5;i<=n;i=i*5){
res=res+n/i;
}
return res;
}
};

class Solution {
public:
int trailingZeroes(int n) {
int res=0;
while(n>0)
{
res+=n/5;
n=n/5;
}
return res;
}
};

class Solution {
public:
int compareVersion(string v1, string v2) {
int n1 = v1.length(), n2 = v2.length();
for(int i=0,j=0;i<n1 || j<n2;){
string s1 = "", s2 = "";
while(i<n1 && v1[i] != '.') s1+=v1[i++];
while(j<n2 && v2[j] != '.') s2+=v2[j++];
int x = 0, y = 0;
if(s1 != "") x = stoi(s1);
if(s2 != "") y = stoi(s2);
 if(x<y) return -1;
else if(x>y) return 1;
i++; j++;
}
return 0;
}
};

https://leetcode.com/problems/word-break/

class Solution {
public:
bool solve(int start, int end, string &s, set<string> &st,
vector<vector<int>> &dp) {
if(dp[start][end]!=-1)
return dp[start][end]==1 ? true : false ;
if (end == s.size() - 1) {
if (st.find(s.substr(start, end - start + 1)) != st.end())
return true;

return false;
}

if (st.find(s.substr(start, end - start + 1)) != st.end()) {

if (solve(end + 1, end + 1, s, st,dp)) {
dp[start][end]=1;
return true;
}
}
dp[start][end]=solve(start, end + 1, s, st,dp) ? 1 : 0;
return dp[start][end];
}

bool wordBreak(string s, vector<string>& wordDict) {

set<string> st;
vector<vector<int>> dp(s.size(),vector<int>(s.size(),-1));
for (auto &i : wordDict)
st.insert(i);
return solve(0, 0, s, st,dp);
}
};

https://leetcode.com/problems/word-break-ii/description/
class Solution {
public:
void solve(int start, int end, string &s, vector<string> &cur, vector<string>
&ans, set<string> &set) {
if (end == s.size() - 1) {
if (set.find(s.substr(start, end + 1 - start)) != set.end()) {
cur.push_back(s.substr(start, end + 1 - start));
string tmp;
for (const auto& word : cur) {
if (!tmp.empty()) tmp += " ";
tmp += word;
}
ans.push_back(tmp);
cur.pop_back();
}
return;
}

if (set.find(s.substr(start, end + 1 - start)) != set.end()) {

cur.push_back(s.substr(start, end + 1 - start));
solve(end + 1, end + 1, s, cur, ans, set);
cur.pop_back();
}
solve(start, end + 1, s, cur, ans, set);
}

vector<string> wordBreak(string s, vector<string>& wordDict) {

vector<string> ans, cur;
set<string> set;
for (auto i : wordDict) {
set.insert(i);
}
solve(0, 0, s, cur, ans, set);
return ans;
}
};

https://leetcode.com/problems/word-ladder/description/

class Solution {
public:
int ladderLength(string s, string t, vector<string>& w) {
set<string>st;
for(int i=0;i<w.size();i++){
st.insert(w[i]);
 }
queue<pair<string,int>>q;
q.push({s,0});
st.erase(s);
while(!q.empty()){
auto curr=q.front();
string str=curr.first;
int d=curr.second;
q.pop();
if(str==t) return d+1;
for(int i=0;i<str.length();i++){
string t=str;
for(char it='a';it<='z';it++){
t[i]=it;
if(st.count(t)){
st.erase(t);
q.push({t,d+1});

}
}
}
}
return 0;
}
};

class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

vector<vector<int>> ans;

if(root==NULL)
return ans;

queue<TreeNode*>q;
q.push(root);
int c=0;
while(!q.empty())
{
int size=q.size();
vector<int> temp;
c++;
while(size--)
{
TreeNode* curr=q.front();
temp.push_back(curr->val);
 q.pop();
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right) ;

}
if(c%2==0)
reverse(temp.begin(),temp.end());

ans.push_back(temp);
}

return ans;

}
};

https://leetcode.com/problems/regular-expression-matching/

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] ||
(i && dp[i - 1][j] &&
(s[i - 1] == p[j - 2] || p[j - 2] == '.')
);
}
else if(i>0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
https://leetcode.com/problems/remove-k-digits/description/

class Solution {
public:
string removeKdigits(string num, int k) {
string res = "";
stack<char> st;
for (auto ch : num) {
while (!st.empty() && st.top() > ch && k > 0) {
st.pop();
k--;
}
st.push(ch);
}

while (k > 0) {
st.pop();
k--;
}

while (!st.empty()) {
res += st.top();
st.pop();
}

while (res.size() > 0 && res.back() == '0') {

res.pop_back();
}

reverse(res.begin(), res.end());
return res.empty() ? "0" : res;
}
};

https://leetcode.com/problems/reconstruct-itinerary/description/

class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string , multiset<string>>adj;
vector<string>ans;
int n = tickets.size();
for(int i=0; i<n; i++){
adj[tickets[i][0]].insert(tickets[i][1]);
}
stack<string>temp;
temp.push("JFK");
while(!temp.empty()){
 string src = temp.top();
if(adj[src].size()==0){
ans.push_back(src);
temp.pop();
}else{
auto dist = adj[src].begin();
temp.push(*dist);
adj[src].erase(dist);
}
}

reverse(ans.begin(),ans.end());

return ans;
}
};

https://leetcode.com/problems/trim-a-binary-search-tree/description/

class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root == NULL)
return NULL;

if(root->val <low)
return trimBST(root->right,low,high);

else if(root->val > high )

return trimBST(root->left,low,high);

root->left=trimBST(root->left,low,high);
root->right=trimBST(root->right,low,high);

return root;

}
};

https://leetcode.com/problems/minimum-operations-to-write-the-letter-y-on-a-grid/

class Solution {
public:
 int fun(vector<vector<int>>& grid, int Y,int nonY){
int ans=0,n=grid.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i<=n/2 && (i==j || i+j==n-1)) || (i>n/2 && j==n/2)){
if(grid[i][j]!=Y){ans++;}
}
else{

if(grid[i][j]!=nonY){ans++;}
}
}
}
return ans;
}
int minimumOperationsToWriteY(vector<vector<int>>& grid) {
int
ans=min({fun(grid,0,1),fun(grid,0,2),fun(grid,1,2),fun(grid,1,0),fun(grid,2,1),fun(gr
id,2,0)});
return ans;
}
};

https://www.geeksforgeeks.org/minimize-cost-of-painting-n-houses-such-that-adjacent-houses-have-different-
colors/

https://leetcode.com/problems/candy/

class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
vector<int>candies(n,1);
for(int i=1;i<n;i++){
if(ratings[i-1]<ratings[i]){
candies[i]=candies[i-1]+1;
}
}
for(int i=n-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
candies[i]=max(candies[i],candies[i+1]+1);
}
}
int candy=0;
for(auto it:candies){
candy+=it;
 }
return candy;
}
};

https://leetcode.com/problems/pass-the-pillow/description/

class Solution {
public:
int passThePillow(int n, int time) {
int cycle=time/(n-1);
int r=time%(n-1);
if(cycle%2 ==0)
return r+1;
else
return n-r;

}
};

https://leetcode.com/problems/ipo/description/

class Solution {
public:

int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital)

{

priority_queue<pair<int,int>>maxpq;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>mi
npq;
for(int i=0;i<profits.size();i++){
minpq.push({capital[i],profits[i]});
}

while(k--){
while(!minpq.empty() && minpq.top().first<=w){
maxpq.push({minpq.top().second,minpq.top().first});
minpq.pop();
}

if(!maxpq.empty()){
w+=maxpq.top().first;
maxpq.pop();
}
 else{
break;
}
}
return w;
}
};

https://leetcode.com/problems/student-attendance-record-i/

class Solution {
public:
bool checkRecord(string s) {
int lc=0;
int a=0;
for(auto c:s)
{
if(c=='A')
{
a++;
if(a>=2)
return false;
}
if(c=='L')
{
lc++;
if(lc>=3)
return false;
}
else
{
lc=0;

}
}
return true;

}
};

https://leetcode.com/problems/student-attendance-record-ii/

class Solution {
public:
int MOD;
int dp[100001][3][3];
int fun(int idx , int n ,int _a , int _l ){
if(dp[idx][_a][_l]!=-1)
return dp[idx][_a][_l];

if(idx==n)
return 1;

int ans=0;

if(_a==0)
ans=fun(idx+1, n,_a+1,0);

if(_l<2)
ans= (ans%MOD +fun(idx+1,n,_a,_l+1)%MOD)%MOD;

ans= (ans%MOD +fun(idx+1,n,_a,0)%MOD )%MOD;

return dp[idx][_a][_l]=ans;

}
int checkRecord(int n) {
MOD= pow(10,9)+7;
memset(dp , -1 , sizeof(dp));
return fun(0,n,0,0);
}
};

https://leetcode.com/problems/magnetic-force-between-two-balls/

class Solution {
private:
bool isPossible(int dist,vector<int> &position,int m){
int numBalls = 1;
int last = position[0];
for(int i=1;i<position.size();i++){
if(position[i]-last >= dist){
numBalls++;
last = position[i];
if(numBalls >= m){
return true;
}
}
}
return false;
}
public:
int maxDistance(vector<int>& position, int m) {
 int n = position.size();
sort(position.begin(),position.end());

int s = 1;
int e = position.back()-position[0];
int ans = 1;
while(s<=e){
int mid = s + (e-s)/2;
if(isPossible(mid,position,m)){
ans = mid;
s = mid + 1;
}
else{
e = mid - 1;
}
}
return ans;
}
};

https://leetcode.com/problems/rotate-array/description/

class Solution {
public:
void rotate(vector<int>& nums, int k) {
k=k%nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());

}
};

https://leetcode.com/problems/valid-palindrome/

class Solution {
public:
bool isPalindrome(string s) {
int start=0;
int end=s.size()-1;
while(start<=end){
if(!isalnum(s[start])){start++; continue;}
if(!isalnum(s[end])){end--;continue;}
if(tolower(s[start])!=tolower(s[end]))return false;
else{
 start++;
end--;
}
}
return true;
}
};

https://leetcode.com/problems/remove-duplicates-from-sorted-array-
ii/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i =0;

for(auto ele : nums)

{
if(i==0 || i==1 || nums[i-2] != ele)
{
nums[i] = ele;
i++;
}
}
return i ;
}
};

https://leetcode.com/problems/length-of-last-word/?envType=study-plan-v2&envId=top-
interview-150

class Solution {
public:
int lengthOfLastWord(string s) {
int length = 0;
bool counting = false;

for (int i = s.length() - 1; i >= 0; i--) {

if (s[i] != ' ') {
counting = true;
length++;
}
else if (counting) {
break;
}
 }

return length;
}
};

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-
string/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.length() < needle.length()) {
return -1;
}

for (int i = 0; i <= haystack.length() - needle.length(); i++) {

if (haystack.substr(i, needle.length()) == needle) {
return i;
}
}

return -1;
}
};

class Solution {
public:
bool isSubsequence(string s, string t) {
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s[sIndex] == t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex == s.length();
}};

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
return solve(board);
}
bool solve(vector<vector<char>>& board){
for(int i=0;i<board.size();i++){
 for(int j=0;j<board[0].size();j++){
if(board[i][j]!='.'){
if(!isvalid(board,board[i][j],i,j))
return false;
}
}
}
return true;
}
bool isvalid(vector<vector<char>>& board,char ch,int row,int col){
int c=0;
for(int i=0;i<9;i++){
if( board[i][col]==ch && row!=i)
return false;
if(board[row][i]==ch && col!=i)
return false;
if(board[3*(row/3)+i/3][3*(col/3)+i%3]==ch
&& row!=3*(row/3)+i/3 && col!=3*(col/3)+i%3)
return false;
}

return true;
}

};

class Solution {
public:
int jump(vector<int>& nums) {
int cover=0,idx=0,jumps=0;
int d=nums.size()-1;
if(nums.size()==1)
return 0;

for(int i=0;i<nums.size();i++)
{
cover=max(cover,i+nums[i]);

if(i==idx)
{
idx=cover;
jumps++;

if(cover>=d)
return jumps;
 }
}

return jumps;

}
};

https://leetcode.com/problems/wiggle-subsequence/description/

class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {

if(nums.size()<2)
return nums.size();

int pre=nums[1]-nums[0];
int dif;
int c;
if(pre!=0)
c=2;
else
c=1;

for(int i=2;i<nums.size();i++)
{
dif=nums[i]-nums[i-1];

if((dif > 0 && pre <= 0) || (dif < 0 && pre >= 0))
{
pre=dif;
c++;
}

}
return c;

}
};

https://leetcode.com/problems/longest-consecutive-sequence/

class Solution {
public:
 int longestConsecutive(vector<int>& nums) {
int cur,res=0;
unordered_set<int> s(nums.begin(),nums.end());
for(auto x :s)
{
if(s.find(x-1)==s.end())
{ cur=1;
while(s.find(x+cur)!=s.end())
cur++;
res=max(cur,res);
}
}
return res;

}
};

https://leetcode.com/problems/binary-tree-right-side-view/

class Solution {
public:
void cal(TreeNode *root,int level,vector<int> &ans)
{
if(!root)
return ;

if(ans.size()<level)
ans.push_back(root->val);

cal(root->right,level+1,ans);
cal(root->left,level+1,ans);
}
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
cal(root,1,ans);
return ans;

}
};

https://leetcode.com/problems/longest-palindromic-substring/

class Solution {
public:
string solve(int i, int j, string &s)
{
while(i>=0 && j<s.length() && s[i]==s[j])
 {
i--;
j++;
}
return s.substr(i+1,j-i-1);
}
string longestPalindrome(string s)
{
string str = s.substr(0,1);
int mx = 1;
for(int i=0;i<s.length()-1;i++)
{
string even = solve(i,i+1,s);
string odd = solve(i,i,s);
if(even.length()>mx)
{
mx = even.length();
str = even;
}
if(odd.length()>mx)
{
mx = odd.length();
str = odd;
}
}
return str;
}
};

https://leetcode.com/problems/binary-tree-cameras/description/

class Solution {
public:
int c=0;
string cal(TreeNode * root)
{
if(!root)
return "ok";

string l=cal(root->left);
string r=cal(root->right);

if(l=="want" || r=="want")
{
c++;
return "provide";
 }
else if(l=="provide" || r=="provide")
{
return "ok";
}
return "want";
}
int minCameraCover(TreeNode* root) {

if(cal(root)=="want")
c++;

return c;

}
};

https://leetcode.com/problems/triangle/description/

class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n=triangle.size();
vector<int> dp (n,0);

for(int i=0;i<n;i++)
dp[i]=triangle[n-1][i];

for(int i=n-2;i>=0;i--)
{
for(int j=0;j<triangle[i].size();j++)
{
dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
}
}

return dp[0];

}
};

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

class Solution {
public:
int minOperations(vector<int>& nums, int x) {

int summ=accumulate(nums.begin(),nums.end(),0);
if(summ==x)
return nums.size();
int sum_make=summ-x;
int s=0,e=0,n=nums.size();
int sum=0;
int ans=0;
while(e<n)
{
sum+=nums[e];

while(s<e && sum>sum_make)

{
sum-=nums[s];
s++;
}

if(sum==sum_make)
{
ans=max(ans,e-s+1);
}

e++;

}
return ans==0 ? -1 : nums.size()-ans;

}
};

https://leetcode.com/problems/valid-triangle-number/description/

class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
int c=0;
for(int i=n-1;i>=0;i--)
{
int l=0,r=i-1;
while(l<r)
 {
if(nums[l]+nums[r]>nums[i])
{
c+=(r-l);

r--;
}
else
l++;

}
}
return c;

}
};

https://leetcode.com/problems/last-stone-weight/

class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq;
for(auto i:stones)
{
pq.push(i);
}
while(pq.size()>1)
{
int x=pq.top();
pq.pop();
int y=pq.top();
pq.pop();
if(x>y)
pq.push(x-y);
}
return pq.size()>0 ? pq.top() : 0;

}
};

https://leetcode.com/problems/minimum-right-shifts-to-sort-the-array/

class Solution {
public:
int minimumRightShifts(vector<int>& nums) {
int pivot;
 int n=nums.size();
int c=0;
for(int i=1;i<n;i++)
{
if(nums[i-1]>nums[i])
{
c++;
pivot=i;

}
}

if(c>1)
return -1;
else if(c==0)
return 0;
else
return (nums[n-1]>nums[0]) ? -1 : n-pivot;

}
};

https://leetcode.com/problems/diameter-of-binary-tree/

int cal(TreeNode* root, int &ans)

{
if(root==NULL)
return 0;

int l=cal(root->left,ans);
int r=cal(root->right,ans);
ans=max(ans,l+r);
return 1+max(l,r);

int diameterOfBinaryTree(TreeNode* root) {

if(root->left==NULL && root->right==NULL)

return 0;

int dia=0;

cal(root,dia);

return dia;
 }
};

https://leetcode.com/problems/min-stack/

class MinStack {
public:
MinStack() {

}
stack<int> s1,s2;

void push(int val) {

if(s2.empty() || s2.top()>=val)
s2.push(val);

s1.push(val);

void pop() {
if(s2.top()==s1.top())
{
s2.pop();
}
s1.pop();
}

int top() {
return s1.top();
}

int getMin() {
return s2.top();
}
};

https://leetcode.com/problems/pacific-atlantic-water-flow/

class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {

vector<vector<int>>ans;
if(matrix.size()<1)return ans;
 vector<vector<int>>pacific(matrix.size(),vector<int>(matrix[0].size(),0));
vector<vector<int>>atlantic(matrix.size(),vector<int>(matrix[0].size(),0));

for(int col=0;col<matrix[0].size();col++)
{
fnc(matrix,0,col,INT_MIN,pacific);
fnc(matrix,matrix.size()-1,col,INT_MIN,atlantic);

for(int row = 0;row<matrix.size();row++)

{
fnc(matrix,row,0,INT_MIN,pacific);
fnc(matrix,row,matrix[0].size()-1,INT_MIN,atlantic);
}

for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(pacific[i][j]==1 && atlantic[i][j]==1)
{
vector<int>v(2);
v[0]=i;
v[1]=j;
ans.push_back(v);
}
}
}

return ans;
}

void fnc(vector<vector<int>>& matrix,int i, int j,int prev,vector<vector<int>>&

ocean)
{
if(i<0 || j<0 || i>=matrix.size() || j>=matrix[0].size())
return;
if(ocean[i][j]==1)
return;
if(matrix[i][j]<prev)
return;

ocean[i][j]=1;

fnc(matrix,i+1,j,matrix[i][j],ocean);
 fnc(matrix,i-1,j,matrix[i][j],ocean);
fnc(matrix,i,j+1,matrix[i][j],ocean);
fnc(matrix,i,j-1,matrix[i][j],ocean);

};

https://leetcode.com/problems/sort-array-by-increasing-frequency/?envType=daily-
question&envId=2024-07-23

class Solution {
public:

vector<int> frequencySort(vector<int>& nums) {

map<int,int>mp;
for(int i=0;i<nums.size();i++)
{
mp[nums[i]]++;
}
sort(nums.begin(),nums.end(),[&](int x,int y){
if(mp[x]==mp[y])
return x>y;
else
return mp[x]<mp[y];
});
return nums;
}
};

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {

int m=matrix.size();
int n=matrix[0].size();
int start=0;
int end=m*n-1;

while(start<=end)
{

int mid=(start+end)/2;
int mid_ele=matrix[mid/n][mid%n];
 if(target==mid_ele)
return true;
else if(target>mid_ele)
start=mid+1;
else
end=mid-1;
}

return false;

}
};

/*

1 3 5 7 10 11 16 20 23 30 34 60
00 01 02 03 10 11 12 13 20 21 22 23

tar=3

mid=6

row=6/4->1

col=6%4->2

*/

https://leetcode.com/problems/search-a-2d-matrix-ii/

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int r=0,c=matrix[0].size()-1;
while(r<matrix.size() && c>=0)
{
if(matrix[r][c]==target)
return true;
else if(matrix[r][c]>target)
c--;
else
 r++;
}
return false;

}
};

https://leetcode.com/problems/find-a-peak-element-ii/

class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& matrix) {
int i=0,j=0;
while(i<matrix.size() && j<matrix[0].size())
{
if(i-1>=0 && matrix[i-1][j]>matrix[i][j])
i--;
else if(j-1>=0 && matrix[i][j-1]>matrix[i][j])
j--;
else if(i+1<matrix.size() && matrix[i+1][j]>matrix[i][j])
i++;

else if(j+1<matrix[0].size() && matrix[i][j+1]>matrix[i][j])

j++;
else
{
vector<int> ans={i,j};
return ans;
}

}
vector<int> emp;
return emp;

}
};

https://leetcode.com/problems/count-good-numbers/

class Solution {
public:
const long mod = 1e9 + 7;

long long myPow(long long x, long long n) {

if (n == 0)
return 1;
 if (n % 2 == 0) {
return myPow(x * x % mod, n / 2)%mod;

} else {
return x * myPow(x * x % mod, (n - 1) / 2) % mod;
}
}

int countGoodNumbers(long long n) {

long long e = (n + 1) / 2;
long long o = n / 2;
long long ans = (myPow(5, e) % mod) * (myPow(4, o) % mod) % mod;
return (int)ans;
}
};

/*
[0, 2, 4, 6, 8] = even
[2, 3, 5, 7] = prime
*/

https://leetcode.com/problems/count-complete-tree-nodes/description/

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
right(right) {}
* };
*/
class Solution {
public:
int LDepth(TreeNode *root)
{
int d=0;
while(root!=NULL)
{
d++;

root=root->left;
}
 return d;
}
int RDepth(TreeNode *root)
{
int d=0;
while(root!=NULL)
{
d++;
root=root->right;
}
return d;
}
int countNodes(TreeNode* root) {
if(!root)
return 0;
int l=LDepth(root);
int r=RDepth(root);

if(l==r)
return (int) pow(2,l)-1;
else
{
return 1+countNodes(root->left)+countNodes(root->right);
}

}
};

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

class Solution {
public:
TreeNode *prev;
void pre(TreeNode* cur)
{
if(cur==NULL)
return ;

if(prev)
{
prev->left=NULL;
prev->right=cur;
}

TreeNode* r=cur->right;
 prev=cur;

pre(cur->left);
pre(r);

}
void flatten(TreeNode* root) {
prev=NULL;
pre(root);
return ;

}
};

https://leetcode.com/problems/bus-routes/

class Solution {
public:
// time/space: O(V + E)/O(V + E);
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
// base case
if (source == target) return 0;

// build the graph (bus as node, bus-transfer as edge)

// the hash table for `stop2bus`, and the `bus2stop` is the `routes`
unordered_map<int, unordered_set<int>> stop2bus;
for (int bus = 0; bus < routes.size(); bus++) {
for (auto& stop : routes[bus]) stop2bus[stop].insert(bus);
}

// start from the buses which pass the bus stop `source`
queue<int> q;
unordered_set<int> bus_taken;
for (auto& bus : stop2bus[source]) {
q.push(bus);
bus_taken.insert(bus);
}

// BFS
int step = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int bus = q.front();
q.pop();
 for (auto& next_stop : routes[bus]) {
if (next_stop == target) return step;
for (auto& next_bus : stop2bus[next_stop]) {
if (bus_taken.count(next_bus) != 0) continue;
bus_taken.insert(next_bus);
q.push(next_bus);
}
}
}
step++;
}

// unreachable
return -1;
}
};

https://leetcode.com/problems/isomorphic-strings/description/

class Solution {
public:
bool isIsomorphic(string s, string t) {
vector<int> smap(256,0);
vector<int> tmap(256,0);

for(int i=0;i<s.size();i++)
{
if(smap[s[i]]!=tmap[t[i]])
return false;
smap[s[i]]=i+1;
tmap[t[i]]=i+1;

return true;

}
};

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-
array/description/

class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int total_sum=0;
 int n=nums.size();
for(int i=0; i<n; i++)total_sum+=nums[i];
vector<int> ans;
int curr_sum=0;
for(int i=0; i<n; i++){
curr_sum+=nums[i];
int Rsum=total_sum-curr_sum;
int Lsum=curr_sum-nums[i];
Lsum=(i*nums[i])-Lsum;
Rsum=Rsum-(n-(i+1))*nums[i];
ans.push_back(Lsum+Rsum);
}
return ans;
}
};

https://leetcode.com/problems/count-of-matches-in-tournament/description/

class Solution {
public:
int numberOfMatches(int n) {
int c=0,adv;
while(n>1)
{
if(n%2==0)
{
c+=n/2;
adv=n/2;

}
else
{
c+=(n-1)/2;
adv=(n-1)/2+1;
}
n=adv;
}
return c;

}
};

https://leetcode.com/problems/count-nice-pairs-in-an-array/description/

class Solution {
public:
 int rev(int n) {
int reverse = 0;
while (n > 0) {
reverse = reverse * 10 + n % 10;
n = n / 10;
}
return reverse;
}

int countNicePairs(vector<int>& nums) {

int result = 0;
int MOD = 1e9 + 7;
unordered_map<int, int> frequency;

for (int i = 0; i < nums.size(); i++) {

nums[i] -= rev(nums[i]);
frequency[nums[i]]++;
}

for (auto i : frequency) {

long long n = i.second;
result += ((n * (n - 1))/2) % MOD;
}

return result % MOD;

}
};

/*
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
*/

https://leetcode.com/problems/bulb-switcher/

int bulbSwitch(int n) {
return sqrt(n);
}

Odd pairs on

https://leetcode.com/problems/assign-cookies/

class Solution {
public:
 int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int i=g.size()-1;
int j=s.size()-1;
int c=0;
while(i>=0 && j>=0)
{
if(g[i]<=s[j])
{
c++;
i--;
j--;
}
else
{
i--;
}
}
return c;

}
};

https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/

class Solution {
public:
int minMovesToSeat(vector<int>& seats, vector<int>& students) {
sort(seats.begin(),seats.end());
sort(students.begin(),students.end());
int c=0;
for(int i=0;i<seats.size();i++)
{
c+=abs(seats[i]-students[i]);
}
return c;

}
};

https://leetcode.com/problems/count-number-of-nice-subarrays/

class Solution {
public:
int solve(vector<int>&nums , int k)
{
 int s=0,e=0,n=nums.size(),c=0,ans=0;
while(e<n)
{
if(nums[e]%2!=0)
{
c++;
}
while(s<=e && c>k)
{
if(nums[s]%2!=0)
{
c--;
}
s++;
}
ans+=(e-s+1);
e++;

}
return ans;
}
int numberOfSubarrays(vector<int>& nums, int k) {

return solve(nums,k)-solve(nums,k-1);

}
};

https://leetcode.com/problems/palindrome-partitioning/description/

class Solution {
private:
bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) {
return false;
}
}
return true;
}

void solve(string s, int start, vector<string> &substr, vector<vector<string>>

&ans) {
if (start == s.length()) {
ans.push_back(substr);
return;
}
 for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
substr.push_back(s.substr(start, i - start + 1));
solve(s, i + 1, substr, ans);
substr.pop_back(); // Backtrack
}
}
}

public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> substr;
solve(s, 0, substr, ans);
return ans;
}
};

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

class Solution {
public:
//int dp[31][10001]={-1};

const int mod=1e9+7;

int solve(int n,int k,int target,vector<vector<int>> &dp)
{
if(target<0)
return 0;

if(n==0)
return target==0;

if(dp[n][target]!=-1)
return dp[n][target];

long ans=0;

for(int f=1;f<=k;f++)
{
ans+=solve(n-1,k,target-f,dp)%mod;
}
dp[n][target]=ans % mod;

return dp[n][target];
}
int numRollsToTarget(int n, int k, int target) {
vector<vector<int>> dp(n+1,vector<int>(target+1,-1));
return solve(n,k,target,dp);

}
};

https://leetcode.com/problems/sort-the-jumbled-numbers/?envType=daily-
question&envId=2024-07-24

Largest Smaller BST Key

int findLargestSmallerKey(Node *rootNode, int num)

{
// your code goes here
int res=-1;
if(rootNode==NULL)
return -1;

while(rootNode!=NULL)
{
if(rootNode->key < num)
{
res=rootNode->key;
rootNode=rootNode->right;
}
else
{
rootNode=rootNode->left;
}
}
return res;
}

https://leetcode.com/problems/path-with-maximum-gold/

class Solution {
public:

int solve(vector<vector<int>> &grid,int i,int j)

{
int r=grid.size(),c=grid[0].size();
 if(i<0 || j<0 || i>=r || j>=c || grid[i][j]==0)
return 0;

int tmp=grid[i][j];
int ans=0;
grid[i][j]=0;
ans=max(ans,solve(grid,i+1,j));
ans=max(ans,solve(grid,i-1,j));
ans=max(ans,solve(grid,i,j+1));
ans=max(ans,solve(grid,i,j-1));
grid[i][j]=tmp;

return tmp+ans;
}
int getMaximumGold(vector<vector<int>>& grid) {
int ans=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]!=0)
{
ans=max(ans,solve(grid,i,j));
}
}
}
return ans;

}
};

https://leetcode.com/problems/sort-an-array/?envType=daily-question&envId=2024-07-25

class Solution {

void merge(vector<int>& nums, int low, int mid, int high) {

vector<int> temp;
int left = low;
int right = mid + 1;
while (left <= mid && right <= high){
if(nums[left]<=nums[right]){
temp.push_back(nums[left++]);
}else{
temp.push_back(nums[right++]);
}
}
 while(left<=mid){
temp.push_back(nums[left++]);
}
while(right<=high){
temp.push_back(nums[right++]);
}
for(int i=low;i<=high;i++){
nums[i]=temp[i-low];
}
}
void mergeSort(vector<int>& nums, int low, int high) {
if (low == high)
return;
int mid = (low + high) / 2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}

public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
};

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
class Solution {
public:

void merge(int left, int mid, int right, vector<pair<int, int>>& arr,vector<int>&
count)
{
vector<pair<int, int>> temp(right - left + 1);

int i = left;
int j = mid + 1;
int k = 0;
int n1=mid-left+1;

while(i <= mid && j <= right)

{
if(arr[i].first <= arr[j].first)
{
temp[k++] = arr[j++];
}
else
 {
count[arr[i].second] += (right - j + 1);

temp[k++] = arr[i++];
}
}

while(i <= mid)

{
temp[k++] = arr[i++];
}

while(j <= right)

{
temp[k++] = arr[j++];
}

for(int l = left; l <= right; l++)

arr[l] = temp[l - left];

void mergeSort(int left, int right, vector<pair<int, int>>& arr, vector<int>&

count)
{
if(left >= right)
{
return;
}

int mid = left + (right - left) / 2;

mergeSort(left, mid, arr, count);

mergeSort(mid + 1, right, arr, count);

merge(left, mid, right, arr, count);

}

vector<int> countSmaller(vector<int>& nums) {

int n=nums.size();
vector<pair<int, int>> arr;

for(int i = 0; i < n; i++)

{
arr.push_back({nums[i], i});
}
 vector<int> count(n, 0);

mergeSort(0, n - 1, arr, count);

return count;
}

};

https://takeuforward.org/data-structure/count-inversions-in-an-array/

https://leetcode.com/problems/can-make-arithmetic-progression-from-
sequence/description/

class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end(), greater<int>());
int diff = arr[0] - arr[1];
for(int i = 1; i < (int)arr.size() - 1; i++){
if (diff != (arr[i] - arr[i + 1])){
return false;
}
}
return true;
}
};
class Solution {
public:
bool isPowerOfFour(int n) {
if(n == 0) return false;
if(n == 1) return true;
while(n>1 || n<1){
if(n%4 != 0) return false;
else n/=4;
}
return true;
}

};

https://leetcode.com/problems/average-waiting-time/

class Solution {
public:
 double averageWaitingTime(vector<vector<int>>& customers) {
int idleTime=1;
double waitTime=0;
for(auto c:customers)
{
if(idleTime<=c[0])
{
idleTime=c[0]+c[1];
}
else
{
idleTime=idleTime+c[1];
}
waitTime+=idleTime-c[0];
}
return (double) waitTime/customers.size();

}
};

https://leetcode.com/problems/course-schedule/description/

class Solution {
public:
bool canFinish(int n, vector<vector<int>>& pre) {
unordered_map<int,vector<int>> m;
vector<int> indegree(n,0);
for(auto it :pre)
{
m[it[1]].push_back(it[0]);
indegree[it[0]]++;
}
queue<int> q;
for(int i=0;i<n;i++)
{
if(indegree[i]==0)
q.push(i);
}
vector<int> topo;
while(!q.empty())
{
int node=q.front();
topo.push_back(node);
q.pop();
for(auto it: m[node])
{
indegree[it]--;
 if(indegree[it]==0)
q.push(it);
}
}

return topo.size()==n?1:0;
}
};

DFS:

void dfs(int node, vector<int> &vis, vector<int> adj[], vector<int> &storeDfs) {

storeDfs.push_back(node);
vis[node] = 1;
for(auto it : adj[node]) {
if(!vis[it]) {
dfs(it, vis, adj, storeDfs);
}
}

https://leetcode.com/problems/possible-bipartition/description/

class Solution {
public:
bool isBipartite(vector<vector<int>>& adj,int n,int node,vector<int> &color)
{
//queue for BFS traversal
queue<int> q;
q.push(node);
color[node]=1;//color the node to find number of edges
while(!q.empty()){
int curr=q.front();
q.pop();
//check neighbours of current node
for(int it:adj[curr]){
if(color[it]==color[curr])
//and if we find ambiguity we return false
return false;
//if it color is 1 color it 0 and vice versa
if(color[it]==-1){
color[it]=1-color[curr];
q.push(it);
 }
}
}
return true;
}
bool possibleBipartition(int n,vector<vector<int>>& dislikes) {
vector<vector<int>> adjlist(n+1);
//making adjancency list
for(int i=0;i<dislikes.size();i++){
adjlist[dislikes[i][0]].push_back(dislikes[i][1]);
adjlist[dislikes[i][1]].push_back(dislikes[i][0]);
}
//color to find out even or odd edges
vector<int> color(n+1,-1);
for(int i=0;i<n;i++){
if(color[i]==-1){ //if node is not colored then only we will call BFS
if(!isBipartite(adjlist,n,i,color))
return false;
}
}
return true;
}
};
https://leetcode.com/problems/find-the-town-judge/

class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> in(n+1);
vector<int> out(n+1);
for(auto e:trust)
{
out[e[0]]++;
in[e[1]]++;

}
for(int i=1;i<=n;i++)
{
if(in[i]==n-1 && out[i]==0)
return i;
}
return -1;

}
};
class Solution {
public:
int findCenter(vector<vector<int>>& edges) {
int n=edges.size()+1;
vector<int> in(n+1);

for(auto e:edges)
{
in[e[0]]++;
in[e[1]]++;
}
for(int i=1;i<=in.size();i++)
{
if(in[i]==n-1)
return i;
}

return -1;
}
};

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/

class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
vector<int> ans;
vector<int> in(n,0);
for(auto e:edges)
{
in[e[1]]++;
}
for(int i=0;i<n;i++)
{
if(in[i]==0)
ans.push_back(i);
}
return ans;
}
};

https://leetcode.com/problems/count-servers-that-communicate/description/

class Solution {
public:
void dfs(vector<vector<int>> &grid,int i,int j ,int r,int c,int &temp)
{
if(i<0 || j<0 || i>=r || j>=c )
return;

grid[i][j]=0;

temp++;

for(int x=0;x<r;x++)
{
if( grid[x][j]==1)
dfs(grid,x,j,r,c,temp);

for(int y=0;y<c;y++)
{
if(grid[i][y]==1)
dfs(grid,i,y,r,c,temp);

return;

}
int countServers(vector<vector<int>>& grid) {

int ans=0;

int r=grid.size();
int c=grid[0].size();

for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
int temp=0;

if(grid[i][j]==1)
{
dfs(grid,i,j,r,c,temp);
if(temp>1)
ans+=temp;
}
}
 }
return ans;

}
};

https://leetcode.com/problems/redundant-connection/

class Solution {
public:
vector<int> par, rank;
int findPar(int u) {
if(u == par[u])
return u;
return par[u] = findPar(par[u]);
}

void findUnion(int u, int v) {

u = findPar(u);
v = findPar(v);
if(rank[u] > rank[v]) {
par[v] = u;
rank[u]++;
}
else if(rank[u] < rank[v]) {
par[u] = v;
rank[v]++;
}
else {
par[u] = v;
rank[v]++;
}
}

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

int n = edges.size();
par.resize(n+1);
rank.resize(n+1);
for(int i=1;i<=n;i++)
par[i] = i;
vector<int> ans;
for(auto &x : edges) {
int u = x[0], v = x[1];
if(findPar(u) == findPar(v)) {
ans = {u, v};
}
else {
 findUnion(u, v);
}
}
return ans;
}
};

https://leetcode.com/problems/satisfiability-of-equality-equations/

class Solution {
private:
vector<int> parent, rank;
int find(int c){
if(parent[c] == c) return c;
return parent[c] = find(parent[c]);
}
void unionn(int c1,int c2){
int p1 = find(c1), p2 = find(c2);
if(p1 == p2) return;
if(rank[p1] > rank[p2]){
parent[p2] = p1;
}else if(rank[p1] < rank[p2]){
parent[p1] = p2;
}else{
parent[p2] = p1;
rank[p1]++;
}
}
public:
bool equationsPossible(vector<string>& arr) {
parent.resize(26), rank.resize(26);
sort(arr.begin(),arr.end(),[&](auto &a, auto &b){return a[1] > b[1];});
for(int i=0;i<26;i++) parent[i] = i;
for(auto it : arr){
int c1 = it[0]- 'a';
char type = it[1];
int c2 = it[3] - 'a';
if(type == '='){
unionn(c1,c2);
}else{
if(find(c1) == find(c2)) return false;
}
}
return true;
}
};
https://leetcode.com/problems/evaluate-division/

class Solution {
public:
void dfs(string& a,string &b,map<string,int>& vis,
map<string,vector<pair<string,double>>>& adj,double ans,double& val)
{
vis[a] = 1;
if(a==b)
{
val = ans;
return;
}
for(auto &i:adj[a])
{
if(vis.find(i.first)==vis.end())
{
dfs(i.first,b,vis,adj,ans*i.second,val);
}
}
}
vector<double> calcEquation(vector<vector<string>>& equ, vector<double>& values,
vector<vector<string>>& q) {
map<string,vector<pair<string,double>>> adj;
int n = values.size();
for(int i=0;i<n;i++)
{
string a = equ[i][0];
string b = equ[i][1];
double val = values[i];
adj[a].push_back({b,val});
adj[b].push_back({a,1.0/val});
}
map<string,int> vis;
vector<double> fans;
for(int i=0;i<q.size();i++)
{
double ans = -1.0;
string a = q[i][0];
string b = q[i][1];
if(adj.find(a)!=adj.end())
{
double val = -1.0;
ans = 1;
dfs(a,b,vis,adj,ans,val);
ans = val;
}
fans.push_back(ans);
 vis.clear();
}
return fans;
}
};

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-
product/description/

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int maxx=0;
for(int i=0;i<nums.size();i++)
{

int negativeCount=0,positiveCount=0,firstNegative=-1,lastNegative=-1,j;
for(j=i;j<nums.size();j++)
{
if(nums[j]<0)
negativeCount++;
else if(nums[j]>0)
positiveCount++;
else
break;
if(nums[j]<0 && firstNegative==-1)
firstNegative=j;
if(nums[j]<0)
lastNegative=j;
}

if(negativeCount%2==0)
maxx=max(positiveCount+negativeCount,maxx);
else
maxx=max(maxx,max(j-firstNegative-1,lastNegative-i));

i=j;

}
return maxx;
}
};

https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-
a-threshold-distance/description/?envType=daily-question&envId=2024-07-26

class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<int> > dis(n, vector<int>(n, 1e8));
for(int i = 0; i < n; i++){
dis[i][i] = 0;
}
for(auto it: edges){
dis[it[0]][it[1]] = it[2];
dis[it[1]][it[0]] = it[2];
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dis[i][k]!=1e8 && dis[k][j]!=1e8)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}
}
}
int ans = 0;
int cnt_sum = INT_MAX;
for(int i = 0; i < n; i++){
int cnt = 0;
for(int j = 0; j < n; j++){
if(dis[i][j] <= distanceThreshold) cnt++;
}

if(cnt <= cnt_sum){

ans = i;
cnt_sum = cnt;
}
}

return ans;
}
};

https://leetcode.com/problems/broken-calculator/

class Solution {
public:
int brokenCalc(int startValue, int target) {
int ans=0;

while(startValue!=target)
{
if(target%2==0)
{
 if(target>startValue)
target=target/2;
else
target++;

ans++;
}
else
{
target++;
ans++;
}

return ans;

}
};

https://leetcode.com/problems/minimum-cost-to-convert-string-
i/description/?envType=daily-question&envId=2024-07-27
class Solution {
public:

long long minimumCost(string source, string target, vector<char>& original,

vector<char>& changed, vector<int>& cost) {

int n = cost.size();
vector<vector<long long>> v(26, vector<long long>(26, INT_MAX));
for(int i = 0; i < 26; i++) v[i][i] = 0;
for(int i = 0; i < n; i++){
int k = v[original[i] - 'a'][changed[i] - 'a'];
v[original[i] - 'a'][changed[i] - 'a'] = min(k, cost[i]);
}

for(int k = 0; k < 26; k++){

for(int i = 0; i < 26; i++){
for(int j = 0; j < 26; j++){
if( v[i][j] > (v[i][k] + v[k][j])){
v[i][j] = v[i][k] + v[k][j];
}
}
}
}

long long ans = 0;

 for(int i = 0; i < source.size(); i++){
long long k = v[source[i] - 'a'][target[i] - 'a'];
if(k == INT_MAX) return -1;
ans += k;
}

return ans;
}
};

https://leetcode.com/problems/super-egg-drop/

class Solution {
public:
int find(int k,int n,vector<vector<int>> &memo)
{ if(n==0||n==1) return n;
if(k==1) return n;
if(memo[k][n]!=-1) return memo[k][n];
int ans=1000000,l=1,h=n,temp=0;

while(l<=h)
{
int mid=(l+h)/2;
int left=find(k-1,mid-1,memo);
int right=find(k,n-mid,memo) ;
temp=1+max(left,right);
if(left<right){
l=mid+1;
}
else
{
h=mid-1;
}
ans=min(ans,temp);
}

return memo[k][n]=ans;

}
int superEggDrop(int K, int N) {

vector<vector<int>> memo(K+1,vector<int> (N+1,-1));

return find(K,N,memo);

}
};
https://leetcode.com/problems/minimum-deletions-to-make-string-
balanced/description/?envType=daily-question&envId=2024-07-30

class Solution {
public:
int minimumDeletions(string s) {
int n = s.length();
vector<int> suff(n, 0); //ount of 'a's from the end
vector<int> pre(n, 0); // count of 'b's from the start

int countb = 0, counta = 0;

for (int i = 0; i < n; i++) {

if (s[i] == 'b') countb++;
pre[i] = countb;
}

for (int i = n - 1; i >= 0; i--) {

if (s[i] == 'a') counta++;
suff[i] = counta;
}

int ans = INT_MAX;

for (int i = 0; i <= n; i++) {

int leftb = (i > 0) ? pre[i - 1] : 0;
int righta = (i < n) ? suff[i] : 0;
ans = min(ans, leftb + righta);
}

return ans;
}
};

https://leetcode.com/problems/filling-bookcase-shelves/description/?envType=daily-
question&envId=2024-07-31

class Solution {
public:
int solve(int ind, vector<vector<int>>& books, int remWidth, int maxH, int
shelfWidth, vector<vector<int>>& dp){
//basecase
if(ind>=books.size()) return maxH;
 if(dp[ind][remWidth]!=-1) return dp[ind][remWidth];

int bookT = books[ind][0];

int bookH = books[ind][1];
//if i keep
int keep = INT_MAX;
if(bookT<=remWidth) keep = solve(ind+1, books, remWidth-bookT, max(maxH,
bookH), shelfWidth, dp);

//if i not keep

int notKeep = INT_MAX;
notKeep = maxH + solve(ind+1, books, shelfWidth-bookT, bookH, shelfWidth, dp);

return dp[ind][remWidth] = min(keep, notKeep);

int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {

vector<vector<int>> dp(books.size(), vector<int>(shelfWidth+1,-1));
int remWidth = shelfWidth;
return solve(0, books, remWidth, 0, shelfWidth, dp);
}
};
https://leetcode.com/problems/task-scheduler/

class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {

int freq[26] = {0};

for (char &ch: tasks) freq[ch-'A']++;
priority_queue<int> pq;
for (int i=0; i<26; i++) {if (freq[i] > 0 ) pq.push(freq[i]);}

int time=0;
while (!pq.empty()) {
int cycle = n+1;
vector<int> store;

int temp = 0;
while (cycle-- && !pq.empty()) {
if (pq.top() > 1)
store.push_back(pq.top()-1);

pq.pop();
temp++;
 }
for (int &x: store) pq.push(x);
time += (pq.empty() ? temp : n+1);

}
return time;
}
};

https://leetcode.com/problems/critical-connections-in-a-network/

class Solution {
public:
int timer = 1;
void dfs(int node,int parent,vector<int> adj[],vector<int>& vis,vector<int>&
tin,vector<int>& low,vector<vector<int>>& bridges){
vis[node] = 1;
tin[node] = low[node] = timer;
timer++;
for(auto it : adj[node]){
if(it == parent) continue;

if(!vis[it]){
dfs(it,node,adj,vis,tin,low,bridges);
low[node] = min(low[node],low[it]);

// Can this edge (node--it) be a bridge?

if(low[it] > tin[node]) bridges.push_back({it,node});
}
else low[node] = min(low[node],low[it]);
}
}

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections)

{

vector<int> adj[n];
for(int i = 0 ; i < connections.size() ; i++){
int u = connections[i][0];
int v = connections[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}

vector<vector<int>> bridges;
vector<int> vis(n, 0);
vector<int> tin(n);
 vector<int> low(n);
dfs(0,-1,adj,vis,tin,low,bridges);

return bridges;
}
};

https://leetcode.com/problems/robot-collisions/description/

class Solution {
public:

vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths,

string directions) {
int n=positions.size();
vector<int> indexes(n);
vector<int> ans;
stack<int> st;

for(int i=0; i<n; i++){

indexes[i]=i;
}

auto comp = [&positions](int l, int r) {

return positions[l] < positions[r];
};
sort(indexes.begin(), indexes.end(), comp);

for(int currIndex : indexes){

if(directions[currIndex]=='R'){
st.push(currIndex);
}
else{
while(!st.empty() && healths[currIndex]>0){
int top=st.top();
st.pop();
 if(healths[top]>healths[currIndex]){
healths[top]-=1;
healths[currIndex]=0;
st.push(top);
}
else if(healths[top]<healths[currIndex]){
healths[currIndex]-=1;
healths[top]=0;
}

else{
healths[currIndex]=0;
healths[top]=0;
}
}
}
}

for (int index = 0; index < n; ++index) {

if (healths[index] > 0) {
ans.push_back(healths[index]);
}
}
return ans;

}
};

https://leetcode.com/problems/reaching-points/description/

class Solution {
public:
 int solve(vector<int>& satisfaction, vector<vector<int>>& dp, int index, int time)
{
if (index == satisfaction.size())
return 0;
if (dp[index][time] != -1)
return dp[index][time];
int include = satisfaction[index] * (time + 1) + solve(satisfaction, dp,
index + 1, time + 1);
int exclude = solve(satisfaction, dp, index + 1, time);
int ans = max(include, exclude);
dp[index][time] = ans;
return dp[index][time];
}

int maxSatisfaction(vector<int>& satisfaction) {

int n = satisfaction.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
sort(satisfaction.begin(), satisfaction.end());
return solve(satisfaction, dp, 0, 0);
}
};

https://leetcode.com/problems/knight-probability-in-chessboard/

class Solution {
public:

vector<pair<int, int>>moves={{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1},
{2, -1}, {1, -2}};
double solve(int row, int col, int n, int k, vector<vector<vector<double>>>
&dp){
if(row<0 || col<0 || row>=n || col>=n) return 0.0;
if(k==0) {
return 1.0;
}
 if(dp[k][row][col]!=-1) return dp[k][row][col];
double ans=0;
for(auto it:moves){
int nrow=row+it.first;
int ncol=col+it.second;
ans=ans+solve(nrow, ncol, n, k-1, dp);
}
return dp[k][row][col]=ans/8;
}
double knightProbability(int n, int k, int row, int column) {
vector<vector<vector<double>>>dp(k+1, vector<vector<double>>(n,
vector<double>(n, -1)));
return solve(row, column, n, k, dp);
}
};

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-
ii/?envType=daily-question&envId=2024-08-02

class Solution {
public:
int minSwaps(vector<int>& nums) {
vector<int> temp(2*nums.size());

for(int i=0;i<2*nums.size();i++)
{
temp[i]=nums[i%nums.size()];
}
int sum=accumulate(nums.begin(),nums.end(),0);

int i=0,j=0,n=nums.size();
int csum=0,ans=0;
while(j<2*n)
{
 if(temp[j]==1)
csum++;

if(j-i+1 >sum)
{
csum-=temp[i];
i++;
}
ans=max(ans,csum);
j++;

}
return sum-ans;

}
};

https://leetcode.com/problems/single-element-in-a-sorted-array/

class Solution {
public:
int singleNonDuplicate(vector<int>& arr) {
int n = arr.size(); //size of the array.

//Edge cases:
if (n == 1) return arr[0];
if (arr[0] != arr[1]) return arr[0];
if (arr[n - 1] != arr[n - 2]) return arr[n - 1];

int low = 1, high = n - 2;

while (low <= high) {
int mid = (low + high) / 2;
 //if arr[mid] is the single element:
if (arr[mid] != arr[mid + 1] && arr[mid] != arr[mid - 1]) {
return arr[mid];
}

//we are in the left:

if ((mid % 2 == 1 && arr[mid] == arr[mid - 1])
|| (mid % 2 == 0 && arr[mid] == arr[mid + 1])) {
//eliminate the left half:
low = mid + 1;
}
//we are in the right:
else {
//eliminate the right half:
high = mid - 1;
}
}

// dummy return statement:

return -1;
}
};

https://leetcode.com/problems/house-robber-ii/

class Solution {
public:
int solve(const vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];

vector<int> dp(n);
dp[0] = nums[0];
 if (n > 1) dp[1] = max(nums[0], nums[1]);

for (int i = 2; i < n; ++i) {

dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
}

return dp[n-1];
}

int rob(vector<int>& nums) {

int n = nums.size();
if (n == 1) return nums[0];

// Rob houses from index 0 to n-2

vector<int> nums1(nums.begin(), nums.end() - 1);
// Rob houses from index 1 to n-1
vector<int> nums2(nums.begin() + 1, nums.end());

return max(solve(nums1), solve(nums2));

}
};

https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/?envType=daily-
question&envId=2024-08-04

class Solution {
public:
int primo=1e9+7;
int rangeSum(vector<int>& nums, int n, int left, int right) {
vector<int> subarraysums;
for (int start = 0; start < n; ++start) {
int sum = 0;
for (int end = start; end < n; ++end) {
sum += nums[end];
 subarraysums.push_back(sum);
}
}
sort(subarraysums.begin(), subarraysums.end());
int result = 0;
for (int i = left - 1; i < right; ++i) {
result =(result+ subarraysums[i])%primo;
}
return result;
}
};

https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-
ii/?envType=daily-question&envId=2024-08-06

class Solution {
public:
int minimumPushes(string word) {
unordered_map<char,int> map;
int ans=0;
for(auto c:word)
map[c]++;

if(map.size()>8)
{
vector<int>temp;
for(auto it=map.begin();it!=map.end();it++)
{
temp.push_back(it->second);
}
sort(temp.begin(),temp.end(),greater<>());

for(int i=0;i<temp.size();i++)
 ans=ans+temp[i]*(i/8+1);
}
else
{
for(auto it=map.begin();it!=map.end();it++)
{
ans=ans+(it->second);
}
}
return ans;
}
};

https://leetcode.com/problems/minimum-falling-path-sum/description/

class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int r = matrix.size(), c = matrix[0].size();
vector<vector<int>> dp(r, vector<int>(c, 0));

// Initialize the first row of dp with the first row of the matrix
for (int j = 0; j < c; j++) {
dp[0][j] = matrix[0][j];
}

// Fill the dp array

for (int i = 1; i < r; i++) {
for (int j = 0; j < c; j++) {
int a = INT_MAX, b = INT_MAX, current = dp[i-1][j];

// Check left diagonal

if (j - 1 >= 0) {
 a = dp[i-1][j-1];
}

// Check right diagonal

if (j + 1 < c) {
b = dp[i-1][j+1];
}

// Update dp[i][j] by adding the current matrix value to the min of

possible paths
dp[i][j] = min({a, b, current}) + matrix[i][j];
}
}

// Return the minimum value from the last row of dp

return *min_element(dp[r-1].begin(), dp[r-1].end());
}
};

https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

class Solution {
public:
int mod=1e9+7;
int dfs(vector<vector<int>>&grid,int i,int j,int sum,int
k,vector<vector<vector<int>>>&dp){

if(i<0||j<0||i>=grid.size() || j>=grid[0].size()){
return 0;
}

if(i==grid.size()-1 && j==grid[0].size()-1){

 sum+=grid[i][j];
if(sum%k==0)return 1;
return 0;
}

if(dp[i][j][sum%k]!=-1){
return dp[i][j][sum%k];
}
int down=dfs(grid,i+1,j,sum+grid[i][j],k,dp);
int right=dfs(grid,i,j+1,sum+grid[i][j],k,dp);
return dp[i][j][sum%k]=(down%mod+right%mod)%mod;
}
int numberOfPaths(vector<vector<int>>& grid, int k) {

vector<vector<vector<int>>>dp(grid.size(),vector<vector<int>>(grid[0].size(),ve
ctor<int>(k,-1)));
return dfs(grid,0,0,0,k,dp);

}
};

https://leetcode.com/problems/shortest-path-in-binary-matrix/

class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int r = grid.size(), c = grid[0].size();

if (grid[0][0] == 1 || grid[r-1][c-1] == 1) {
return -1;
 }

if (r == 1 && c == 1) {
return 1;
}

vector<vector<int>> dir {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-

1},{1,0},{1,1}};
queue<pair<pair<int, int>, int>> q;

q.push({{0, 0}, 1});

grid[0][0] = 1;

while (!q.empty()) {
auto [cell, length] = q.front();
int i = cell.first, j = cell.second;
q.pop();

for (int d = 0; d < 8; d++) {

int ni = i + dir[d][0];
int nj = j + dir[d][1];

if (ni >= 0 && ni < r && nj >= 0 && nj < c && grid[ni][nj] == 0) {

if (ni == r - 1 && nj == c - 1) {
return length + 1;
}
q.push({{ni, nj}, length + 1});
grid[ni][nj] = 1;
 }
}
}
return -1;
}
};

https://leetcode.com/problems/minimum-cost-for-cutting-cake-i/

class Solution {
public:
int minimumCost(int m, int n, vector<int>& horCut, vector<int>& verCut) {
int hs=horCut.size(),vs=verCut.size();
sort(horCut.begin(),horCut.end(),greater<>());
sort(verCut.begin(),verCut.end(),greater<>());
int hp=1,vp=1;
int i=0,j=0,ans=0;

while(i<hs && j<vs)

{
if(horCut[i]>verCut[j])
{
ans+=vp*horCut[i];
i++;
hp++;
}
else
{
ans+=hp*verCut[j];
j++;
vp++;
}
 }
while(i<hs)
{
ans+=vp*horCut[i];
i++;
hp++;
}
while(j<vs)
{
ans+=hp*verCut[j];
j++;
vp++;
}

return ans;

}
};

https://leetcode.com/problems/koko-eating-bananas/description/
class Solution {
public:

bool caneat(vector<int>piles ,int h,int mid)

{
int sum=0;
for(auto x:piles)
{
sum+=ceil((double)x/(double)mid);
 }
if(sum<=h)
return true;
else
return false;

int minEatingSpeed(vector<int>& piles, int h) {

if(piles.size()>h)
return -1;
int left=1;
int right=*max_element(piles.begin(),piles.end());

while(left<right)
{
int mid=left+(right-left)/2;

if(caneat(piles,h,mid))
right=mid;
else
left=mid+1;
}

return left;

}
};

https://leetcode.com/problems/dungeon-game/
class Solution {
int solve(vector<vector<int>> dungeon,int i,int j,int n,int m,vector<vector<int>>
& dp){

if(i>=n || j>=m)
return 1e9;

if(i==n-1 && j==m-1) {

if(dungeon[i][j]>0)
return 1;
else
return 1 - dungeon[i][j];
}
if(dp[i][j]!=1e5)
return dp[i][j];

int right = solve(dungeon,i,j+1,n,m,dp);

int bottom = solve(dungeon,i+1,j,n,m,dp);

int val = min(right,bottom) - dungeon[i][j];

if(val>0)
return dp[i][j] = val;
else
return dp[i][j] = 1;
}
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon[0].size();
int n = dungeon.size();
vector<vector<int>> dp(n,vector<int> (m,1e5));
return solve(dungeon,0,0,n,m,dp);
}
};

https://leetcode.com/problems/integer-to-english-words/description/

class Solution {
private:
vector<string> belowTen =
{"Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
vector<string> belowTwenty =
{"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eight
een","Nineteen"};
vector<string> belowHundred =
{"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

public:
string numberToWords(int num)
{
if(num == 0) return "Zero";

if(num < 10) return belowTen[num];

if(num < 20) return belowTwenty[num - 10];

if(num < 100){ // 9 9

return belowHundred[num/10] + (num % 10 != 0 ? " " + belowTen[num%10] :
"");
}

if(num < 1000){ // 9 99

return belowTen[num/100] + " Hundred" + (num % 100 != 0 ? " " +
numberToWords(num%100) : "");
}

if(num < 1000000){ // 999 999

 return numberToWords(num/1000) + " Thousand" + (num % 1000 != 0 ? " " +
numberToWords(num%1000) : "");
}

if(num < 1000000000){ // 999 999999

return numberToWords(num/1000000) + " Million" + (num % 1000000 != 0 ? "
" + numberToWords(num%1000000) : "");
}

if(num < 10000000000){ // 2 999999999

return numberToWords(num/1000000000) + " Billion" + (num % 1000000000 !=
0 ? " " + numberToWords(num%1000000000) : "");
}
return "";
}
};

https://leetcode.com/problems/cherry-pickup-ii/
class Solution {
public:
int m, n;
int dp[71][71][71];

int helper(vector<vector<int>>& grid, int row, int column1, int column2) {

if (row >= m) return 0;
if (dp[row][column1][column2] != -1) return dp[row][column1][column2];

int cherryCount = grid[row][column1];

if (column1 != column2) cherryCount += grid[row][column2];

int result = 0;
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
int newRow = row + 1;
 int newColumn1 = column1 + i;
int newColumn2 = column2 + j;
if (newColumn1 >= 0 && newColumn1 < n && newColumn2 >= 0 &&
newColumn2 < n)
result = max(result, helper(grid, newRow, newColumn1,
newColumn2));
}
}

return dp[row][column1][column2] = cherryCount + result;

}

int cherryPickup(vector<vector<int>>& grid) {

m = grid.size();
n = grid[0].size();
memset(dp, -1, sizeof(dp));
return helper(grid, 0, 0, n - 1);
}
};

https://leetcode.com/problems/sender-with-largest-word-count/description/
class Solution {
public:
string largestWordCount(vector<string>& m, vector<string>& s) {
unordered_map<string,int> mp;
int mx=INT_MIN;
string ans="";
for(int i=0;i<m.size();i++)
{
char ch=' ';
int counter=0;
counter=count(m[i].begin(),m[i].end(),ch);
mp[s[i]]+=(counter+1);
 if(mp[s[i]] == mx){
ans = max(ans ,s[i] );
}
else if(mp[s[i]] > mx){
mx = mp[s[i]];
ans = s[i];
}
}
return ans;
}
};

https://leetcode.com/problems/copy-list-with-random-pointer/
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* temp = head;
while(temp!=NULL){
Node* new_node = new Node(temp->val);
new_node->next = temp->next;
temp->next = new_node;
temp=temp->next->next;
}

temp=head;
while(temp!=NULL){
if(temp->random!=NULL){
temp->next->random=temp->random->next;
}
temp=temp->next->next;
}

Node* dummy = new Node(-1);

 Node* ptr = dummy;
temp=head;
while(temp!=NULL){
ptr->next = temp->next;
ptr=ptr->next;
temp->next=temp->next->next;
temp=temp->next;
}
return dummy->next;
}
};

https://leetcode.com/problems/spiral-matrix-iii/description/?envType=daily-
question&envId=2024-08-08

class Solution {
public:
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
vector<vector<int>> directions= {
{0,1}, //east
{1,0}, //south
{0,-1}, //west
{-1,0} //north
};

vector<vector<int>> ans;
ans.push_back({rStart,cStart});
int steps = 0;
int dir = 0;

while(ans.size()< rows*cols){
if(dir == 0 || dir == 2){
steps++;
 }

for(int i=0;i<steps;i++){
rStart += directions[dir][0];
cStart += directions[dir][1];

if(rStart>=0 && rStart<rows && cStart>=0 && cStart< cols){

ans.push_back({rStart,cStart});
}
}
dir = (dir+1)%4;
}
return ans;
}
};

https://leetcode.com/problems/rotting-oranges/
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int r = grid.size(), c = grid[0].size();
queue<pair<int, int>> q;
int freshOranges = 0;
vector<vector<int>> dir{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int minutes = 0;

// Add all rotten oranges to the queue and count fresh oranges
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
freshOranges++;
 }
}
}

while (!q.empty() && freshOranges > 0) {

int size = q.size();

while (size--) {
int i = q.front().first;
int j = q.front().second;
q.pop();

for (int k = 0; k < 4; k++) {

int ni = i + dir[k][0];
int nj = j + dir[k][1];

if (ni >= 0 && ni < r && nj >= 0 && nj < c && grid[ni][nj] == 1)
{
grid[ni][nj] = 2;
q.push({ni, nj});
freshOranges--;
}
}
}

minutes++;
}

return freshOranges == 0 ? minutes : -1;

}
};
https://leetcode.com/problems/number-of-provinces/
class Solution {
public:
void dfs(int i,vector<vector<int>>& adj,vector<bool> &vis)
{
vis[i]=true;
for(auto e:adj[i])
{
if(vis[e]==false)
dfs(e,adj,vis);
}
}
int findCircleNum(vector<vector<int>>& graph) {
int n=graph.size();
int ans=0;
vector<bool> vis(n,false);
vector<vector<int>> adj(n);
for(int i=0;i<n;i++)
{
for(int j=0;j<graph[i].size();j++)
if(i!=j && graph[i][j])
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}

for(int i=0;i<n;i++)
{
if(vis[i]==false)
{
ans++;
 dfs(i,adj,vis);
}
}

return ans;

}
};

https://leetcode.com/problems/online-stock-span/
stack<pair<int,int>> st;

int next(int price) {

int c=1;
while(!st.empty() && st.top().first<=price)
{
c=c+st.top().second;
st.pop();

}
st.push({price,c});
return c;

}
};

https://leetcode.com/problems/swap-nodes-in-pairs/

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next)
return head;
 ListNode * temp=head->next;
head->next=swapPairs(temp->next);
temp->next=head;
return temp;

}
};

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode* p1=NULL,*p2=NULL,*temp=head;
int flag=0;

while(temp)
{
if(p2)
{
p2=p2->next;
}
k--;
if(k==0 && flag==0)
{
p1=temp;
p2=head;
flag=1;
}
temp=temp->next;
}
 swap(p1->val,p2->val);

return head;

}
};

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-
array/
class Solution {
public:
int first(vector<int>& nums, int target) {
int ans = -1;
int low = 0, high = nums.size()-1;
while(low<=high) {
int mid = (low+high)/2;
if(nums[mid] == target) {
ans = mid;
high = mid-1;
}
else if(nums[mid]<target) low = mid+1;
else high = mid-1;
}
return ans;
}
int last(vector<int>& nums, int target) {
int ans = -1;
int low = 0, high = nums.size()-1;
while(low<=high) {
int mid = (low+high)/2;
if(nums[mid] == target) {
ans = mid;
 low = mid+1;
}
else if(nums[mid]<target) low = mid+1;
else high = mid-1;
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
return {first(nums,target), last(nums,target)};
}
};

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {

int left=0,right=nums.size();

while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]>=target)
right=mid;
else
left=mid+1;
}
return left;

}
};

https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
vector<pair<int, int>> adj[n]; // Create adjacency list
for (auto& nbr : roads) {
adj[nbr[0]].push_back({nbr[1], nbr[2]});
adj[nbr[1]].push_back({nbr[0], nbr[2]});
}

priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,

greater<pair<long long, long long>>> pq;
vector<long long> dist(n, LLONG_MAX);
vector<long long> ways(n, 0);
dist[0] = 0;
ways[0] = 1;
pq.push({0, 0});
const long long mod = 1e9 + 7;

while (!pq.empty()) {
long long dis = pq.top().first;
long long node = pq.top().second;
pq.pop();

for (auto& it : adj[node]) {

long long adjNode = it.first;
long long edw = it.second;

if (dis + edw < dist[adjNode]) {

dist[adjNode] = dis + edw;
pq.push({dis + edw, adjNode});
ways[adjNode] = ways[node];
} else if (dis + edw == dist[adjNode]) {
ways[adjNode] = (ways[adjNode] + ways[node]) % mod;
}
 }
}

return ways[n - 1] % mod;

}
};

https://leetcode.com/problems/path-with-maximum-probability/description/

Dijstra

class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb,
int start, int end) {
vector<double> prob(n + 1, 0.0);
vector<pair<int, double>> adj[n + 1];

for (int i = 0; i < edges.size(); i++) {

adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
}

priority_queue<pair<double, int>> pq;

pq.push({1.0, start});
prob[start] = 1.0;

while (!pq.empty()) {
int node = pq.top().second;
double node_prob = pq.top().first;
pq.pop();
 for (auto it : adj[node]) {
int neigh_node = it.first;
double neigh_prob = it.second;
double new_prob = neigh_prob * node_prob;

if (prob[neigh_node] < new_prob) {

prob[neigh_node] = new_prob;
pq.push({prob[neigh_node], neigh_node});
}
}
}

return prob[end];
}
};

https://leetcode.com/problems/network-delay-time/

class Solution {
public:
int networkDelayTime(vector<vector<int>>& edges, int n, int k) {
vector<vector<pair<int, int>>> adj(n + 1);

for (int i = 0; i < edges.size(); i++) {

adj[edges[i][0]].push_back({edges[i][1], edges[i][2]});
}

vector<int> dist(n + 1, INT_MAX);

dist[k] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,

int>>> pq;
pq.push({0, k});
 while (!pq.empty()) {
int d = pq.top().first;
int node = pq.top().second;
pq.pop();

if (d > dist[node])
continue;

for (auto e : adj[node]) {

int neighbor = e.first;
int weight = e.second;

if (d + weight < dist[neighbor]) {

dist[neighbor] = d + weight;
pq.push({dist[neighbor], neighbor});
}
}
}

int ans = *max_element(dist.begin() + 1, dist.end());

return ans == INT_MAX ? -1 : ans;
}
};

https://leetcode.com/problems/evaluate-boolean-binary-tree/description/
class Solution {
public:
bool evaluateTree(TreeNode* root) {
if(root->val==0)
return false;
 if(root->val==1)
return true;

bool l=evaluateTree(root->left);
bool r=evaluateTree(root->right);

if(root->val ==2)
return l || r;
else if(root->val==3)
return l && r;

return false;

}
};

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-
of-that-tree/description/
class Solution {
public:
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
if (cloned==NULL)
return NULL;
if (cloned->val == target->val)
return cloned;
TreeNode* leftSearch = getTargetCopy(original, cloned->left, target);
TreeNode* rightSearch = getTargetCopy(original, cloned->right, target);

if (leftSearch != NULL)
return leftSearch;
else
return rightSearch;
}
};

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/description/
`
class Solution {
public:
void k(TreeNode* root,int &sum,string &s){
if(!root) return ;
char c = '0' + root->val;
s+=c;
if(root->left==NULL && root->right==NULL){
cout<<s<<endl;
sum+=stoi(s, 0, 2);
}
k(root->left,sum,s);
k(root->right,sum,s);
s.pop_back();
}
int sumRootToLeaf(TreeNode* root) {
int sum=0;
string s="";
k(root,sum,s);
return sum;
}
};

class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if(!root)
return 0;
if(root->val >= low && root->val <= high )
 return root->val+rangeSumBST(root->left,low,high)+rangeSumBST(root-
>right,low,high);

if(root->val < low)

return rangeSumBST(root->right,low,high);

return rangeSumBST(root->left,low,high);

}
};

https://leetcode.com/problems/search-in-a-binary-search-tree/description/

class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {

if(!root)
return NULL;

if(root->val ==val)
return root;

if(root->val > val)

return searchBST(root->left,val);

return searchBST(root->right,val);

}
};

https://leetcode.com/problems/coin-change/
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {

int N=coins.size();

int dp[N+1][amount+1];
for(int i=0;i<=amount;i++)
dp[0][i]=1e5;
for(int j=0;j<=N;j++)
dp[j][0]=0;

for(int i=1;i<=N;i++)
{
for(int j=1;j<=amount;j++)
{
if(j<coins[i-1])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=min(1+dp[i][j-coins[i-1]],dp[i-1][j]);
}
}

return dp[N][amount]>1e4?-1:dp[N][amount];

}
};

https://leetcode.com/problems/coin-change-ii/

class Solution {
public:
int change(int amount, vector<int>& coins) {
 int N=coins.size();
int dp[N+1][amount+1];
for(int i=0;i<=amount;i++)
dp[0][i]=0;

for(int i=0;i<=N;i++)
dp[i][0]=1;

for(int i=1;i<=N;i++)
{
for(int j=1;j<=amount;j++)
{
if(j<coins[i-1])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
}
}

return dp[N][amount];

}
};

https://leetcode.com/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/

class Solution {
public:

void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& visited, bool

&ans){
 if(i>=grid.size() || j>=grid[0].size() || ans==1 || grid[i][j]==0 || visited[i][j]
== 1)
return;
if(i==grid.size()-1 && j==grid[0].size()-1){
ans = 1;
return;
}

visited[i][j] = 1;

dfs(grid, i+1, j, visited, ans);

dfs(grid, i, j+1, visited, ans);
}

bool isPossibleToCutPath(vector<vector<int>>& grid) {

int n= grid.size() , m = grid[0].size();
vector<vector<int>> visited(n, vector<int>(m, 0) );

bool ans1=0, ans2 = 0;

dfs(grid, 0, 0, visited, ans1);

visited[0][0] = 0;

dfs(grid, 0, 0, visited, ans2);

if(ans1&&ans2)
return 0;
return 1;
}
};

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-
island/?envType=daily-question&envId=2024-08-11
class Solution {
public:

void dfs(int i, int j,vector<vector<int>>& grid, vector<vector<bool>> &vis){

if(i<0 || j<0 || i>=grid.size() || j>= grid[0].size() || grid[i][j] == 0 ||
vis[i][j] == true) return;
vis[i][j] = true;
dfs(i+1,j,grid,vis);
dfs(i,j+1,grid,vis);
dfs(i-1,j,grid,vis);
dfs(i,j-1,grid,vis);
}

int count_islands(vector<vector<int>>& grid){

vector<vector<bool>> vis(grid.size(), vector<bool>(grid[0].size(),false));
int cnt =0 ;
for(int i=0; i<grid.size(); i++){
for(int j=0; j<grid[i].size(); j++){
if(grid[i][j] == 1 && !vis[i][j]){
cnt++;
dfs(i,j,grid,vis);
}
}
}
return cnt;
}
int minDays(vector<vector<int>>& grid) {
if(count_islands(grid) == 0 || count_islands(grid)> 1) return 0;

for(int i=0; i<grid.size(); i++){

for(int j=0;j<grid[i].size(); j++){
if(grid[i][j] == 1){
 grid[i][j] = 0;
int cnt = count_islands(grid);
if(cnt > 1 || cnt == 0) return 1;
else grid[i][j] = 1;
}
}
}
return 2;
}
};

https://leetcode.com/problems/make-the-string-great/

class Solution {
public:
string makeGood(string s) {
string ans;
for (const char c : s)
if (!ans.empty() && isBadPair(ans.back(), c))
ans.pop_back();
else
ans.push_back(c);
return ans;
}

bool isBadPair(char a, char b) {

return a != b && tolower(a) == tolower(b);
}
};

https://leetcode.com/problems/maximum-score-after-splitting-a-string/
class Solution {
public:
 int maxScore(string s) {
int maxScore = 0;
int zerosLeft = 0;
int onesRight = count(s.begin(), s.end(), '1');

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') {
zerosLeft++;
} else {
onesRight--;
}

int currentScore = zerosLeft + onesRight;

maxScore = max(maxScore, currentScore);
}

return maxScore;
}
};

https://leetcode.com/problems/valid-boomerang/

class Solution {
public:
bool isBoomerang(vector<vector<int>>& points) {
int x1 = points[0][0];
int x2 = points[1][0];
int x3 = points[2][0];
int y1 = points[0][1];
int y2 = points[1][1];
int y3 = points[2][1];

double area = 0.5*(x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2));

 return area==0? false: true;
}
};

https://leetcode.com/problems/occurrences-after-bigram/
class Solution {
public:
vector<string> findOcurrences(string text, string first, string second) {
vector<string> st;
string x="";
for(int i=0 ; i<text.size() ; i++)
{
if(text[i]==' '){
st.push_back(x);
x="";
}

else{
x+=text[i];
}
}
st.push_back(x);
vector<string> result;
bool flag=0;
int n=st.size();
for(int i=0 ; i<n-2 ; i++)
{
if(st[i]==first && st[i+1]==second)
result.push_back(st[i+2]);
}
return result;
}
};
https://leetcode.com/problems/check-if-n-and-its-double-exist/
class Solution {
public:
bool checkIfExist(vector<int>& arr) {
sort(arr.begin(),arr.end());

for(int i=0;i<arr.size();i++){
int s = 0, e = arr.size()-1;
int target = 2*arr[i];
while(s<=e){
int mid = s+(e-s)/2;
if((arr[mid]==target) && (i!=mid))
return true;
else if(arr[mid] > target){
e = mid-1;
}
else
s = mid+1;
}
}
return false;
}
};

https://leetcode.com/problems/unique-number-of-occurrences/
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
unordered_map<int, int> map;

for (int num : arr)

map[num]++;
 unordered_set<int> set;

for(auto it=map.begin();it!=map.end();it++)
{
if(set.find(it->second)==set.end())
{
set.insert(it->second);
}
else
return false;
}

return true;

}
};

https://leetcode.com/problems/distance-between-bus-stops/
class Solution {
public:
int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
if(start > destination )
swap(start,destination);

int clocksum=0;

int anticlocksum=0;

int total=0;

int size=distance.size();
 for(int i=0 ; i<distance.size(); i++)
{
if(i>=start && i<destination)
clocksum+=distance[i];

total+=distance[i];
}

anticlocksum=total-clocksum;

return min(clocksum,anticlocksum);

}
};

https://leetcode.com/problems/rank-transform-of-an-array/
class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr)
{

int rank=1;
map<int,vector<int>>mp;

for(int i=0;i<arr.size();i++)
{
mp[arr[i]].push_back(i);
}
vector<int>v;
for(auto it=mp.begin();it!=mp.end();it++)
{
v=it->second;
 int idx;
for(int i=0;i<v.size();i++)
{
idx=v[i];
arr[idx]=rank;
}
rank++;
}
return arr;

}
};

https://leetcode.com/problems/relative-ranks/
class Solution {
public:
static bool comp(pair<int,int> &a , pair<int,int> &b)
{
return (a.first >= b.first);

}
vector<string> findRelativeRanks(vector<int>& score) {
vector<pair<int,int>> arr;

int n = score.size();
for(int i = 0 ; i < n ; i++)
{
arr.push_back({score[i] , i});
}

sort(arr.begin() , arr.end() , comp);

vector<string> ans(n);
 for(int i = 0 ; i < n ; i++)
{

int index = arr[i].second;

if(i == 0)
{
ans[index] = "Gold Medal";
}
else if(i == 1)
{
ans[index] = "Silver Medal";
}
else if(i == 2)
{
ans[index] = "Bronze Medal";
}
else
{
ans[index] = to_string(i+1);
}
}

return ans;
}
};

https://leetcode.com/problems/detect-capital/

class Solution {
public:
bool detectCapitalUse(string word) {
if(word.size() == 1)
{
return true;
}
//Checking first Capital
if(word[0] < 'a' && word[1] > 'Z')
{
for(int i = 2;i < word.size(); i++)
{
if(word[i] < 'a')
{
return false;
}
}
return true;
}
//Checking All Capital
if(word[0] < 'a' && word[1]<'a')
{
for(int i = 2;i < word.size(); i++)
{
if(word[i] > 'Z')
{
return false;
}
}
return true;
}
//Checking all small
if(word[0] > 'Z')
{
for(int i=1;i<word.size();i++)
{
 if(word[i] < 'a')
{
return false;
}
}
return true;
}
return false;
}
};

https://leetcode.com/problems/longest-uncommon-subsequence-i/

class Solution {
public:
int findLUSlength(string a, string b) {
int m=a.length(),n=b.length();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++){
if(i==0 || j==0) dp[i][j]=0;
else if(a[i-1]==b[j-1]) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
if(dp[m][n]==m && m==n) return -1;
return max(m,n);
}
};

https://leetcode.com/problems/delete-columns-to-make-sorted/
class Solution {
public:
 int minDeletionSize(vector<string>& strs) {
int n = strs.size();
int m = strs[0].size();
int count = 0;
for(int col = 0 ; col < m ; col++){
for(int row = 0 ; row < n-1 ; row++){
if(strs[row][col] > strs[row+1][col]){
count++;
break;
}
}
}
return count;
}
};

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& arr) {

int rank = 0;

map<int, vector<int>> mp;

for (int i = 0; i < arr.size(); i++)

{
mp[arr[i]].push_back(i);

}
vector<int> v;
 for (auto it = mp.begin(); it != mp.end(); it++)
{
v = it->second;

int idx;
int c = 0;

for (int i = 0; i < v.size(); i++)

{
idx = v[i];
arr[idx] = rank;
c++;

}
if (c > 1)
rank = rank + c;
else
rank++;

}
return arr;
}
};

https://leetcode.com/problems/kth-largest-element-in-a-stream/?envType=daily-
question&envId=2024-08-12

class KthLargest {
int num;
priority_queue<int, vector<int>, greater<int>> pq;
public:
KthLargest(int k, vector<int>& nums) {
num = k;
 for(auto ele : nums) {
pq.push(ele);
if(pq.size() > k) pq.pop();
}
}

int add(int val) {

pq.push(val);
if(pq.size() > num) pq.pop();
return pq.top();
}
};

https://leetcode.com/problems/longest-palindromic-subsequence/

class Solution {
public:
int longestCommonSubsequence(string &s,string &t)
{
int n = s.length();
int m = t.length();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));

for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
if(s[i-1] == t[j-1])
{
dp[i][j] = 1 + dp[i-1][j-1];
}
else
{
 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
int longestPalindromeSubseq(string s) {
string t = s;
reverse(s.begin(),s.end());
return longestCommonSubsequence(s,t);
}
};

https://leetcode.com/problems/delete-operation-for-two-strings/description/
class Solution {
public:
int minDistance(string word1, string word2) {
int n=word1.length(),m=word2.length();
int dp[n+1][m+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0){dp[i][j]=0;}
else{
if(word1[i-1]==word2[j-1]){
dp[i][j]=1+dp[i-1][j-1];
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
}
return n+m-2*dp[n][m];
 }
};

https://leetcode.com/problems/edit-distance/description/

class Solution {
public:

int minn(int x, int y, int z)

{
return min(min(x, y), z);
}
int minDistance(string word1, string word2) {

int s1=word1.size();
int s2=word2.size();
int dp[s1+1][s2+1];

for(int i=0;i<=s1;i++)
{
for(int j=0;j<=s2;j++)
{
if(i==0)
dp[i][j]=j;

else if(j==0)
dp[i][j]=i;

else if(word1[i-1]==word2[j-1])
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=minn(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
 }
}

return dp[s1][s2];

}
};

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n=s1.length(), m=s2.length();

vector<vector<int>> dp(n+1,vector<int>(m+1,INT_MAX/2));

dp[0][0]=0;

// cost when s2 = ""

for(int i=1;i<n+1;i++){
dp[i][0]=dp[i-1][0]+s1[i-1]-'a'+97;
}

// cost when s1 = ""

for(int j=1;j<m+1;j++){
dp[0][j]=dp[0][j-1]+s2[j-1]-'a'+97;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
 if(s1[i-1] == s2[j-1]){
dp[i][j]=dp[i-1][j-1]; // cost of subsequence [i,j] = [i-1,j-1]
}else{
int delete_s1 = s1[i-1]-'a'+97 + dp[i-1][j]; // cost of
subsequence [i,j] = ASCII(ith char) + [i-1,j]
int delete_s2 = s2[j-1]-'a'+97 + dp[i][j-1]; // cost of
subsequence [i,j] = ASCII(jth char) + [i,j-1]

dp[i][j]=min(delete_s1, delete_s2);
}
}
}
return dp[n][m];
}
};

https://leetcode.com/problems/maximum-length-of-pair-chain/

class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
// sorting by left values
sort(pairs.begin(), pairs.end());

int curr_end = pairs[0][1]; // ending of the first interval

int count = 1; // including this interval to the count

for(int i = 1; i < pairs.size(); i++) {

// values for the new interval we are considering
int start = pairs[i][0];
int end = pairs[i][1];

// case 1: no collision
 if(start > curr_end) {
curr_end = end; // move end point
count++; // increment count

// case 2: collision (take smallest end point)

} else {
curr_end = min(curr_end,end);
}
}

return count;
}
};

Meeting room 1:

int prev_end=INT_MIN;
for(auto it:interval)
{
if(it[0]<prev_end)
return false;

prev_end=it[1];
}
return true

Min meeting rooms:

sort
min heap pq;
for(auto it:interval)
{
if(!pq.empty() && it[0]>=pq.top())
 pq.pop();

pq.push(it[1]);
}
return pq.size();

https://leetcode.com/problems/determine-if-two-events-have-conflict/

class Solution {
public:
bool haveConflict(vector<string>& event1, vector<string>& event2) {
if(event1[0]<=event2[0] && event2[0]<=event1[1] || event2[0]<=event1[0] &&
event1[0]<=event2[1])
return true;
return false;
}
};

https://leetcode.com/problems/find-k-th-smallest-pair-
distance/description/?envType=daily-question&envId=2024-08-14

class Solution {
public:
static int cntPairs(int x, vector<int>& nums){//sliding window
const int n=nums.size();
int cnt=0;
for(int l=0, r=1; r<n; r++){
while(r>l && nums[r]-nums[l]>x)
l++;
cnt+=r-l;
}
return cnt;
}
 static int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
const int M=nums.back();

//Binary search
int l=0, r=M, m;
while(l<r){
m=(r+l)/2;
if (cntPairs(m, nums)<k)
l=m+1;
else r=m;
}
return l;
}
};

https://leetcode.com/problems/lemonade-change/submissions/1356141283/?envType=daily-
question&envId=2024-08-15

class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fiveBills = 0;
int tenBills = 0;
for(int i = 0; i<bills.size();i++){
if(bills[i] == 5) fiveBills++;
else if(bills[i] == 10){
tenBills++;
if(fiveBills) fiveBills--;
else return false;
 }
else{
if(tenBills && fiveBills){
tenBills--;
fiveBills--;
}else if(fiveBills>=3){
fiveBills -= 3;
}
else return false;
}
}
return true;
}
};

https://leetcode.com/problems/find-k-closest-elements/

class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int>ans;
int n = arr.size();

// priority queue (min heap) to store the pair of difference and array
element
priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int ,
int>>>q;

for(int i=0 ; i<n ; i++)

{
q.push({abs(x-arr[i]) , arr[i]});
}

while(k--)
 {
ans.push_back(q.top().second);
q.pop();
}

sort(ans.begin() , ans.end());

return ans;
}
};

https://leetcode.com/problems/find-closest-number-to-zero/
class Solution {
public:
int findClosestNumber(vector<int>& nums) {
int ans=INT_MAX;
for(int i=0; i<nums.size(); i++)
{
int dist = abs(nums[i]), val = nums[i];
if(dist<abs(ans))
ans = val;
else if(dist==abs(ans))
ans = ans>val ? ans : val;
}
return ans;
}
};

https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/description/

class Solution {
public:
 int minMove(int egg,int f,vector<vector<int>> &dp){
if(egg==1){
return f;
}

if(f==0 || f==1) return f;

if(dp[egg][f]!=-1) return dp[egg][f];

int mi=INT_MAX;
for(int i=1;i<f;++i){
int Break=minMove(egg-1,i-1,dp);
int notBreak=minMove(egg,f-i,dp);
int move=1+max(Break,notBreak);
mi=min(mi,move);
}

return dp[egg][f]=mi;
}

int twoEggDrop(int n) {
vector<vector<int>> dp(3,vector<int>(n+1,-1));
return minMove(2,n,dp);
}
};

https://leetcode.com/problems/my-calendar-i/
class MyCalendar {
map<int, int> mp;
public:
MyCalendar() {
 }

bool book(int start, int end) {

mp[start]++;
mp[end]--;
int sum=0;
for(auto it=mp.begin(); it!=mp.end(); it++) {
sum += it->second;
if(sum>1){
mp[start]--;
mp[end]++;
return false;
}
}
return true;
}
};

/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/

https://leetcode.com/problems/letter-tile-possibilities/description/

class Solution {
public:
int numTilePossibilities(string tiles) {

set<string> answer;

unordered_map<int, bool> visited;

 for(int i = 0; i < tiles.length(); i++) {
visited[i] = false;
}

string path = "";

backtrack(tiles, answer, path, visited);

return answer.size()-1;
}

void backtrack(string tiles, set<string> &answer, string path, unordered_map<int,

bool> &visited) {

answer.insert(path);

for(int i = 0; i < tiles.length(); i++) {

if (visited[i] == true) {
continue;
}

path.push_back(tiles[i]);

visited[i] = true;

backtrack(tiles, answer, path, visited);

visited[i] = false;

path.pop_back();
}
 }
};

https://leetcode.com/problems/132-pattern/

#include<stack>
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n= nums.size();

if(n<3)
return false;

stack<int>stk;

int third = INT_MIN;

for(int i=n-1;i>=0;i--){

while(!stk.empty() && nums[i]>stk.top()){

third=stk.top();
stk.pop();
}

if(nums[i]<third)
return true;

stk.push(nums[i]);
}

return false;
 }
};

https://leetcode.com/problems/maximum-number-of-points-with-
cost/submissions/1358539425/?envType=daily-question&envId=2024-08-17

class Solution {
public:

long long solve(vector<vector<int>>& points, int n, int m, int prevcol, int

currrow, vector<vector<long long>>& dp){

if(currrow == n){
return 0;
}

if(dp[currrow][prevcol] != -1){
return dp[currrow][prevcol];
}

long long ans = LLONG_MIN;

for(int i = 0; i < m; i++){
long long currentPoints = points[currrow][i] - abs(prevcol - i);
ans = max(ans, currentPoints + solve(points, n, m, i, currrow + 1, dp));
}

return dp[currrow][prevcol] = ans;

}

long long maxPoints(vector<vector<int>>& points) {

int n = points.size(), m = points[0].size();
 vector<vector<long long>> dp(n, vector<long long>(m, -1));
long long ans = LLONG_MIN;
for(int i = 0; i < m; i++){
ans = max(ans, points[0][i] + solve(points, n, m, i, 1, dp));
}

return ans;
}
};

https://leetcode.com/problems/path-sum/
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root ==NULL) return false;

targetSum-=root->val;
if (root->left == NULL && root->right == NULL) {

if(targetSum == 0){
return true;
}else{
return false;
}
}

return (root->left && hasPathSum(root->left, targetSum)) ||

(root->right && hasPathSum(root->right, targetSum));
}
};

https://leetcode.com/problems/path-sum-ii/
class Solution {
public:
void solve(TreeNode* root, int targetSum, vector<vector<int>>& ans,
vector<int> temp, int sum) {
if (root == NULL) {
return;
}

sum += root->val;
temp.push_back(root->val);
if (root->left == NULL && root->right == NULL) {
if (sum == targetSum) {

ans.push_back(temp);
} else {
return;
}
}
solve(root->left, targetSum, ans, temp, sum);
solve(root->right, targetSum, ans, temp, sum);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> ans;
vector<int> temp;
int sum = 0;
solve(root, targetSum, ans, temp, sum);
return ans;
}
};

https://leetcode.com/problems/binary-tree-paths/
class Solution {
private:
 void findPaths(TreeNode* node, string path, vector<string>& paths) {
if (node==NULL) return;
if(!path.empty()) {
path += "->";
}
path+=to_string(node->val);

if (node->left == NULL && node->right == NULL){

paths.push_back(path);
}else{

findPaths(node->left, path, paths);

findPaths(node->right, path, paths);
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
if(root != NULL){
findPaths(root, "", paths);
}
return paths;
}
};

https://leetcode.com/problems/even-odd-tree/
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
queue<TreeNode*>q;
q.push(root);
int level=0;
while(!q.empty()){
 int size=q.size();
int prev=level%2==1 ?INT_MAX:INT_MIN;
for(int i=0;i<size;i++){
auto curr=q.front();
q.pop();
//Filter out all invalid cases and return false
//if found any condition violated
if(level%2==0){//even level
if(curr->val%2==0)
return false;
if(prev>=curr->val)
return false;
}
else if(level%2==1){//odd level
if(curr->val%2==1)
return false;
if(prev<=curr->val)
return false;
}
prev=curr->val;
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
}
level++;
}
return true;
}
};

https://leetcode.com/problems/combinations/
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> comb;

backtrack(1, comb, res, n, k);

return res;
}

private:
void backtrack(int start, std::vector<int>& comb, std::vector<std::vector<int>>&
res, int n, int k) {
if (comb.size() == k) {
res.push_back(comb);
return;
}

for (int num = start; num <= n; num++) {

comb.push_back(num);
backtrack(num + 1, comb, res, n, k);
comb.pop_back();
}
}
};

https://leetcode.com/problems/beautiful-arrangement/description/
class Solution {
public:
int solve(vector<int>&nums, vector<int>&vis, int index, int n){
if(index==n+1){
return 1;
}
int res=0;
 for(int i=0;i<nums.size();i++){
if(vis[nums[i]]==0 && (nums[i]%index==0 || index%nums[i]==0)){
vis[nums[i]]=1;
res+=solve(nums,vis,index+1,n);
vis[nums[i]]=0;
}
}
return res;
}
int countArrangement(int n) {
vector<int>nums, vis(n+1,0);
for(int i=1;i<=n;i++){
nums.push_back(i);
}

int ans=solve(nums,vis,1,n);
return ans;

}
};

https://leetcode.com/problems/heaters/description/
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int radius = 0;

for (int house : houses) {

auto it = lower_bound(heaters.begin(), heaters.end(), house);
int dist1 = (it == heaters.end()) ? INT_MAX : *it - house;
int dist2 = (it == heaters.begin()) ? INT_MAX : house - *(--it);
radius = max(radius, min(dist1, dist2));
 }

return radius;
}
};

https://leetcode.com/problems/deepest-leaves-sum/
class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
if(!root)
return 0;

vector<vector<int>>v;

queue<TreeNode*>q;
q.push(root);

while(!q.empty()){
int size=q.size();
int i=0;
vector<int>a;
while(size--){

auto curr=q.front();
q.pop();
a.push_back(curr->val);
if(curr->left){
q.push(curr->left);
}
if(curr->right)
q.push(curr->right);
 }
v.push_back(a);
}
int c=0;
for(int i=0;i<(v[v.size()-1]).size();i++)
c+=v[v.size()-1][i];

return c;

}
};

https://leetcode.com/problems/rearrange-array-elements-by-sign/
class Solution {
public:
vector<int> rearrangeArray(vector<int>& nums)
{
vector<int> ans(nums.size());

int pos = 0;
int neg = 1;

for(int i=0; i<nums.size(); i++)

{
if(nums[i] > 0)
{
ans[pos] = nums[i];
pos += 2;
}
else
{
ans[neg] = nums[i];
neg += 2;
 }
}

return ans;
}
};

https://leetcode.com/problems/binary-tree-tilt/description/
class Solution {
public:
int ans = 0;
int findTilt(TreeNode* root) {
sum(root);
return ans;
}

int sum(TreeNode* root)

{
if (!root) return 0;
int l = sum(root->left);
int r = sum(root->right);
ans += abs(l - r);
return (l + r + root->val);
}
};

class MyCalendarTwo {
public:
map<int,int> mp;
MyCalendarTwo() {

}
 bool book(int start, int end) {
mp[start]++;
mp[end]--;

int sum=0;
for(auto it:mp)
{
sum+=it.second;
if(sum>2)
{
mp[start]--;
mp[end]++;
return false;
}
}

return true;
}
};

/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo* obj = new MyCalendarTwo();
* bool param_1 = obj->book(start,end);
*/

https://leetcode.com/problems/mice-and-cheese/
class Solution {
public:
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
int n = reward1.size(), ans = 0;
vector<vector<int>> v;
for(int i=0; i<n; i++)
 v.push_back({reward1[i] - reward2[i], reward1[i], reward2[i]});

sort(v.begin(), v.end(), greater<vector<int>>());

for(int i=0; i<n; i++) {

if(k > 0) ans += v[i][1], k--;
else ans += v[i][2];
}
return ans;
}
};

https://leetcode.com/problems/reorder-list/
class Solution {
public:
ListNode* reverseList(ListNode* head){
ListNode* prev = NULL;
ListNode* curr = head;
while(curr){
ListNode* nxt = curr -> next;
curr -> next = prev;
prev = curr;
curr = nxt;
}
return prev;
}

void reorderList(ListNode* head) {

if (!head || !head->next)
return;
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast -> next){
 fast = fast -> next -> next;
slow = slow -> next;
}
ListNode* l2 = reverseList(slow -> next);
slow -> next = nullptr;
ListNode* l1 = head;
while(l2){
ListNode* temp1 = l1 -> next;
ListNode* temp2 = l2 -> next;
l1 -> next = l2;
l2 -> next = temp1;
l1 = temp1;
l2 = temp2;
}
}
};

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode* fast=head;
ListNode* slow=head;
ListNode* temp=head;
if(!head || !head->next)
return NULL;
while(fast && fast->next){
fast=fast->next->next;
temp=slow;
slow=slow->next;
}
temp->next=slow->next;
slow->next=NULL;
 return head;
}
};

https://leetcode.com/problems/remove-linked-list-elements/

class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while(head != NULL && head->val == val){
head = head->next;
}

ListNode *curr = head;

while(curr != NULL && curr->next != NULL){
if(curr -> next -> val == val){
curr ->next = curr->next->next;
}else{
curr = curr->next;
}
}

return head;
}
};

https://leetcode.com/problems/count-operations-to-obtain-zero/

class Solution {
public:
int countOperations(int num1, int num2) {
int count=0;
while(num1!=0 && num2!=0){
 if(num1>=num2){
num1=num1-num2;
}
else{
num2=num2-num1;
}
count++;
}
return count;
}
};

https://leetcode.com/problems/2-keys-keyboard/submissions/1361197124/?envType=daily-
question&envId=2024-08-19

class Solution {
private:
int targetLength;
vector<vector<int>> cache;

int calculateMinOps(int currentLength, int clipboardLength) {

if (currentLength == targetLength) return 0;
if (currentLength > targetLength) return INT_MAX / 2;

if (cache[currentLength][clipboardLength] != -1) {
return cache[currentLength][clipboardLength];
}

int pasteOption = 1 + calculateMinOps(currentLength + clipboardLength,

clipboardLength);
int copyPasteOption = 2 + calculateMinOps(currentLength * 2, currentLength);

int result = min(pasteOption, copyPasteOption);

 cache[currentLength][clipboardLength] = result;

return result;
}

public:
int minSteps(int n) {
if (n == 1) return 0;
targetLength = n;
cache = vector<vector<int>>(n + 1, vector<int>(n / 2 + 1, -1));
return 1 + calculateMinOps(1, 1);
}
};

https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-
i/description/

class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
int l = 0, r = 0;
int one = 0, zero = 0;
int ans = 0;

while (r < s.size()) {

if (s[r] == '0') zero++;
else one++;

while (zero > k && one > k) { // Both exceed k, so we need to shrink the
window
if (s[l] == '0') zero--;
else one--;
l++;
 }

ans += (r - l + 1); // All substrings ending at r and starting from l to

r are valid
r++;
}

return ans;
}
};

https://leetcode.com/problems/stone-game-ii/?envType=daily-question&envId=2024-08-20

class Solution {
public:
int f(int p, int i, int m, int n, vector<int>& piles,
vector<vector<vector<int>>>& dp) {
if (i >= n) {
return 0;
}
if (dp[p][i][m] != -1) {
return dp[p][i][m];
}
int stones = 0;
int maxi = (p == 0) ? -1 : INT_MAX; // Alice wants to maximize, Bob wants to
minimize

for (int x = 1; x <= min(2 * m, n - i); x++) {

stones += piles[i + x - 1]; // Accumulate stones picked in this move

if (p == 0) {
// Alice's turn
maxi = max(maxi, stones + f(1, i + x, max(m, x), n, piles, dp));
} else {
 // Bob's turn
maxi = min(maxi, f(0, i + x, max(m, x), n, piles, dp));
}
}
return dp[p][i][m] = maxi;
}

int stoneGameII(vector<int>& piles) {

int n = piles.size();
vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 1, vector<int>(n +
1, -1)));
return f(0, 0, 1, n, piles, dp);
}
};

https://leetcode.com/problems/range-sum-query-mutable/
class NumArray {
public:

vector<int>a;
vector<int>v;
int build(vector<int>&v,int left,int right,int index){
// base case
if(left==right){
return v[index]=a[left];
}
// return answer
int mid=(left+right)/2;
return v[index]=build(v,left,mid,2*index+1)+build(v,mid+1,right,2*index+2);
}
void updatee(int loc,int left,int right,int index,int x){
if(loc<left||loc>right)return ;
// complete overlap
 if(loc==left&&left==right){
v[index]=x;
return;
}
// partial overlap
int mid=(left+right)/2;
// return answer
updatee(loc,left,mid,2*index+1,x);
updatee(loc,mid+1,right,2*index+2,x);
v[index]=v[2*index+1]+v[2*index+2];
}

int query(int qleft,int qright,int left,int right,int index){

// no overlap
if(qright<left||qleft>right)return 0;
// complete overlap
else if(qleft<=left&&qright>=right)return v[index];
// partial overlap
int mid=(left+right)/2;
// return answer
int lefts=query(qleft,qright,left,mid,2*index+1);
int rights=query(qleft,qright,mid+1,right,2*index+2);
return lefts+rights;
}

NumArray(vector<int>& nums) {
a=nums;
v.resize(4*a.size());
build(v,0,a.size()-1,0);
}

void update(int index, int val) {

updatee(index,0,a.size()-1,0,val);
 }

int sumRange(int left, int right) {

return query(left,right,0,a.size()-1,0);
}
};

https://leetcode.com/problems/decode-ways/description/
class Solution {
public:
int f(int i,string &s,vector<int>&dp){
int n=s.size();
if(s[i]=='0') return 0;
if(i==n) return 1;
if(dp[i]!=-1) return dp[i];
int res=f(i+1,s,dp);
if(i<n-1 && (s[i]=='1' || s[i]=='2' && s[i+1]<='6'))
res=(res+f(i+2,s,dp));
return dp[i]=res;
}
int numDecodings(string s) {
vector<int>dp(s.size()+1,-1);
return f(0,s,dp);
}
};

https://leetcode.com/problems/count-number-of-texts/
class Solution {
public:
int mod = (1e9+7);
long long solve(int i, string& s, vector<int>& dp) {
if(i<=0)
return 1;

if(dp[i]!=-1)
return dp[i];

long long ans = 0;

ans=(ans+solve(i-1,s,dp))%mod;
if(i>0 && s[i]==s[i-1])
ans=(ans+solve(i-2,s,dp))%mod;

if(i>0 && s[i]==s[i-1] && i>1 && s[i]==s[i-2])

ans=(ans+solve(i-3, s,dp))%mod;

if(i>0 && s[i]==s[i-1] && i>1 && s[i]==s[i-2] && i>2 && s[i]==s[i-3] &&
(s[i]=='7' || s[i]=='9'))
ans=(ans+solve(i-4, s,dp))%mod;
 return dp[i]=ans%mod;

}
int countTexts(string pressedKeys) {
int n = pressedKeys.size();
vector<int> dp(n,-1);
return solve(n-1, pressedKeys, dp);
}
};