Category vector

Is vector<vector> costlier than vector<pairs> in C++?

Arunima Mandal Leave a comment

Yes, it is way costlier! I stumbled on the problem very recently and got these two very useful links in Google. Please check these out for a thorough understanding.

  1. The following link is helpful for core theoretical logic – https://stackoverflow.com/questions/73095254/how-is-vectorvectorint-heavier-than-vectorpairint-int
  2. And here the fact is experimentally proved which is cool! – https://codeforces.com/blog/entry/110222

So my take on this is:

  1. When we need a large vector size but a small number of walkthroughs, the vector<pair<int>> implementation has a way more advantage over vector<vector<int>>.
  2. When you need larger walkthroughs per index of the outside vector(maybe you do not know even the actual size of the inside vector), then it is better to declare the vector with size and later assign values to it instead of pushing back (that’s given when you declare the size of the vector!) throughout the code.

For example,

a. vector<vector<int>> v (n, vector<int> (m,0)); – When you know the size of the inside vector – m

b. vector<vector<int>> v (n); (When you are not sure what the size of the inside vector would be)

Any of these two would give slightly better performance than just declaring vector<vector<int>> v;

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

Leetcode 729. My Calendar I

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/my-calendar-i/description/

Note:

This problem is interesting to solve. It’s easy but again if you want to optimize, you will have to be careful about using data structure.

Approach 1: Using vector and Binary Search (O(N^2logN) time complexity)

In this approach, the time complexity is O(N^2 logN) because the sort() function takes O(NlogN) time. So for calling it N times, the time complexity will be O(N*NlogN) = O(N^2logN).

class MyCalendar {
public:
    vector<pair<int,int> > v;
    
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        return true; 
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

Approach 2: Using Set and Binary Search (O(NlogN) time complexity)

Here, the highest time is taken by the set insert which is logN. So for calling it N times, the time complexity will be O(N*logN) = O(NlogN).

class MyCalendar {
public:
    //vector<pair<int,int> > v;
    set<pair<int,int> >st;
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        /*
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        */
        auto nextEvent=st.lower_bound(p);
        if(nextEvent!=st.end() && end>nextEvent->first) return false;
        if(nextEvent!=st.begin())
        {
            auto prevEvent=prev(nextEvent);
            if(start<prevEvent->second) return false;
        }
        st.insert(p);
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */