Leetcode 729. My Calendar I

December 8, 2022December 8, 2022Arunima 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);
 */

Longest Common Prefix of a String

September 22, 2022Arunima Mandal Leave a comment

Brute-Force (Vertical Scanning):

Here we are returning an empty string if no common prefix is found.

Time Complexity: O(S) where S is the sum of all characters present in the vector. Or we can say O(mn) where m is the length of the vector and n is the length of the strings (assuming of highest limit) inside the vector.

Space Complexity: O(1) as constant space for the answer only.

#include <bits/stdc++.h>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    string ans="";
    for(int j=0; j<strs[0].size(); j++)
    {
        char ch=strs[0][j];
        for(int i=1; i<strs.size(); i++)
        {
            if(j>=strs[i].size() || strs[i][j]!=ch)
            {
                return ans;
            }
        }
        ans+=ch;
    }
    return ans;
}

int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Binary Search:

The trick to using the binary search in this problem is to find out the minimum length string first, and then apply binary search to it.

Time Complexity: O(S*log(n)) where S is the sum of all characters in the vector and n is the size of the length of the minimum string.

Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isCommonPrefix(vector<string>& strs, int len)
{
    string s=strs[0].substr(0,len);
    for(int i=1; i<strs.size(); i++)
    {
        if(strs[i].substr(0,len)!=s) return false;
    }
    return true;
}

string longestCommonPrefix(vector<string>& strs) {
    string mini_str;
    int mini=300;
    for(int i=0; i<strs.size(); i++)
    {
        if(strs[i].size()<mini)
        {
            mini=strs[i].size();
            mini_str=strs[i];
        }
    }
    if(mini==0) return "";

    int low=1; //Can't initialize it to 0 as we are considering length
    int high=mini;
    while(low<=high)
    {
        int mid=low+(high-low)/2;
        if(isCommonPrefix(strs, mid)) low=mid+1;
        else high=mid-1;
    }
    return strs[0].substr(0,(high+low)/2);
}


int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

UVA 11413 – Fill the Containers

June 22, 2022August 25, 2022Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2408

Note:

After reading the problem statement, most of our instant intuition will go with the Dynamic Programming approach understandably to solve this problem. Yes, that is obviously correct but another approach would be Binary Search which is unlikely to come to our mind at first. But Binary Search approach is more efficient in solving this problem compared to the Dynamic approach in terms of time and space complexity. Also, once you understand this approach, it’s easier to implement than the Dynamic one!

Here, the non-breaking property of the input array, that is you’ll have to maintain the serial of the containers in the conveyor belt (array). So we can choose to guess the minimal capacity of the container by calculating what would be the initialization of left and right in code. This initialization is an important step in this problem. In binary search, if the problem is not so straightforward as this one, initializing the left and right correctly is the first big step.

binarySearch():

Here, as I will guess minimum capacity, so the left limit would be the minimum possible value of the answer, thus the maximum element of the array. And the right limit would be the maximum possible value of the answer, the sum of all elements of the array.

Then we would run binary search within this range and would call the checkM function whether the mid satisfies the given limit of containers – m or not.

-If yes, then that’s a probable answer so we will keep that in our next iteration, and since in the next iteration we can find a lesser capacity amount than this one, we would update mid=right.

-If not, that means, our mid (the chosen probable capacity) is lower than any probable answer as it is requiring more containers than m. So we will update left=mid+1.

And in the end, if the condition left<right is not met, the code will exit the while loop, and now we can return left or right, that does not matter in this case(ultimately left and right would be equal while exiting the loop) due to the condition set for the loop and updating mid the way I did. In my code, I have written right as it seems easier to me to understand.

checkM():

This function is pretty straightforward. If with our predicted possible value (mid), all the elements of the array can be distributed in exactly m containers then it returns true, if it requires more than m containers we break immediately and return false.

I hope solving these types of problems using Binary search would increase the range of our intuition to solve a problem with an efficient and easier approach – Binary search.

Code:

#include <bits/stdc++.h>

using namespace std;

bool checkM(vector<int>& v, int m, int probableCap)
{
    int sz=v.size();
    int total=0, cnt=1;
    for(int i=0; i<sz; i++)
    {
        total+=v[i];
        if(total>probableCap)
        {
            total=v[i];
            cnt++;
            if(cnt>m) return 0;
        }
    }
    return 1;
}

int binarySearch(vector<int>& v, int left, int right, int m)
{
    int mid;
    while(left<right)
    {
        mid=left+(right-left)/2;
        if(checkM(v, m, mid)) right=mid;
        else left=mid+1;
    }
    return right;
}
int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        vector<int> v;
        int sum=0, maxx_element=-1, x;
        for(int i=0; i<n; i++)
        {
            cin>>x;
            v.push_back(x);
            sum+=x;
            maxx_element=max(x,maxx_element);
        }
        int left=maxx_element, right=sum;
        cout<< binarySearch(v,left,right,m)<<endl;
    }
    return 0;
}

Binary Search

June 9, 2022June 13, 2022Arunima Mandal Leave a comment

Note:

Binary Search is a core algorithm of Computer Science. It can be found everywhere but I am particularly writing it here as I just got to know about new knowledge or change in the logic of the traditional algorithm. The algorithm has been made more appropriate recently with the memory and capacity evolving in recent age. For detail and in-depth knowledge please see this – https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

So basically in the traditional algorithm while dividing the array or vector space into two halves, the proper logic would be –

mid = first+(last-first)/2;

instead of

mid = (first+last)/2;

Otherwise, you would get a runtime error in the case that the sum of the first and last is

greater than the maximum positive int value (2³¹ – 1).

Code:

#include <bits/stdc++.h>

using namespace std;

int a[10000007];
int not_found_pos=-1; //Declaring it global to get the index if the item is not found

bool binarySearch(int item, int n) 
{
    int first=0, last=n-1, mid=0;
    while(first<=last)
    {
        mid=first+(last-first)/2; //for avoiding overflow of summation of first and last
        if(item>a[mid]) first=mid+1;
        else if(item<a[mid]) last=mid-1;
        else return mid; //item=a[mid] //item found
    }
    //Item was not found
    not_found_pos=first; //But if it was found it would be at index 'first'
    return -1; 
}

int main()
{
    int n,item;
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i]; // Must be sorted.
    cout<<"Enter the item that to be searched"<<endl;
    cin>>item;
    int pos=binarySearch(item,n);
    if(pos==-1)
    {
        cout<<"The item "<<item<<" was not found but if it was found, it would be at index "<< not_found_pos << endl;
    }
    else //Assuming Indexing from "0"
    {
        cout<<"The item "<<item<<" was found at position "<<pos<<endl;
    }
    return 0;
}

UVa – 10611 – The Playboy Chimp

April 26, 2017Arunima Mandal Leave a comment

#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 pii                 pair<int,int>
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define ff                  first
#define ss                  second
#define sz(x)               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                 100005
#define inf                 100000008

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

ll a[50004];

int main()
{
    //CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n,q;
    sf(n);
    for0(i,n) sfl(a[i]);
    sf(q);
    for0(i,q) 
    {
        ll x;
        sfl(x);
        int l=lower_bound(a,a+n,x)-a;
        int u=upper_bound(a,a+n,x)-a;
        if(a[l-1]==0) pf("X ");
        else pf("%lld ",a[l-1]);
        if(a[u]==0) pf("X\n");
        else pf("%lld\n",a[u]);
    }
    return 0;
}

Fall out, Codes!

Let all the problems bow before your patience and stubbornness!

Category Searching

Leetcode 729. My Calendar I

Longest Common Prefix of a String

UVA 11413 – Fill the Containers

Binary Search

UVa – 10611 – The Playboy Chimp