Leetcode 365. Water and Jug Problem solution

Problem statement could be found @https://leetcode.com/problems/water-and-jug-problem/

Solution code

class Solution {
public:
    int getHCF(int x, int y){
         if ( y == 1)
            return 1;
        if (x%y == 0)
            return y;
        return getHCF(y, x%y);
    }
    bool canMeasureWater(int x, int y, int z) {
        if ( (x+y) < z){
            return false;
        }
        int hcf = 0;
        if (x > y)
            hcf = getHCF(x,y);
        else
            hcf = getHCF(y,x);
   
        if (z%hcf == 0)  
            return true;
        else
            return false;
    }
};

Leetcode 398. Random Pick Index solution

Problem statement could be found @https://leetcode.com/problems/random-pick-index/

Initial approach - Initially I started by creating a map of elements and their index list but this got TLE as the memory is given as constraint. The reason for this thought was index once and query multiple times.

Second approach - Compare the values on fly and save matching indexes. Then generate random value and mod by nos of instances of matching indexes, using the value received after mod to do find the index. This was accepted

Following is the code with second approach

class Solution {
 
    vector<int> elementVector;
    size_t vectorSize ;
public:
    Solution(vector<int> nums) {
      elementVector = nums;
      vectorSize = nums.size();
     
     
     
    }
   
    int pick(int target) {
        vector<int> indexVect;
        for (int i=0;i<vectorSize; i++){
            if (elementVector[i] == target)
                indexVect.push_back(i);
        }
        int indexSize = indexVect.size();
        int randVal = (rand()%indexSize);
        return indexVect[randVal];
    }
};

Leetcode 399 Evaluate Division Solution

Problem description could be found @https://leetcode.com/problems/evaluate-division/

Approach - The solution is a DFS to be done on Graph, where graph nodes are the divisor and dividends. Value obtained from result is the edge weight between divisor and dividend node

 The first idea in  my mind was to create adjacency matrix with assumption that there are only 1 length string but it failed as sample testcases had  strings like ab, cd. So had to go with Adjacency list solution. Following is the accepted code which ran in 3 msec

struct node{
  double weight;
  string adjacentNode;
 
  node (double wt, string dest){
      this->weight = wt;
      this->adjacentNode = dest;
  }
};

class Graph{
    private:
        map<string, list<node *> *> nodeMap;
    public:
        Graph(){
           
        }
        void addNode(string src, string des, double wt){
            node *tempNode = new node(wt, des);
           
            list<node *> *nodeList;
            if (nodeMap.count(src) == 0){
                nodeList = new list<node *>();
                nodeMap[src] = nodeList;
            }else{
               nodeList =  nodeMap.at(src);
            }
            nodeList->push_back(tempNode);
           
            // add in reverse way
            node *tempOppNode = new node(1.0/wt, src);
           
            list<node *> *revList;
            if (nodeMap.count(des) == 0){
                revList = new list<node *>();
                nodeMap[des] = revList;
               
            }else{
               revList =  nodeMap.at(des);
            }
            revList->push_back(tempOppNode);
        }
       
        bool contains(string key){
            if (nodeMap.count(key) != 0)
                return true;
            return false;
        }
       
        double dfs(string src, string dest, set<string> traversed){
            list<node *> *myList = nodeMap[src];
            if (traversed.find(src) != traversed.end())
                return -1.0;
               
            if (myList == NULL){
                return -1.0;
            }
            traversed.insert(src);
           for (list<node *>::iterator it=myList->begin();
                    it != myList->end() ; it++){
               node *listNode = *it;
               if (listNode->adjacentNode == dest){
                   traversed.erase(src);
                   return listNode->weight;
               }else{
                   double d = dfs(listNode->adjacentNode, dest, traversed);
                   if (d != -1.0){
                       traversed.erase(src);
                       return d * listNode->weight;
                   }
               }
           }
           traversed.erase(src);
           return -1;
        }
};


class Solution {
public:
 
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        Graph g ;
        for (int i=0;i<equations.size();i++)   {
            pair<string, string> val = equations[i];
            double value = values[i];
            g.addNode(val.first, val.second, value);
         
         
        }
       
        vector<double> retVal;
        for (size_t i=0;i<queries.size();i++){
            string src = queries[i].first;
            string dest = queries[i].second;
            if (src == dest){
                if (g.contains(src))
                    retVal.push_back(1.0);
                else
                    retVal.push_back(-1.0);
            }else{
                set<string> traversed;
                double d = g.dfs(src, dest, traversed);
                retVal.push_back(d);
            }
        }
        return retVal;
    }
}; 

Leetcode 395 Longest Substring with At Least K Repeating Character Solution

Problem Statement could be found @https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

Solution:-
Idea is to first count all character occurrence in a string. If a character is repeated less than k times, then is shouldn't be considered and can act string splitter.
class Solution {
    int repeatCount;
    int maxSubSize;
public:
    int helper(string s){
        int tempMaxSize = 0;
        if (s.size() < repeatCount){
            return 0;
        }
        //int tempMaxSize
        int arr[26] = {0};
        for (int i=0;i<s.size();i++){
            arr[s.at(i) -'a'] ++;
        }
       
        int startLength = 0;
        int flag = false;
        int charCount = 0;
        for (int i=startLength;i<s.size();i++){
            // this could act as breaker
            int charVal = (s.at(i) -'a');
         
            if (arr[charVal] < repeatCount){
                if (charCount == 0)
                    charCount = 1;
                string temp = s.substr(startLength,charCount);
                int tempL = helper(temp);
                if (tempL > tempMaxSize)
                    tempMaxSize = tempL;
                startLength = i+1;
                flag = true;
                charCount = 0;
            }else{
                charCount ++;
            }
        }
        if (flag == false && s.size() >= repeatCount  ){
            //maxSubSize = s.size();
            tempMaxSize = s.size();
            return tempMaxSize ;
        }else{
            string temp = s.substr(startLength);
            int tempL = helper(temp);
            if (tempL > tempMaxSize){
                tempMaxSize = tempL;
            }
        }
           
        return tempMaxSize;
    }
    int longestSubstring(string s, int k) {
        repeatCount  = k ;
        maxSubSize = 0;
        int tempMaxSize = helper(s);
        if (tempMaxSize > maxSubSize)
            return tempMaxSize;
        else
            return maxSubSize;
    }
};