Set | Fall out, Codes!

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);
 */

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

Fall out, Codes!

Let all the problems bow before your patience and stubbornness!

Category Set

Leetcode 729. My Calendar I

Longest Consecutive Sequence