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:
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;
}
};
