LeetCode, GeeksForGeeks Problem of the day solution
Open in Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Show more1 250
Subscribers
+224 hours
+147 days
+2930 days
Posts Archive
class Solution {
public:
int noOfPP=0;
void dfs(TreeNode* root,int path[]){
path[root->val]++;
if(root->left){
dfs(root->left, path);
}
if(root->right){
dfs(root->right, path);
}
if(root->left==nullptr && root->right==nullptr){
int count=0;
for(int i=1;i<=9;i++){
if(path[i]%2 != 0){
count++;
}
}
if(count <= 1){
noOfPP++;
}
}
path[root->val]--;
}
int pseudoPalindromicPaths (TreeNode* root) {
int path[10] ={0};
dfs(root, path);
return noOfPP;
}
};
class Solution {
public:
bool isCycle(int src, vector &visited, vector adj[]) {
queue>q;
q.push({src,-1});
visited[src] = 1;
while(!q.empty()) {
int node = q.front().first;
int parent = q.front().second;
q.pop();
for(auto i : adj[node]) {
if(!visited[i]) {
visited[i] = 1;
q.push({i,node});
} else if(parent != i){
return true;
}
}
}
return false;
}
int isTree(int n, int m, vector> &B) {
if (n-1 != m) {
return 0;
}
vectorvisited(n,0);
vector adj[n];
for(int i=0; itemp = B[i];
adj[temp[0]].push_back(temp[1]);
adj[temp[1]].push_back(temp[0]);
}
for(int i=0; i < n; i++) {
if(visited[i] == 0) {
if(isCycle(i,visited,adj)) {
return 0;
}
}
}
for(int i=0; i
class Solution {
public:
bool compare(vector &selected,string &currString){
vector selfCheck(26,0);
for(int i=0;i &arr,vector &selected,int len){
if(i == arr.size()){
return len;
}
string currString = arr[i];
if(compare(selected,currString) == false){
return f(i+1,arr,selected,len);
}
else
{
//pick
for(int j=0;j& arr) {
vector selected(26,0);
return f(0,arr,selected,0);
}
};
class Solution
{
public:
vector findOrder(int n, int m, vector> prerequisites)
{
vector adj[n];
for(auto it:prerequisites){
adj[it[1]].push_back(it[0]);
}
int indegree[n]={0};
for(int i=0;i q;
for(int i=0;i topoSort;
while(!q.empty()){
int node = q.front();
q.pop();
topoSort.push_back(node);
for(auto it:adj[node]){
indegree[it]--;
if(indegree[it]==0){
q.push(it);
}
}
}
if(topoSort.size()==n){
return topoSort;
}
return {};
}
};
class Solution {
public:
vector findErrorNums(vector& nums)
{
int XOR = 0, duplicatedNum = 0, missingNum = nums.size();
for (int num : set(nums.begin(), nums.end())){
XOR ^= num;
}
for (size_t i = 0; i < nums.size(); i++){
duplicatedNum ^= nums[i];
}
for (size_t i = 1; i < nums.size(); i++){
missingNum ^= i;
}
return {duplicatedNum ^ XOR, missingNum ^ XOR};
}
};
class Solution
{
public:
void solve(Node * root , int s , int sum , vector&v, vector>&ans)
{
if(root==NULL) return ;
v.push_back(root->key);
s+=root->key;
if(s==sum) {
ans.push_back(v);
}
solve(root->left , s, sum , v, ans);
solve(root->right,s,sum,v,ans);
s-=root->key;
v.pop_back();
}
vector> printPaths(Node *root, int sum)
{
//code here
vector>ans;
vectorv;
solve(root,0,sum,v,ans);
return ans;
}
};
class Solution {
public:
int solve(vector& nums, int ind, vector&dp){
if(ind < 0){
return 0;
}
if(dp[ind]!=-1){
return dp[ind];
}
return dp[ind]=max(nums[ind]+solve(nums, ind-2, dp), solve(nums, ind-1, dp));
}
int rob(vector& nums) {
int n = nums.size();
vector dp(n, -1);
return solve(nums, n-1, dp);
}
};
class Solution{
public:
vector> adj;
bool isPossible(int n, int m, int mid) {
int set = (1 << mid) - 1;
int limit = (1 << n);
while (set < limit) {
bool vis[n + 1][n + 1] = {0};
int edgeCovered = 0;
for (int j = 1, u = 1; j < limit; j = j << 1, u++) {
if (set & j) {
for (int v = 1; v <= n; v++) {
if (adj[u][v] && !vis[u][v]) {
edgeCovered++;
vis[u][v] = 1;
vis[v][u] = 1;
}
}
}
}
if (edgeCovered == m)
return true;
int rightMostSetBit = set & -set;
int val = set + rightMostSetBit;
set = (((val ^ set) >> 2) / rightMostSetBit) | val;
}
return false;
}
public:
int vertexCover(int n, vector> &edges) {
int m = edges.size();
adj.resize(n + 1, vector(n + 1));
for (auto v : edges) {
adj[v.first][v.second] = 1;
adj[v.second][v.first] = 1;
}
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (isPossible(n, m, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
stack<int> s1, s2;
int n = arr.size();
vector<int> next_smaller(n), prev_smaller(n);
for(int i = 0;i<n;i++){
next_smaller[i] = n-i-1;
prev_smaller[i] = i;
}
for(int i = 0;i<n;i++){
while(!s1.empty() && arr[s1.top()]>arr[i]){
next_smaller[s1.top()] = i - s1.top() - 1;
s1.pop();
}
s1.push(i);
}
for(int i = n-1;i>=0;i--){
while(!s2.empty() && arr[s2.top()]>=arr[i]){
prev_smaller[s2.top()] = s2.top() - i - 1;
s2.pop();
}
s2.push(i);
}
long ans = 0;
int mod = 1e9 + 7;
for(int i = 0;i<n;i++){
ans = (ans + (long)arr[i] * (prev_smaller[i]+1) * (next_smaller[i]+1)) % mod;
ans %= mod;
}
return ans;
}
};
class Solution
{
public:
int check(Node* root,int &count)
{
if(root==NULL)
return 0;
int a=check(root->left,count);
int b=check(root->right,count);
count+=abs(a)+abs(b);
int h=root->key-1+a+b;
return h;
}
int distributeCandy(Node* root)
{
//code here
int ans=0;
int j=check(root,ans);
return ans;
}
};
int check(Node* root,int &count)
{
if(root==NULL)
return 0;
int a=check(root->left,count);
int b=check(root->right,count);
count+=abs(a)+abs(b);
int h=root->key-1+a+b;
return h;
}
int distributeCandy(Node* root)
{
//code here
int ans=0;
int j=check(root,ans);
return ans;
}
