Category Algorithmic Codes

Dijkstra – From Source to Destination

Arunima Mandal Leave a comment

Here, I have used the adjacency matrix and Priority queue of C++ STL to implement the basic Dijkstra algorithm.

Time Complexity: O(E log(V)). This is because, for each vertex, we need to traverse all its adjacent vertices and update their distances, which takes O(E) time. Also, we use a Priority Queue which takes O(logV) time for each insertion and deletion.

Space Complexity: O(V*V). This is because, in the worst-case scenario, every vertex can be connected to every other vertex in the graph.

Code:

#include <bits/stdc++.h>

#define MAX             100005
#define INF             INT_MAX
#define pii             pair<int,int>

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

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    //dis[100005]={INT_MAX} ; why doesn't work(gives wrong answer) I don't know!
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in the priority queue:
        /*
        Ideally, for updating the priority queue, we must delete the old value and reinsert with the
        new cost value. But, as we know that the updated cost value is always lesser than the old
        value and would be popped from the queue and visited before the old value,
        we could save time and avoid removing the old value from the queue.
        */
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

//unordered_map<string,int> mp; //for string input

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int node, edge;
    cout<<"Enter number of nodes: \n";
    cin>>node;
    cout<<"Enter number of edges: \n";
    cin>>edge;
    //int c=1;

    cout<<"Enter the edges and their corresponding cost (node node cost):"<<endl;

    vector<vector<pair<int,int> > > adj(MAX);
    //vector<pair<int,int>> adj[node]; //can also be written like this

    for(int i=0; i<edge; i++)
    {
        int from,to,cost;
        //string frm,to;
        cin>>from>>to>>cost;

//        if(mp[frm]==0)
//        {
//            mp[frm]=c;
//            c++;
//        }
//        if(mp[to]==0)
//        {
//            mp[to]=c;
//            c++;
//        }

        adj[from].push_back({to, cost});
        adj[to].push_back({from, cost}); //If undirected graph
//        g[mp[frm]].push_back(mp[to]);
//        g[mp[to]].push_back(mp[frm]); //If undirected graph
    }

    int src,dst;
    //string src,dst;

    cin>>src>>dst;

    int min_distace=dijkstra(src, dst, adj);
    //int min_distace=dijkstra(mp[src],mp[dst], adj);
    if(min_distace==INF) cout<<"No path"<<endl;
    else
    {
        cout<<"Shortest distance with min cost: "<<min_distace<<endl;
    }
    return 0;
}

Stable Marriage/Internship problem

Arunima Mandal Leave a comment


Assumption: The problem is usually biased toward the interns. That is – the intern’s preference is given priority. If we solve the problem by giving the priority to the teams, the solution might be different. So we’ve to make sure to understand from the problem statement – who should we give priority to – interns or teams? If not explicitly mentioned anything about this, then it will be the interns. Similarly, in case of a stable marriage problem, make sure who to give priority – men or women.

Approach: Gale–Shapley algorithm



#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > stableInternships(vector<vector<int>> interns, vector<vector<int>> teams) {

  int n=interns.size();

  unordered_map<int,int> chosen_interns;
  stack<int> free_interns;
  vector<int> current_intern_choices(n+1,0);
  vector<unordered_map<int,int> > team_maps;

  for(int i=0; i<teams.size(); i++)
    {
      free_interns.push(i);
      unordered_map<int,int> rank;
      for(int j=0; j<teams[i].size(); j++) rank[teams[i][j]]=j;
      team_maps.push_back(rank);
    }
  while(!free_interns.empty())
    {
      int intern=free_interns.top();
      int preferred_team=interns[intern][current_intern_choices[intern]];
      if(!chosen_interns.count(preferred_team))
      {
        chosen_interns[preferred_team]=intern;
        free_interns.pop();
      }
      else
      {
        int prev_intern= chosen_interns[preferred_team];
        int rank_intern=team_maps[preferred_team][intern];
        int rank_prev_intern=team_maps[preferred_team][prev_intern];
        if(rank_intern<rank_prev_intern)
        {
          chosen_interns[preferred_team]=intern;
          free_interns.pop();
          free_interns.push(prev_intern);
        }
      }
      current_intern_choices[intern]++;
    }
  unordered_map<int,int>::iterator it;
  vector<vector<int> > ans;
  for(it=chosen_interns.begin(); it!=chosen_interns.end(); ++it)
    {
      vector<int> v;
      v.push_back(it->second);
      v.push_back(it->first);
      ans.push_back(v);
    }
  return ans;
}

int main()
{
    vector<vector<int> > interns={
        {0,1,2},
        {1,0,2},
        {1,2,0}
    };
    vector<vector<int> > teams={
        {2,1,0},
        {1,2,0},
        {0,2,1}
    };
    vector<vector<int> > ans=stableInternships(interns, teams);
    for(int i=0; i<ans.size(); i++)
    {
        cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
    }
    cout<<endl;
    return 0;
}

Time complexity: O(N^2)

Space Complexity: O(N^2)

Trie (Insert and Search)

Arunima Mandal Leave a comment

Note: I have understood the concept of Trie from the following link- https://www.geeksforgeeks.org/trie-insert-and-search/
I have just modified the code according to my understanding and tried to make the code concise.

Code:

#include <bits/stdc++.h>
using namespace std;

struct TrieNode
{
	TrieNode *child[26]={}; //if string contains alphabets only
	bool word=0;
};

void insert(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) it->child[index] = new TrieNode();
		it = it->child[index];
	}
	it->word = 1;
}

bool search(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) return false;
		it = it->child[index];
	}
	return (it->word);
}

// Driver
int main()
{
	// Input keys (use only 'a' through 'z' and lower case)
	vector<string> keys={"the", "a", "there", "answer", "any", "by", "bye", "their" };

	TrieNode *root = new TrieNode();

	// Construct trie
	for (int i = 0; i < keys.size(); i++)
		insert(root, keys[i]);

	// Search for different keys
	char output[][32] = {"Not present in trie", "Present in trie"};

	// Search for different keys
	cout<<"the"<<" --- "<<output[search(root, "the")]<<endl;
	cout<<"these"<<" --- "<<output[search(root, "these")]<<endl;
	cout<<"their"<<" --- "<<output[search(root, "their")]<<endl;
	cout<<"thaw"<<" --- "<<output[search(root, "thaw")]<<endl;
	return 0;
}

Longest Palindromic Substring

Arunima Mandal Leave a comment

Note: The problem title is pretty self-explaining. Now as for the solution, it can be solved in the usual brute force method (for each starting and ending position) in O(N^3) time. Another way would be Dynamic Programming which results in O(N^2) for both time complexity and space complexity.

The following approach is also an intuitive one (though hard to come to mind at first) with better time and space complexities. It is called Expand Around Centre.

Since expanding a palindrome around its center could take O(n) time, and as we are expanding for every index of the string, the overall complexity is O(n^2). And the space complexity is O(1).

Code:

#include <bits/stdc++.h>

using namespace std;

int expandAroundCentre(string &s, int left, int right)
{
    while(left>=0 && right<s.size() && s[left]==s[right])
    {
        left--;
        right++;
    }
    return right-left-1;
}

string longestPalindrome(string s)
{
    if(s.size()==0) return "";
    int start=0, ans=0;
    for(int i=0; i<s.size(); i++)
    {
        int len1=expandAroundCentre(s,i,i); //for odd length
        int len2=expandAroundCentre(s,i,i+1); //for even length
        int len=max(len1,len2);
        if(len>ans) //if len is greater than previous palindromic length
        {
            start=i-(len-1)/2; //for left side of i
            ans=len;
        }
    }
    return s.substr(start,ans);
}

int main()
{
    string s;
    cin>>s;
    cout<<"The longest palndromic substring is "<<longestPalindrome(s)<<endl;
    return 0;
}

Maximum Sum SubArray Problem

Arunima Mandal Leave a comment

Approach 1: Kadane’s Algorithm

Though it’s a particular algorithm, if one is good at programming, this approach is more intuitive than any other approach without knowing that this is actually an algorithm! 

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0, start =0, end = 0, s=0;
    //cout<<"max_so_far "<<max_so_far<<endl;

    for (int i=0; i< size; i++ )
    {
        max_ending_here += a[i];

        if (max_ending_here > max_so_far)
        {
            max_so_far = max_ending_here;
            start = s;
            end = i;
        }

        if (max_ending_here < 0)   ///If that is any negative number, we discard it
        {
            max_ending_here = 0;
            s = i+1; ///and start considering from the next index.That is we are rightfully assuming
                    ///that the beginning & ending of the subsequence can't contain any negative number.
        }
    }
    cout << "Maximum contiguous sum is "
        << max_so_far << endl;
    cout << "Starting index "<< start
        << endl << "Ending index "<< end << endl;
}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n);
    return 0;
}

If the problem states that the subarray would have to be of k size, fear not! That solution is not much different from the above approach. We have just to modify the above solution a bit in that case.

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size, int k)
{
    if(k>size) cout<<"Invalid"<<endl;

    int sum=0,maxi=-100000,start=0,endi;
    for(int i=0;i<k;i++) sum+=a[i];
    maxi=sum;
    for (int i=k; i< size; i++ )
    {
        sum+= a[i]-a[i-k];
        if(sum>maxi)
        {
            maxi=sum;
            start= i-k+1;
            endi=i;
        }
    }
    cout<<"Maximum sum "<<maxi<<endl;
    cout<<"Start at index "<<start<<" and ends at index "<<endi<<endl;
    return maxi;

}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int k=3;
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n, k);
    return 0;
}

Approach 2: Using DP(Dynamic Programming)

This method is also intuitive for solving the problem if one is comfortable using the DP algorithm.

#include <bits/stdc++.h>

using namespace std;

int maxSumSubArray_dp(int nums[], int size)
{
    int dp[100005]= {0};
    dp[0] = nums[0];
    int maxi = dp[0];
    for (int i = 1; i < size; i++)
    {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        maxi = max(maxi, dp[i]); // find max in dp
    }
    return maxi;
}

int main()
{
    int nums[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(nums)/sizeof(nums[0]);
    int max_sum = maxSumSubArray_dp(nums, n);
    cout<<"Maximum Sum Subarray using DP is "<<max_sum<<endl;
    return 0;
}