In the previous post, we discussed Topological Sorting and in this post, we are going to discuss two problems based on it. So, let’s start.

Leetcode 210 :  Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair [0,1].

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]

Explanation: There are total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Note : The input prerequisites is a graph represented by a list of edges, not adjacency matrices.

You may assume that there are no duplicate edges in the input prerequisites.

Analysis of Problem Statement

The Problem Statement is very much clear and I don’t think any further explanation is required.

NOTE that prerequisite [0,1] means course 1 should be completed first, then course 0.

How to approach the problem..??

Since, problem statement has some ‘n’ keys along with some sets which are dependent on each other, clearly it is a Graph Question.

In the above problem, n represent the number of vertices and prerequisites define the edges between them.

Also, [0,1] means course 1 should be completed first, then course 0. So, here graph is Directed because [0,1] is not equal to [1,0].

Logic behind the problem statement

Since, it is very much clear that the problem statement is of Directed Graph data structure.

Now, let’s understand the logic behind the problem statement.

Let’s take an example,

n = 4
prerequisites[] = {[1, 0], [2, 0], [3, 1], [3, 2]}

Let’s draw the directed graph for the above example,

Query [2, 0] means course 0 should be completed before course 2, so (0 -> 2) represents course 0 first, then course 2.

Now, our objective is to return the ordering of courses one should take to finish all courses.

For above example, order should be 0 1 2 3.

Since Course 0 doesn’t depend on other course, it should be completed first.

Course 1 and Course 2 depends on Course 0 and since we have completed course 0, so now we can complete both course 1 and course 2 in any order.

Lastly, Course 3 depends on Course 1 and Course 2, so we will complete Course 3 at last.

Solution to Course Schedule II

From above discussion it is clear that it is a Topological Sort Problem.

We have to sort the Graph according to their in-degrees as we have discussed in the previous post.

We will first create the directed Graph and perform Topological Sort to it and at last we will return the vector which stores the result of Topological Sort.

NOTE if Topological Sorting is not possible, return empty vector as it is mentioned in the problem statement.

Let’s see the code,

unordered_map<int, vector<int>> adj;

vector<int> findOrder(int num, vector<vector<int>>& p) 
{   
    for(int i = 0; i < p.size(); i++)
    {
        adj[p[i][1]].push_back(p[i][0]);
    }

    int *in_order = new int[num];

    for(int i = 0; i < num; i++) {
        in_order[i] = 0;
    }

   for(int i = 0; i < num; i++)
   {
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_order[*itr]++;
        }
    }

    queue<int> q;

    vector<int> res;

    for(int i=0; i < num; i++) 
    {
        if(in_order[i] == 0) q.push(i);
    }

    while(!q.empty())
    {							            							        
        int p = q.front();
        q.pop();

        res.push_back(p);

        for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
        {
            in_order[*itr]--;

            if(in_order[*itr] == 0) q.push(*itr);
        }
    }

    if(res.size() == num) return res;

    res.clear();
    return res;

}

I think above code doesn’t require any explanation. It is a simple Topological Sort question.

The main part of the above problem is to analyse it how approach the above problem step by step, how to reach to the point where we can understand that Topological Sort will give us the desired result.

Now let’s see another problem to make concept more clear.

Problem : Alien Dictionary

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary.

Objective : Find the order of characters in the alien language.

Note: Many orders may be possible for a particular test case, thus you may return any valid order.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N and k denoting the size of the dictionary. Then in the next line are sorted space separated values of the alien dictionary.

Output:
For each test case in a new line output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function findOrder() which takes the string array dict[], its size N and the integer K as inputs and returns a string denoting the order of characters in the alien language.

Expected Time Complexity: O(N + K).
Expected Auxiliary Space: O(K).

Constraints:

1 <= T <= 1000
1 <= N <= 300
1 <= k <= 26
1 <= Length of words <= 50

Example:

Input:
2
5 4
baa abcd abca cab cad
3 3
caa aaa aab

Output:
1
1

Explanation:

Test Case 1:
Input:  Dict[ ] = { "baa", "abcd", "abca", "cab", "cad" }, k = 4
Output: Function returns "bdac"

Here order of characters is 'b', 'd', 'a', 'c'

Note that words are sorted and in the given language "baa"
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Test Case 2:
Input: Dict[] = { "caa", "aaa", "aab" }, k = 3
Output: Function returns "cab"

Analysis of Problem Statement

We are all familiar with English Dictionary and we all know that dictionary follows alphabetical order (A-Z).

Alien Dictionary also follows a particular alphabetical order, we just need to find the order with the help of given words.

There are some N words given which uses k letters, we have to find the order of characters in the alien language.

Hope, problem statement is clear to you, please refer to above examples for more clarity.

Logic behind the Problem statement

It is quite obvious that character appearing first in the words has higher preference. For ex,

In {“ba”,”ab”}, b has higher preference than a, so order will be (b a).

Let’s take another example,

5 4
{"wrt", "wrf", "er", "ett", "rftt"}

In the above example,

From first two words, it is clear that t comes before f. (t->f)
From 2nd and 3rd words, it is clear that w comes before e. (w->e)
From 3rd and 4th words, it is also clear that r comes before t. (r->t)
Lastly, from 4th and 5th words, it is clear that e comes before r. (e->r)

From above observation, order will be (w->e->r->t->f).

Hope you got the Logic, it is highly recommended to think of the approach to solve this problem before moving ahead.

Algorithm behind Alien Dictionary

From the above observation, you might have guessed that clearly it is a Graph question but the masterstroke is that how to construct the graph from given words.

Let’s discuss how will you construct the graph from given words.

As discussed above, we will take two words at a time and compare it to find the appropriate order.

It’s obvious that there will be definitely a mismatch of letter in both the pair of words. From every words, we will find the mismatch and finally we will conclude the graph.

Let’s take the another example to make things clear,

5 4
{"baa", "abcd", "abca", "cab", "cad"}

From first two words, it is clear that b comes before a. (b->a)
From 2nd and 3rd words, d comes before a. (d->a)
From 3rd and 4th words, a comes before c. (a->c)
Lastly, from 4th and 5th words, b comes before d. (b->d)

From above observation order will be (b->d->a->c).

Let’s see the code for constructing the Graph,

void findOrder(string dict[], int N, int K) 
{
    unordered_map<char,vector<char>> adj;
    
    for(int i = 1; i < N; i++)
    {
        string str1 = dict[i-1];
        string str2 = dict[i];
        
        int x = 0;
        while(x < min(str1.length(),str2.length()))
        {
            if(str1[x] != str2[x])
            {
                adj[str1[x]].push_back(str2[x]);
                break;
            }
            x++;
        }
    }
}

Hope you understood the code, let’s move ahead.

2nd step of the Algorithm

Since, we had constructed the graph, now our job is to find the ordering and for that Topological Sort will help us.

We already have the Graph, we will simply apply Topological Sort on it. Also since, graph is linear order will be unique.

Let’s see a example,

Graph : b->d->a->c

We will start Topological Sort from 1st vertex (w),

Topological Sort will be : b d a c and it will be our result.

Let’s see the code,

Code in C++ for Alien Dictionary

unordered_map<int, vector<int> adj;
int* topoSort(int V) {
    
    int cnt[V]={0};
    
    for(int i = 0; i < V; i++)
    {
  	for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
  	{
	    cnt[*itr]++;
  	}
    }
    queue<int> q;
    
    for(int i = 0;i < V; i++) {
        if(cnt[i] == 0) q.push(i);
    }
    
    int *r = new int[V]; 
    int k = 0;
    
    while(!q.empty())
    {					
        int p = q.front();
  	q.pop();
  	r[k++] = p;
  
 	for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
  	{
      	    cnt[*itr]--;
      	    if(cnt[*itr] == 0) q.push(*itr);
        }
    }
    return r;
}

string printOrder(string dict[], int N, int k) {
    
    for(int i = 1; i < N; i++)
    {
        string str1 = dict[i-1];
        string str2 = dict[i];
        
        int x = 0;
        while(x < min(str1.length(),str2.length()))
        {
            if(str1[x] != str2[x])
            {
                adj[str1[x]-'a'].push_back(str2[x]-'a');
                break;
            }
            x++;
        }
    }
    
    int *r = new int[k];
    
    r = topoSort(k,adj);
    string s = " ";
    
    for(int i = 0; i < k; i++)
    {
        s += char(r[i]+'a');
    }
    return s;
}

Hope code is clear, we constructed the graph first and then did Topological Sort of that Graph, since graph is linear, Topological Sort will be unique.

We have discussed two problems on Graph and hope both problem and approach to them is clear to you. If you have doubts comment below.

It’s Ok if you are not able to solve the problem, just learn the approach to tackle it. We will be discussing other applications of Graph in next post.

That’s it folks..!!!