LeetCode, GeeksForGeeks Problem of the day solution

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

class Solution { public: //Function to find a solved Sudoku. bool safe(int row,int col,int num,int grid[N][N]){ for(int i=0;i<9;i++){ // checking for row if(grid[row][i]==num)return false; // checking for column if(grid[i][col]==num)return false; // checking for grid if(grid[(row/3)*3 + i/3][(col/3)*3 + i%3]==num) return false; } return true; } bool SolveSudoku(int grid[N][N]) { for(int i=0;i

class Solution { public: #define ll long long const int MOD = 1e9 + 7; ll solve(int n, int goal, int k, vector < vector < int >> & dp) { if (n == 0 && goal == 0) return 1; if (n == 0 || goal == 0) return 0; if (dp[n][goal] != -1) return dp[n][goal]; ll pick = solve(n - 1, goal - 1, k, dp) * n; ll notpick = solve(n, goal - 1, k, dp) * max(n - k, 0); return dp[n][goal] = (pick + notpick) % MOD; } int numMusicPlaylists(int n, int goal, int k) { vector < vector < int >> dp(n + 1, vector < int > (goal + 1, -1)); return solve(n, goal, k, dp); } };

class Solution{ public: //Complete this function void solve(int index, string& vec, vector &ans){ if(index==vec.size()){ ans.push_back(vec); return; } for(int i=index;i permutation(string S) { vector ans; solve(0,S, ans); sort(ans.begin(), ans.end()); return ans; } };

class Solution { public: vector buildTree(int start, int end) { vector ans; // If start > end, then subtree will be empty so add NULL in the ans and return it. if(start > end) { ans.push_back(NULL); return ans; } // Iterate through all values from start to end to construct left and right subtree recursively for(int i = start; i <= end; ++i) { vector leftSubTree = buildTree(start, i - 1); // Construct left subtree vector rightSubTree = buildTree(i + 1, end); // Construct right subtree // loop through all left and right subtrees and connect them to ith root for(int j = 0; j < leftSubTree.size(); j++) { for(int k = 0; k < rightSubTree.size(); k++) { TreeNode* root = new TreeNode(i); // Create root with value i root->left = leftSubTree[j]; // Connect left subtree rooted at leftSubTree[j] root->right = rightSubTree[k]; // Connect right subtree rooted at rightSubTree[k] ans.push_back(root); // Add this tree(rooted at i) to ans data-structure } } } return ans; } vector generateTrees(int n) { return buildTree(1, n); } };

class Solution{ public: long long findMinDiff(vector a, long long n, long long m){ sort(a.begin(), a.end()); int i=0; int j=m-1; long long ans = 1e9; while(j

class Solution { public: unordered_set st; int dp[301]; int solve(string& s, int index){ if(index>=s.size()){ return 0; } if(dp[index] != -1){ return dp[index]; } int mini = 1e9; for(int i=1;i<=s.size();i++){ string str = s.substr(index, i); if(st.find(str) != st.end()){ mini = min(mini, solve(s, index+i)); } } mini = min(mini, 1+solve(s, index+1)); return dp[index] = mini; } bool wordBreak(string s, vector& wordDict) { for(int i=0;i

class Solution{ public: void solve(stack<int>& st, deque<int>& dq){ if(st.size()==0){ return; } int val = st.top(); st.pop(); dq.push_back(val); solve(st, dq); int val2 = dq.front(); dq.pop_front(); st.push(val2); } void Reverse(stack<int> &St){ if(St.size()==0){ return; } // int val = St.top(); // St.pop(); // St.push(val); deque<int> dq; solve(St, dq); } };

class Solution { public: void solve(string digits,string output,int index,string mapping[],vector &ans){ if(index>=digits.size()){ ans.push_back(output); return; } int i = digits[index]-'0'; string value = mapping[i]; for(int i=0;i letterCombinations(string digits) { vector ans; if(digits.size()==0){ return ans; } string output=""; int index = 0; string mapping[10] = {"", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; solve(digits,output,index,mapping,ans); return ans; } };

// User function Template for C++ class Solution { public: void topoSort(int node, vector<pair<int,int>> adj[], vector<int>& vis, stack<int>& st){ vis[node] = 1; for(auto it:adj[node]){ int v = it.first; if(vis[v]==0){ topoSort(v, adj, vis, st); } } st.push(node); } vector<int> shortestPath(int N,int M, vector<vector<int>>& edges){ vector<pair<int,int>> adj[N]; for(int i=0;i<M;i++){ int u = edges[i][0]; int v = edges[i][1]; int wt = edges[i][2]; adj[u].push_back({v, wt}); } stack<int> st; vector<int> vis(N, 0); for(int i=0;i<N;i++){ if(vis[i]==0){ topoSort(i, adj, vis, st); } } vector<int> dist(N); for(int i=0;i<N;i++){ dist[i] = 1e9; } dist[0] = 0; while(!st.empty()){ int node = st.top(); st.pop(); for(auto it:adj[node]){ int v = it.first; int wt = it.second; if(dist[node]+ wt < dist[v]){ dist[v] = dist[node]+wt; } } } for(int i=0;i<N;i++){ if(dist[i]==1e9){ dist[i] = -1; } } return dist; } };