GeeksForGeeks - POTD | GFG POTD Answer

Flipkart GRiD 6.0

class Solution {
  public:
    int alternatingMaxLength(vector<int>& arr) {
      
        int n=1,m=1;
        for(int i=1;i<arr.size();i++){
            if(arr[i-1]<arr[i]){
                n=m+1;
            }
             if(arr[i]<arr[i-1]){
                m=n+1; 
            }
            else{
                continue;
            }
        }
        return max(n,m);
    }
};

class Solution {
  public:
    
    Node *createTree(vector<int> parent) {
        unordered_map<int,Node*> nodes;
        for(int i =0;i< parent.size();i++){
            nodes[i] =new Node(i);
        }
        int rootval =-1;
        for(int i =0;i< parent.size();i++){
            int Par =parent[i];
            int Child =i;
            if(Par == -1){
                rootval =i;
                continue;
            }
            if(nodes[Par]->left == nullptr){
                nodes[Par]->left =nodes[Child];
            }else{
                nodes[Par]->right =nodes[Child];
            }
        }
        return nodes[rootval];
    }
};

class Solution {
  public:

    string printString(string s, char ch, int count) {
        
        string ans="";
        for(auto i:s){
            if(count <= 0) ans+=i;
            if(i==ch) count--;
        }
        return ans;
 }
};

class Solution {
  public:
    string smallestNumber(int s, int d) {
        if (9 * d < s) {
            return "-1";
        }
        if (s > 9) {
            return smallestNumber(s - 9, d - 1) + "9";
        }
        if (d == 1){
            return to_string(s);
        }
        if (s > 1) {
            return smallestNumber(1, d - 1) + to_string(s - 1);
        }
        
        return smallestNumber(1, d - 1) + "0";
    }
};

class Solution {
  public:
    void segregate0and1(vector<int> &arr) {
          
        int n = arr.size();
        int i =0;
        int j =n-1;
        while(j> i){
            if(arr[i]==1 && arr[j]==0){
                swap(arr[j],arr[i]);
                i++;
                j--;
            }
            else if(arr[i] ==1 && arr[j]== 1){
                j--;
            }
            else if(arr[i] ==0 && arr[j]== 0){
                i++;
            }
            else{
                i++;
                j--;
            }
        }
    }
};

class Solution {
  public:
    vector<int> shortestPath(int V, int m, vector<vector<int>>& edges) {
        unordered_map<int,list<pair<int,int>>>adj;
        for(auto&it:edges){
            int u=it[0];
            int v=it[1];
            int weight=it[2];
            adj[u].push_back({v,weight});
            adj[v].push_back({u,weight});
        }
        
        vector<int>visited(V+1,0);
        vector<int>dist(V+1,INT_MAX);
        dist[1]=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; 
        pq.push({0,1});
        vector<int>parent(V+1,-1);
        
        while(!pq.empty()){
            int node=pq.top().second;
            pq.pop();
            
            if(!visited[node]){
                visited[node]=true;
                for(auto v:adj[node]){
                    int nbr=v.first;
                    int weight=v.second;
                    if(dist[nbr]>dist[node]+weight){
                        dist[nbr]=dist[node]+weight;
                        pq.push({dist[nbr],nbr});
                        parent[nbr]=node;
                    }
                }
            }
        }
        
        if(parent[V]==-1)return {-1};
        vector<int>path;
        int t=V;
        while(t!=-1){
         path.push_back(t);
         t=parent[t];
        }
        path.push_back(dist[V]);
        reverse(path.begin(),path.end());
        return path;
    }
};

class Solution {
public:
    bool hasPathSum(Node* root, int target) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return target == root->data;
        }
        int remainingSum = target - root->data;
        return hasPathSum(root->left, remainingSum) || hasPathSum(root->right, remainingSum);
    }
};