LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) { int n=positions.size(); map<int, int> mp; stack<int> st; for(int i=0;i<n;i++) { mp[positions[i]] = i; } for(auto i:mp) { int pos = i.first; int ind = i.second; if(directions[ind] == 'L' && st.empty()) { continue; } else if(directions[ind] == 'L') { while(!st.empty() && healths[ind] != 0) { int pInd = st.top(); st.pop(); if(healths[ind] > healths[pInd]) { healths[ind]--; healths[pInd] = 0; } else if(healths[ind] < healths[pInd]) { healths[pInd]--; healths[ind] = 0; st.push(pInd); } else { healths[ind] = 0; healths[pInd] = 0; } } } else { st.push(ind); } } vector<int> res; for(auto i:healths) { if(i != 0) res.push_back(i); } return res; } };

class Solution { public: vector<int> shortestPath(int n, int m, vector<vector<int>>& edges) { // Code here vector<vector<pair<int,int>>> adj(n+1); for(auto &it:edges){ adj[it[0]].push_back({it[1],it[2]}); adj[it[1]].push_back({it[0],it[2]}); } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<int> dist(n+1,1e9), parent(n+1); for(int i=1;i<=n;i++) parent[i] = i; dist[1] = 0; pq.push({0,1}); while(!pq.empty()){ auto it = pq.top(); int dis = it.first; int node = it.second; pq.pop(); for(auto &it:adj[node]){ int adjNode = it.first; int edW = it.second; if(dis + edW < dist[adjNode]){ dist[adjNode] = dis + edW; pq.push({dist[adjNode],adjNode}); parent[adjNode] = node; } } } // if destination is not reachable if(dist[n]==1e9) return {-1}; vector<int> path; int node = n; while(parent[node] != node){ path.push_back(node); node = parent[node]; } path.push_back(1); path.push_back(dist[n]); reverse(path.begin(),path.end()); return path; } };

class Solution { public: int maximumGain(string s, int x, int y) { int n = s.length(); stack<char> st; bool flag = (x > y) ? 1:0; int res = 0; for(int i=0; i<n; i++){ if(s[i] != ((flag)? 'b':'a')) st.push(s[i]); else{ if(!st.empty() && st.top() == ((flag)? 'a':'b')){ res+= (flag)? x:y; st.pop(); } else st.push(s[i]); } } string t = ""; while(!st.empty()){ t.push_back(st.top()); st.pop(); } reverse(t.begin(), t.end()); for(int i=0; i<t.length(); i++){ if(t[i] != ((flag)? 'a':'b')) st.push(t[i]); else{ if(!st.empty() && st.top() == ((flag)? 'b':'a')){ res+= (flag)? y:x; st.pop(); } else st.push(t[i]); } } return res; } };

class Solution { public: // Function to find a continuous sub-array which adds up to a given number. vector subarraySum(vector arr, int n, long long s) { // Your code here int right = 0; int left = 0; long long sum = arr[left]; while(right < n){ if(sum == s){ return {left+1,right+1}; } else if(sum < s){ right++; sum += arr[right]; } else if(sum > s && left == right){ left++; right++; sum = arr[left]; } else{ sum -= arr[left]; left++; } } return {-1}; } };

class Solution { public: bool check(vector<int>&v, int m, int mid){ int n=v.size(); int num=v[0]; int c=1; for(int i=1; i<n; i++){ if(v[i]-num>=mid){ c++; num=v[i]; } } return c>=m; } int maxDistance(vector<int>& v, int m) { int n=v.size(); sort(v.begin(),v.end()); int s=1; int ans=s; int e=v[n-1]-v[0]; while(s<=e){ int mid=(s+e)/2; if(check(v,m,mid)){ ans=mid; s=mid+1; } else e=mid-1; } return ans; } };

class Solution { public: long long int InternalCount(long long int p[], long long int q[], long long int r[]) { long long int A=abs((p[0]*(q[1]-r[1]) + q[0]*(r[1]-p[1]) + r[0]*(p[1]-q[1]))/2); long long int B1 =__gcd(abs(p[0]-q[0]),abs(p[1]-q[1]))+1; long long int B2 =__gcd(abs(q[0]-r[0]),abs(q[1]-r[1]))+1; long long int B3 =__gcd(abs(r[0]-p[0]),abs(r[1]-p[1]))+1; long long int B=(B1+B2+B3-3)/2; return (A-B+1); } };

class Solution { public: // Whether it is possible required bouquets with given max time bool bouquetPossible(vector& bloom_days, int bloom_day, int m, int k) { int bouquets = 0, flowers = 0; for(const int& day: bloom_days) { if(day <= bloom_day) ++flowers; else flowers = 0; if(flowers == k) ++bouquets, flowers = 0; } return bouquets >= m; } int minDays(vector& bloomDay, int m, int k) { // No. of flowers req more than available if(m * k > bloomDay.size()) return -1; int low = 0, high = INT_MAX; while(low < high) { // Candidate bloom date for making req bouquets int bloom_day = low + (high - low) / 2; if(bouquetPossible(bloomDay, bloom_day, m, k)) high = bloom_day; else low = bloom_day + 1; } return high; } };

class Solution { public: double maxVolume(double perimeter, double area) { double P = perimeter; double A = area; double sqrtTerm = sqrt(P * P - 24 * A); double dimension1 = (P - sqrtTerm) / 12.0; double dimension2 = (P / 4.0) - 2 * dimension1; double volume = pow(dimension1, 2) * dimension2; return round(volume * 100.0) / 100.0; } };

class Solution { public: vector getPrimes(int n) { vector isP(n+1,true); isP[0]=isP[1]=false; for(int i=2;i*i<=n;i++){ if(isP[i]){ for(int j=i*i;j<=n;j+=i) isP[j]=false; } } vector p; for(int i=2;i<=n;i++) if(isP[i]) p.push_back(i); int i=0,j=p.size()-1; if(n&1){ if(isP[n-2]) return {2,n-2}; else return {-1,-1}; } while(i<=j){ if(p[i]+p[j]==n) return {p[i],p[j]}; if(p[i]+p[j]

class Solution { public: int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { int n = profits.size(); vector<pair<int, int>> projects; for (int i = 0; i < n; ++i) { projects.push_back({ capital[i], profits[i] }); } sort(projects.begin(), projects.end()); int pind = 0; priority_queue<int> q; for (int i = 0; i < k; ++i) { while (pind < n && projects[pind].first <= w) { q.push(projects[pind++].second); } if (q.empty()) break; w += q.top(); q.pop(); } return w; } };