Category Sorting

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

Bubble sort

Arunima Mandal Leave a comment

Solution:

#include <iostream>
using namespace std;
int main()
{
int i,j;
int n,temp; // In case of dealing with 'char', instead of 'int', 'char' would have to be written
cin>>n;
int a[n];
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<n;i++) cout<<a[i]<<endl;
return 0;
}
view raw Bubble sort.cpp hosted with ❤ by GitHub

Quicksort

Arunima Mandal Leave a comment

Note: I have used pivot as the middle element each time.

#include <iostream>
using namespace std;
void quicksort(int a[],int left, int right)
{
int i,j,temp,pivot;
i=left;
j=right;
pivot=a[(left+right)/2];
while(i<=j)
{
//For left side
while(a[i]<pivot) i++;
//For right side
while(a[j]>pivot) j--;
// a[i], which is greater than the pivot and a[j], which is less than the pivot, those two are swapping,
// to make the all the elements left of the pivot, smaller than the pivot and right of the pivot, greater than the pivot
if(i<=j)
{
swap(a[i],a[j]);
/* Since after the swap, a[i] is smaller than the pivot & a[j] is greater than the pivot,
so there is no need to start checking from i or j, that's why i++ and j-- is done */
i++;
j--;
}
}
// After this loop, the left side of the present pivot is smaller and the right side is greater.
// Now it's turn to quick sort the left and the right part
if(left<j)
{
quicksort(a,left,j);
}
if(right>i)
{
quicksort(a,i,right);
}
}
int main()
{
int n,l;
cout<<"Enter the size of the array : "<<endl;
cin>>n;
int ar[n];
cout<<"Enter the unsorted array elements : "<<endl;
for(l=0;l<n;l++) cin>>ar[l];
quicksort(ar,0,n-1);
cout<<"The sorted array : "<<endl;
for(l=0;l<n;l++)
{
cout<<ar[l]<<endl;
}
return 0;
}
view raw Quick sort.cpp hosted with ❤ by GitHub

UVa – 10008 – What’s Cryptanalysis

Arunima Mandal Leave a comment 
#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define sz(x)           x.size()
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;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 case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(tx,ty)    tx>=0 && tx<r && ty>=0 && ty<c
#define MAX             2000

/*----------------------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<char,int> mp;
vector<pair<char,int> > v;

bool comp(pair<char,int> a,pair<char,int> b)
{
    if(a.ss>b.ss) return 1;
    else if(a.ss==b.ss)
    {
        if(a.ff<b.ff) return 1;
        else return 0;
    }
    else return 0;
}

int main()
{
    //CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int n;
    cin>>n;
    getchar();
    loop0(i,n)
    {
        string s;
        getline(cin,s);
        char ch;
        loop0(j,sz(s))
        {
            if((s[j]>='A' && s[j]<='Z') || (s[j]>='a' && s[j]<='z'))
            {
                ch=toupper(s[j]);
                mp[ch]++;
            }
        }
    }
    stlloop(mp) v.pb(make_pair(it->ff,it->ss));
    sort(all(v),comp);
    loop0(i,sz(v)) cout<<v[i].ff<<" "<<v[i].ss<<endl;
    return 0;
}