LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: int minimumEffortPath(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); vector<vector<int>> visi(n,vector<int>(m,1e7)); priority_queue<pair<int,pair<int,int>>> q; vector<pair<int,int>> dirs = {{1,0},{0,1},{-1,0},{0,-1}}; q.push({0,{0,0}}); visi[0][0]=0; while(!q.empty()){ auto t = q.top(); if(t.second.first==n-1&&t.second.second==m-1)return -1*t.first; q.pop(); for(auto& dir:dirs){ int nx = t.second.first+dir.first; int ny = t.second.second + dir.second; if(nx<0 or ny<0 or nx>=n or ny>=m)continue; int val = -1*max(-1*t.first,abs(grid[nx][ny]-grid[t.second.first][t.second.second])); if(-1*val<visi[nx][ny]){ q.push({val,{nx,ny}}); visi[nx][ny]=-val; } } } return -1; } };

class Solution { public: //Function to count the number of ways in which frog can reach the top. long long countWays(int n) { long long mod = 1000000007; vector dp(n+1, 0); dp[0] = 1; dp[1] = 1; dp[2] = 2; for(long long i=3;i<=n;i++){ dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%mod; } return dp[n]%mod; } };

class Solution { int dist(int x1, int y1, int x2, int y2){ return abs (x1-x2) + abs(y1-y2); } public: int minCostConnectPoints(vector>& points) { if (points.size() < 1) return 0; int V = points.size(); int result = 0; vector minDists(V, INT_MAX); vector mst(V, 0); minDists[0] = 0; mst[0] = 1; for (auto i = 0 ; i < V; i++) { minDists[i] = dist(points[0][0],points[0][1],points[i][0],points[i][1]); } for(int i = 0;i

class Solution{ public: int solve(int i, int sum, int N,int a[], vector>&dp){ if( i >= N){ if(sum == 0) return 1; return 0; } if(sum == 0) return 1; if(sum < 0) return 0; if(dp[i][sum] != -1) return dp[i][sum]; int include = solve(i+1,sum-a[i],N,a,dp); int exclude = solve(i+1,sum,N,a,dp); return dp[i][sum] = include || exclude; } int equalPartition(int N, int arr[]) { // code here int sum = 0; for(int i = 0 ;i>dp(N+1,vector(sum/2+1,-1)); if(sum%2 != 0) return 0; return solve(0,sum/2,N,arr,dp); } };

class Solution { public: vector findItinerary(vector>& tickets) { unordered_map> adjlist; vector res{"JFK"}; int n = tickets.size(); sort(tickets.begin(), tickets.end()); for (auto ticket: tickets) { string src = ticket[0]; string dst = ticket[1]; adjlist[src].push_back(dst); } dfs(res, adjlist, "JFK", n); return res; } bool dfs(vector& res, unordered_map>& adjlist, string cur, int n) { if (res.size() == n + 1) return true; if (adjlist.find(cur) == adjlist.end()) return false; deque tmp = adjlist[cur]; while (!tmp.empty()) { string dst = tmp.front(); tmp.pop_front(); res.push_back(dst); adjlist[cur].pop_front(); if (dfs(res, adjlist, dst, n)) return true; res.pop_back(); adjlist[cur].push_back(dst); } return false; } };

class Solution{ public: int perfectSum(int arr[], int n, int sum) { vector dp(sum + 1, 0); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = sum; j >= arr[i]; j--) { dp[j] += dp[j - arr[i]]; dp[j] %= 1000000007; // Modulo to avoid integer overflow } } return dp[sum]; } };

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

class Solution{ public: string findLargest(int N, int S){ if(N>1 && S==0){ return "-1"; } string ans=""; while(N>0){ if(S>=9){ ans += "9"; S -= 9; } else{ ans += char(S+'0'); S -= S; } N--; } if(S==0) return ans; return "-1"; } };

class Solution { public: int minDeletions(string s) { int arr[26] = {0}; for(int i=0;iv; for(int i=0;i<26;i++) if(arr[i] > 0) v.push_back(arr[i]); sort(v.begin(),v.end()); int ans = 0; for(int i=v.size()-2;i>=0;i--){ if(v[i+1] == 0){ ans += v[i]; v[i] = 0; } else if(v[i] >= v[i+1]){ ans += v[i]-v[i+1]+1; v[i] = v[i+1]-1; } } return ans; } };

class Solution { public: int isPerfectNumber(long long N) { if(N==1) return 0; long long sum=1; for(long long i=2;i*i<=N;i++){ if(N%i==0){ sum += i; if(N/i != i){ sum += N/i; } } } return sum==N; } };