Category Map

LeetCode 2115. Find All Possible Recipes from Given Supplies

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/

Note: Since the problem explicitly demands dependency, and the recipes are the ultimate nodes that have indegrees topological sort is the most intuitive thing that can come to mind if you know the idea of the topological sort well. I used Kahn’s algorithm here to do the topological sort.

  • Time complexity: O(n)
  • Space complexity: O(n)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string> > ump;
        unordered_map<string,int> indegree;
        vector<string> ans;
        for(int i=0; i<ingredients.size(); i++)
        {
            for(int j=0; j<ingredients[i].size(); j++)
            {
                 ump[ingredients[i][j]].push_back(recipes[i]);
                 indegree[recipes[i]]++;
            }
        }
        for(int i=0; i<supplies.size(); i++)
        {   
            for(int j=0; j<ump[supplies[i]].size(); j++)
            {
                string adj=ump[supplies[i]][j];
                indegree[adj]--;
                if(indegree[adj]==0)
                {
                    supplies.push_back(adj);
                    ans.push_back(adj);
                }
            }
        }
        return ans;
    }
};

Longest Consecutive Sequence

Arunima Mandal Leave a comment

Problem Statement: https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Notice that, the repeated numbers do not count! Also, note that here the ‘sequence’ does not mean that they cannot break! But for many problems with “sequence”, that is not the case. So it’s better if you can verify this with the problem creator before attempting to solve the question.

Approach 1: This problem can be solved in different ways. The brute force one would take O(N^3). I am not going to show that here, because honestly, I think that solution didn’t come to mind at all! I think except for newbies, for most programmers that is the case.

Approach 2: The first solution that comes intuitively to mind is to sort the array first! That simplifies the solution instantly! But that would take O(NlogN) time because sorting alone takes that time, the rest of the method would take O(N) time understandably. So the overall time complexity will be O(NlogN) ultimately.

Approach 3: Other O(NlogN) solutions are using set or ordered_map. Since here the sequence of the original array doesn’t matter, and also, the repeated numbers do not matter, so we can use a set and map, where looking up the elements takes O(logN) time! Both in set or map, the numbers are always sorted when constructed. So the overall time complexity of the solution would take O(NlogN) time.

Approach 4: We can improve the time complexity to O(N) if we can think slightly out of the box. The method is to use a hash set or hash map and then run an intelligent sequence building method. Here basically, we will search for the elements that have no precedent number. If found, then we’ll only process that number to find its later consecutive numbers. Since we’ll not deal with the numbers that have precedent numbers, so we are essentially avoiding N^2 computation. In the following code below, in worst case, it will take N+N time, resulting in O(N+N)=O(2N)=O(N) time complexity

Code:

#include <bits/stdc++.h>

using namespace std;

int longestConsecutive_sorting(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    sort(nums.begin(),nums.end());
    int maxi=-1,count=1;
    for(int i=1; i<nums.size(); i++)
    {
        if(nums[i]-nums[i-1]==1) count++;
        else if(nums[i]-nums[i-1]!=0)
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_set(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    set<int> st;
    for(int i=0; i<nums.size(); i++) st.insert(nums[i]);
    set<int>:: iterator it;
    int maxi=-1,count=1;
    for(it=st.begin(); next(it)!=st.end(); ++it)
    {
        int x=*it;
        int y=*(next(it));
        if(y-x==1) count++;
        else
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_map(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    map<int,int> mp;
    for(int i=0; i<nums.size(); i++) mp[nums[i]]++;
    map<int,int>:: iterator it;
    int maxi=-1,count=1;
    for(it=mp.begin(); next(it)!=mp.end(); ++it)
    {
        int x=it->first;
        int y=(next(it))->first;
        if(y-x==1) count++;
        else
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_hashSet(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    unordered_set<int> st;
    for(int i=0; i<nums.size(); i++) st.insert(nums[i]);
    unordered_set<int>:: iterator it;
    int ans=0;
    for(it=st.begin(); it!=st.end(); ++it)
    {
        if(!st.count((*it)-1))
        {
            int cur=*it;
            int count=1;
            while(st.count(cur+1))
            {
                cur++;
                count++;
            }
            ans=max(ans,count);
        }
    }
    return ans;
}

int main()
{
    vector<int> nums;
    cout<<"No. of elements"<<endl;
    int n;
    cin>>n;
    cout<<"Enter an unsorted array elements: "<<endl;
    for(int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        nums.push_back(x);
    }
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Sorting is "<<longestConsecutive_sorting(nums)<<endl;
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Set is "<<longestConsecutive_set(nums)<<endl;
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Map is "<<longestConsecutive_map(nums)<<endl;
    //Takes O(N) time
    cout<<"Longest Consecutive sequence using hashSet is "<<longestConsecutive_hashSet(nums)<<endl;
    return 0;
}

LeetCode 692. Top K Frequent Words

Arunima Mandal Leave a comment

Problem link: https://leetcode.com/problems/top-k-frequent-words/

Note:

This is mainly a basic code for sorting a map according to its value. That can be done in multiple ways but I usually do that with the help of a vector, by copying the map into a vector of pairs, then sorting that vector by the second value of each pair.

Also, it’s a bit more challenging while sorting the vector since if the values are the same then the strings should be printed according to their lexicographical order.

Code:

class Solution {
public:
    static bool comp(pair<string,int> x, pair<string,int> y)
    {
        if(x.second>y.second) return 1;
        else if(x.second<y.second) return 0;
        else
        {
            int a=x.first.size();
            int b=y.first.size();
            for(int i=0; i<x.first.size(); i++)
            {
                if(x.first[i]<y.first[i]) return 1;
                else if(x.first[i]>y.first[i]) return 0;
            }
            if(a<b) return 1;
            else return 0; 
        }
        
    }
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> mp;
        vector<pair<string,int> > v;
        vector<string> ans;
        int sz=words.size();
        for(int i=0; i<sz; i++)
        {
            mp[words[i]]++;
        }
        
        unordered_map<string,int>:: iterator it;
        for(it=mp.begin(); it!=mp.end(); ++it)
        {
            v.push_back({it->first, it->second});
        }
        sort(v.begin(), v.end(), comp);
        for(int i=0; i<k; i++)
        {
            ans.push_back(v[i].first);
        }
        return ans;
    }
};

SPOJ – ACMCEG2B – FIGUREFUL

Arunima Mandal Leave a comment

Problem Link: http://www.spoj.com/problems/ACMCEG2B/

Solution:

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define db                  double
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define pll                 pair<long,long>
#define ff                  first
#define ss                  second
#define sz(x)               (int)x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000006
#define inf                 100000008

ll power(int n,int p)
{
    ll ans=1;
    for1(i,p) ans*=n;
    return ans;
}

ll m=1000001;
ll bigmod(ll n,ll p)
{
    if(p==0) return 1;
    else if(p%2==0)
    {
        ll x=(bigmod(n,p/2))%m;
        return (x*x)%m;
    }
    else return ((n%m)*(bigmod(n,p-1)%m))%m;
}


/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

map<pii,string> mp;

int main()
{
    //CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,t,x,y;
    string s;
    sf(n);
    for0(i,n)
    {
        sff(x,y);
        cin>>s;
        pii z=make_pair(x,y);
        mp[z]=s;
    }
    sf(t);
    for1(z,t)
    {
        sff(x,y);
        pii w=make_pair(x,y);
        cout<<mp[w]<<endl;
    }

    return 0;
}