Category STL

LeetCode 388. Longest Absolute File Path

Arunima Mandal 1 Comment

Problem Link: https://leetcode.com/problems/longest-absolute-file-path/

Note:
This problem intuitively resembles a tree structure. But it can be solved using a deque easily, though I think the first data structure that will come to mind is a stack, at least that was in my case. A stack would work, but eventually while accessing all the elements of the stack for length counting, then you will get how deque will serve in that case!

In the following code, one limiting criterion is that the length of the level cannot be less than the size of the deque, if it is greater then we have already processed the subdirectory/file and we haven’t found our answer yet, so we can discard that from the deque. 

class Solution {
public:
    int lengthLongestPath(string input) {
        deque<int> dq;
        int len=0, level=0, res=0;
        bool flag=0;
        for(int i=0; i<input.size(); i++)
        {
            if(input[i]=='\n')
            {
                dq.push_back(len);
                len=0;
                level=0;
                flag=0; 
            }
            else if(input[i]=='\t') level++;
            else if(input[i]=='.')
            {
                flag=1;
                len++;
            }
            else
            {
                len++;
                if(flag)
                {
                    int sum=0;
                    for(int i=0; i<dq.size(); i++)
                    {
                        sum+=dq[i];
                    }
                    res=max(res, sum+len+level);
                }
                while(level<dq.size()) dq.pop_back();
            }
        }
        return res;
    }
};

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

UVA – 673 – Parentheses Balance

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/6/673.pdf

Note:
This can be solved using different data structures and logic. I have used Stack to approach the problem.

Solution:

/*
Author: Arunima Mandal
Updated Date: 06.16.2020
*/
#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;
stack<char> st;
string s;
int main()
{
// CIN; //if getline() is present, it can't be used.
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,d;
sf(t);
getchar();
for0(z,t)
{
getline(cin,s);
d=0;
for0(i,sz(s))
{
if(s[i]=='(' || s[i]=='{' || s[i]=='[')
{
st.push(s[i]);
}
else if(s[i]==' ') continue;
else
{
if(!st.empty())
{
char ch=st.top();
if((ch=='(' && s[i]==')') || (ch=='{' && s[i]=='}') || (ch=='[' && s[i]==']'))
{
st.pop();
}
else break;
}
else {d=1; break;} //there is nothing left in stack to compare with.
}
}
if(!d && st.empty()) pf("Yes\n");
else
{
pf("No\n");
while(!st.empty()) st.pop();
}
}
return 0;
}
view raw UVA 673 - Parentheses Balance.cpp hosted with ❤ by GitHub

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