Problems on Topological Sorting

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,

topological sorting problem

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.

topological sorting problem

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 sorting problem

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..!!!

Tagged : /

Topological Sorting Algorithm

In this post, we are continuing with Graph series and we will discuss the Topological Sorting algorithm and some problems based on it.

Topological Sorting Algorithm is very important and it has vast applications in the real world. So, let’s start.

Directed Acyclic Graph

We have already discussed the directed and undirected graph in this post. So, now let’s discuss the cyclic and acyclic graph.

The simplest definition would be that if a Graph contains a cycle, it is a cyclic graph else it is an acyclic Graph.

In undirected graph, to find whether a graph has a cycle or not is simple, we will discuss it in this post but to find if there is a cycle present or not in a directed graph, Topological Sort comes into play.

Detect cycle in undirected Graph

Now let’s discuss how to detect cycle in undirected Graph. For that, let’s take an example,

Now let me ask you, what is the difference between the above two Graphs ..?

Yes, you guessed it right, the one in the left side is undirected acyclic graph and the other one is cyclic.

Why the graph on the right side is called cyclic ?

The reason is simple, there is at least two ways to reach any node of the cycle and this is the main logic to find a cycle in undirected Graph.

If an
undirected Graph is Acyclic, then there will be only one way to reach the nodes of the Graph.

Algo to find Cycle in undirected Graph

To find cycle, we will simply do a DFS Traversal and also keep track of the parent vertex of the current vertex. If parent vertex is unique for every vertex, then graph is acyclic or else it is cyclic.

Let’s see the code,

unordered_map<int, vector<int>> adj;
bool detect(int s, bool vis[], int parent)
{
    vis[s] = true;
    for(auto i = adj[s].begin(); i != adj[s].end(); i++)
    {
        if(vis[*i] == false)
        {
            if(detect(*i, vis, s) == true)
                return true;
        }
        else if(*i != parent){
            return true;
        }
    }
    return false;
}

For every vertex, the parent will be the vertex from which we reach the current vertex.

Initially, parents will be -1 but accordingly, we will update the parent when we move ahead.

Hope, code, and logic is clear to you. Let’s move ahead.

Detect Cycle in Directed Graph

For directed Graph, the above Algorithm may not work. Let’s see how,

The above Directed Graph is Acyclic, but the previous algorithm will detect a cycle because vertex 1 has two parents (vertex 2 and vertex 3), which violates our rule.

Although the above-directed Graph is Acyclic, the previous algorithm will detect a cycle. So the Algorithm fails.

To detect a cycle in a Directed Acyclic Graph, the topological sort will help us but before that let us understand what is Topological Sorting?

Topological Sort

We have discussed many sorting algorithms before like Bubble sort, Quick sort, Merge sort but Topological Sort is quite different from them.

Topological Sort for directed cyclic graph (DAG) is a algorithm which sort the vertices of the graph according to their indegree.

Let’s understand it clearly,

What is in-degree and out-degree of a vertex ?

OutDegree of a vertex (let say x) refers to the number of edges directed away from x .

Similarly,  In-Degree of a vertex (let say y) refers to the number of edges directed towards y from other vertices.

Let’s see an example,

topological sorting algorithm

Hope, concept of in-degree and out-degree is clear to you.

Now in Topological Sorting, we sort the vertices of graph according to their In-degree.

Let’s take the same example to understand Topological Sorting,

topological sorting

Topological Sorting of above Graph : 2 3 1

Let’s take another example,

topological sorting

Topological Sorting of above Graph : 0 5 2 4 1 3 6

There may be multiple Topological Sort for a particular graph like for the above graph one Topological Sort can be 5 0 4 2 3 6 1, as long as they are in sorted order of their in-degree, it may be the solution too.

Hope, concept of Topological Sorting is clear to you. Now let’s discuss the algorithm behind it,

Topological Sorting Algorithm (BFS)

We can find Topological Sort by using DFS Traversal as well as by BFS Traversal. We will discuss both of them.

Let’s first the BFS approach to finding Topological Sort,

Step 1: First we will find the in degrees of all the vertices and store it in an array. Let’s discuss how to find in-degree of all the vertices.

For that, the adjacency list given us will help, we will go through all the neighbours of all the vertices and increment its corresponding array index by 1.

Let’s see the code,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
}

Step 2 : We will declare a queue, and we will push the vertex with in-degree 0 to it.

Step 3 : We will run a loop until the queue is empty, and pop out the front element and print it.

The popped vertex has the least in-degree, also after popping out the front vertex of the queue, we will decrement in-degree of it’s neighbours by 1.

It is obvious, removal of every vertex will decrement the in-degree of it’s neighbours by 1.

Step 4: If in-degree of any neighbours of popped vertex reduces to 0, then push it to the queue again.

Let’s see the above process,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
    queue<int> q;

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

    while(!q.empty())
    {							            							        
        int p = q.front();
        q.pop();
        
        cout << p <<" ";
        
        for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
        {
            in_degree[*itr]--;
            
            if(in_degree[*itr] == 0) q.push(*itr);
        }
    }
}

That’s it, the printed data will be our Topological Sort, hope Algorithm and code is clear.

Let’s understand it by an example,

topological sorting algorithm

in_degree[] for above graph will be, {0, 2, 1, 2, 1, 0, 2}. Now let’s move ahead,

topological sorting algorithm

The above pictorial diagram represents the process of Topological Sort, output will be 0 5 2 3 4 1 6.

Time Complexity : O(V + E)
Space Complexity : O(V)


Hope concept and code is clear to you. Let’s move ahead.

Cycle Detection in Directed Graph

Since we have discussed Topological Sorting, let’s come back to our main problem, to detect cycle in a Directed Graph.

Let’s take an simple example,

topological sorting algorithm

In the example above, graph on left side is acyclic whereas graph on right side is cyclic.

Run Topological Sort on both the Graphs, what is your result..?

For the graph on left side, Topological Sort will run fine and your output will be 2 3 1.

But for the graph on right side, Topological Sort will print nothing and it’s obvious because queue will be empty as there is no vertex with in-degree 0.

Now, let’s analyse why is it happening..?

Significance of vertex with in-degree 0

As observed for the above case, there was no vertex present in the Graph with in-degree 0.

This signifies that there is no vertex present in the graph which is not connected to atleast one other vertex. You know what is signifies..?

It signifies the presence of a cycle, because it can only be possible in the case of cycle, when no vertex with in-degree 0 is present in the graph.

Let’s take another example,

topological sorting algorithm

Again run Topological Sort for the above example,

Graph

If we run Topological Sort for the above graph, situation will arise where Queue will be empty in between the Topological Sort without exploration of every vertex.

And this again signifies a cycle. Hope you understood the concept behind it.

Let’s see the code,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
    queue<int> q;

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

    int cnt = 0;
    while(!q.empty())
    {							            							        
        int p = q.front();
        q.pop();
       
        cnt++;
        
        for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
        {
            in_degree[*itr]--;
            
            if(in_degree[*itr] == 0) q.push(*itr);
        }
    }
    
    if(cnt != V) cout<<"Cycle Present\n";
    else cout<<"Cycle Not Present\n";
}

Hope code is simple, we are just counting the occurrence of vertex, if it is not equal to V, then cycle is present as topological Sort ends before exploring all the vertices.

Logic behind the Algorithm (MasterStroke)

The main logic of the above algorithm is that if there is a cycle present in a directed Graph, definitely a situation will arise where no vertex with in-degree 0 will be found because for having a cycle, minimum in-degree 1 is required for every vertices present in the cycle.

It’s obvious logic and hope, code and logic is clear to you all. Let’s move ahead.

Topological Sorting Algorithm (DFS)

Although this topic was not important as we have already discussed the BFS approach which is relatively easier to understand but sometimes in an interview, interviewer ask you to find Topological Sort by DFS approach. So it’s better to give it a look.

It is highly recommended to try it before moving to the solution because now you are familiar with Topological Sorting. So, give it a try for sure.

Let’s take the same example,

degree in graph

It’s clear in topological Sorting our motive is to give preference to vertex with least in-degree.

In other words, if we give preference to vertex with least out-degree and reverse the order of Topological Sort, then also we can get our desired result.

Let’s say, Topological Sorting for above graph is 0 5 2 4 3 1 6.

degree in graph

In above diagram number of out-degrees in written above every vertex.

If we sort it with respect to out-degree, one of the Topological Sort would be 6 1 3 4 2 5 0 and reverse of it will give you Topological Sort w.r.t in-degree.

Hope this is clear and this is the logic of this algorithm of finding Topological Sort by DFS.

Algorithm to find Topological Sort (DFS)

Step 1: Do a DFS Traversal and if we reach a vertex with no more neighbors to explore, we will store it in the stack.
2: Continue this process until DFS Traversal ends.

Step 3: Take out elements from the stack and print it, the desired result will be our Topological Sort. That’s it.

NOTE: Topological Sort works only for Directed Acyclic Graph (DAG).

Let’s see the code for it,

unordered_map<int,vector<int>> adj;
void f(int s, stack<int> &stack, bool vis[])
{
    vis[s] = true;
    for(auto i = adj[s].begin(); i != adj[s].end(); i++)
    {
        if(vis[*i]==false)
        {
            f(*i,stack,vis);
        }
    }
    stack.push(s);
}

void topological_Sort(int V) 
{
    bool vis[V] = {false};
    stack<int> s;
    
    for(int i=0;i<V;i++)
    {
        if(vis[i] == false)
        {
            f(i, s, vis);
        }
    }

    while(!s.empty())
    {
         cout << s.top() << " ";
         s.pop();
     }
}

Hope code is clear, it is simple code and logic is similar to what we have discussed before.

DFS Traversal sorts the vertex according to out-degree and stack is helping us to reverse the result. That’s it.

Time Complexity : O(V + E)
Space Complexity
: O(V)

I hope you enjoyed this post about the topological sorting algorithm. We will continue with the applications of Graph. See you later in the next post.

That’s all folks..!!!Wiki

Tree Traversals (Both Recursive and Iterative)

In this post, I am going to discuss basic DFS Tree Traversals in both recursive and iterative way.

The recursive way is a cakewalk but the iterative way is a trickier one to think, so I will try to derive iterative version from the recursive version solution.

So, let’s start,

Tree Traversals

There are two types of Tree Traversals-
(i) Depth First Search (DFS)
(ii) Breadth First Search (BFS)

We are going to discuss DFS Traversals in this post.

DFS Tree Traversals (Recursive)

DFS as the name suggests Depth First Search, in this traversal technique preference is given to depth of the tree, so it will try to traverse till it reaches the deepest nodes of the tree.

This algorithm starts from the root , traverses all the nodes firstly in left sub tree until it reaches the leaf node before exploring the nodes in right sub tree as well.

This Algorithm takes a sub tree first go as deep as it can until you hit the leaf node before taking the other paths.

Types of DFS Tree Traversal


tree traversals


Unlike linear Data Structures we can traverse Tree in many ways. The basics DFS Tree Traversals are PreOrder, InOrder and PostOrder Traversals and we will discuss it one by one.

Binary Tree is the combination of root, left subtree and right subtree. Our traversal methods basically decides the order in which way we want to visit.

typedef struct TreeNode
{
     int data;
     struct Node *left;
     struct Node *right;
} TreeNode;

PreOrder Tree Traversals

In PreOrder Traversal, we will visit root node first, then its left subtree and then right subtree. So here preference of the order is given to root node.

tree traversals
PreOrder Traversal : A B D E C F G

In above Tree we visit root A first, then move to its left subtree. Again in that subtree we print B first as it is the root of that subtree. This way we traverse whole tree.

Preference of the Order will be given to root first then to left subtree and at last right subtree.

Recursive Code in C/C++

void PreOrder(TreeNode *root)
{
     if(root == NULL) return;
     printf("%d ", root->data);
     PreOrder(root->left);
     PreOrder(root->right);
}

InOrder Tree Traversals

In InOrder Traversal, we will visit left subtree first, then explore the root and at last right subtree.

tree traversals
InOrder Traversal : D B E A C G F

In above Tree we will go to left subtree until it is NULL (A-> B-> D-> NULL) then we will visit the root D first, since root D doesn’t have right child so we will return to previous recursion call, print node B then move to its right subtree to print E. This way we traverse whole tree.

Preference of the Order will be given to left subtree first then to root of the subtree and at last right subtree.

Recursive Code in C/C++

void InOrder(TreeNode *root)
{
     if(root == NULL) return;
     InOrder(root->left);
     printf("%d ", root->data);
     InOrder(root->right);
}

PostOrder Tree Traversals

In PostOrder Traversal, we will visit left subtree first, then right subtree and at last we will explore the root.

tree traversals
PostOrder Traversal : D E B G F C A

In above Tree we will go to left subtree until it is NULL (A-> B-> D-> NULL) then we will go to its right subtree since root D doesn’t have a right child so we will print root D, return to previous recursion call, then move to its right subtree to print E and at last print B. This way we traverse the whole tree.

Preference of the Order will be given to the left subtree first then to right subtree and at the root of the Tree.

Recursive Code in C/C++

void PostOrder(TreeNode *root)
{
     if(root == NULL) return;
     PostOrder(root->left);
     PostOrder(root->right);
     printf("%d ", root->data);
}

DFS Tree Traversals (Iterative)

Recursive Solutions are cakewalk and hope you understood it well, now I am going to discuss iterative solutions. Iterative Solutions are asked in interviews and it is not so easy to think it in that way.

Iterative PreOrder Traversal

For understanding iterative Solutions, you must be clear with the recursive solution. I will try to derive an iterative solution from a recursive solution.

Let’s take an example,

tree traversals

Try to draw a recursion diagram for the above tree.

tree traversals

This is how Recursion Tree looks like and if you observe it clearly, recursion uses a virtual stack to perform its operation.

Like for performing operations on ‘D’, ‘B’ was in that stack, similarly for performing activity on ‘B’, ‘A’ was in the stack.

Let’s see it diagrammatically how recursion uses the virtual stack.

tree traversals
tree traversals

This is how the virtual stack works in recursion. In the iterative solution, we just have to replace the virtual stack with the real stack to perform these operations.

I hope you are getting this idea clearly. This is the basic idea of the iterative solution.

Conversion of Recursive to Iterative Solution

Now forget about Recursion, just try to analyse the working of stack and that’s it, we just have to write code accordingly.

(i) First, we will push root in the stack and print its data.
(ii) Then move to its left node, if the left node is present, we will again push it into the stack.
(iii) Continue this process until the left node is NULL.

(iv) Else, pop from the stack and check whether the right node of the popped data exists or not.
(v) If it exists then again check for the left node as we did before.
(vi) If not we will continue to pop nodes from the stack.

Let’s see its code,

void PreOrder(TreeNode* root) {

   if(root == NULL) return;

    stack<TreeNode*> st;
    TreeNode *ptr = root;

    while(1)
    {   
        if(ptr)
        {
            st.push(ptr);
            printf("%d ",ptr->data);
            ptr = ptr->left;
        }
        else
        {
            if(st.empty()) break;
            TreeNode *temp = st.top();

            st.pop();
            if(temp->right) ptr = temp->right;
        }
    }
}

Yes, this is the code, it is just the reflection of the logic which we discussed earlier. So, I think code must be clear.

Iterative InOrder Traversal

Iterative InOrder Traversal is similar to iterative PreOrder Traversal.

In previous code, we were pushing root to the stack, then printing root’s data, and then we were moving to it’s left node.

Here, we have to push the root to the stack until root-> left is not NULL and then while popping nodes we will print that node’s data, and lastly, we will move to its a right node.

void inOrder(TreeNode* root) {

    if(root == NULL) return v;

    stack<TreeNode*> st;
    TreeNode *ptr = root;

    while(1)
    {   
        if(ptr)
        {
            st.push(ptr);
            ptr = ptr->left;
        }
        else
        {
            if(st.empty()) break;
            TreeNode *temp = st.top();

            printf("%d ", ptr->data);

            st.pop();
            if(temp->right) ptr = temp->right;
        }
    }
}

Iterative PostOrder Traversal

Iterative PostOrder will be different from the above two. The reason behind it is because in PostOrder Traversal we are simultaneously pausing two recursive calls.

Let’s understand it more clearly,

tree traversals

For this above tree, first left part will be processed then right part will be processed at last root will be explored.

Let’s see it’s recursion diagram,

tree traversals

For processing Node B, first node D will get pause and then node E will get pause simultaneously.

So at a time, two recursive calls will get pause, so this is the reason behind the complex iterative PostOrder Traversal.

But once if you can analyse it with the help of virtual stacks, things will be clear.

Let’s start,

tree traversals

Now, D->left = NULL, so now we have to check whether D->right is present or not. Here D->right is NULL.

So, we print D, and then we pop the topmost element from the stack. (D)

Now, topmost element in stack is B, so we have to explore it’s right part of it first. Here we will get stuck because we don’t have any information whether right child of that node is present or not.

How to Overcome this problem ?

So, to overcome it, what we will do, we will put right child of the root node first in the stack and then the root, so this will give help us to retrieve the identity of right child, where we got stucked above.

Let’s understand it by the diagram,

tree traversals

Now D doesn’t have left child as well as right child, so we will print D and we will pop it from the stack.

Set topmost element (B) of the stack as root, and pop it, now check if root->right (E) is the topmost element in stack, if yes then it confirms that root has right child as well.

Hope you get this idea clearly, this is the main logic of the iterative post Order Traversal.

Let’s see stack diagram for the entire Tree and then we will write the Algo and code accordingly.

tree traversals
tree traversals

This is the stack diagram of the PostOrder Iterative Traversal. Let discuss what we did,

(i) Push right child of the root and root to the stack and move to its left node, until root is NULL.
(ii) Pop the stack and if popped node equals topmost node of stack, then that node has right child as well.
(iii) If right child is present then pop the right child push that node and set current node as right child.
(iv) Continue it until stack is empty. That’s it

Let’s see the code for better clarification,

void postOrder(TreeNode* root) {

    stack<TreeNode*> st;
    TreeNode* ptr = root;
    
    while (!st.empty()) 
    {
        if (ptr) 
        {
            st.push(ptr);
            
            if(ptr->right) st.push(ptr->right)
            ptr = ptr->left;
        } 
        
        else 
        {
            ptr = st.top();
            st.pop();
            
            if (ptr->right == st.top()) 
            {
                st.pop();
                
                st.push(ptr);
                ptr = ptr->right;
            } 
            
            else {
                printf("%d ",root->data);
                ptr = NULL;
            }
        }
    }
}

I hope this explanation and code are clear to you.

I have discussed Tree DFS Traversals in both the Recursive and Iterative approaches. I hope it is clear.

That’s all folks..!!!

Learn Clone A linked List

Learn Rat in a maze problem

Learn Celebrity problem MasterStroke

Learn Duplicate and Missing Number

Tagged : /

Clone a linked list with next and random pointer

Leetcode Problem 138

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. We need to clone-a-linked-list-with-next-and-random-pointer. Read rat in a maze problem here

Return a deep copy of the list.Aka clone-a-linked-list-with-next-and-random-pointer.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val : an integer representing Node.val
  • random_index : the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

clone a linked list
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

clone a linked list
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Another Example 3:

clone a linked list
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Analysis of Problem Statement

The problem seems quite confusing and it is but let us understand it clearly. We are basically given a Linked List where each nodes have three field.

clone a linked list

Basically the structure of the node of the Linklist will look like,

struct Node  
{
     int data;
     struct Node *next;
     struct Node *random;
};

The node has its data and it also stores two pointers (Next and Random). Next Pointer stores the address of Next Node and Random Pointer stores the address of any Random Node, it can be NULL as well.

So, we are given a link list where each node stores this information. Our task is to create a new link list which is a copy of the given link list. Learn Two pointer algorithm

Approach to the Problem

I hope the Problem Statement is clear to you. This problem is a bit different from other Linklist Problems but doesn’t worry we will understand it step by step.

Our motive is to just create a copy of the given link list.
So, for that, we have to create new nodes.

How to create new nodes..??

In C/C++, we create nodes dynamically by using malloc() and new() keywords.

Normally, we have to create a new node of a Node type and we have to assign data to it.

But here GFG has already created the constructor for us, we just have to create a new node and have to pass data as a parameter. Learn Subtree problem in data structure

Node *head = new Node(x->data);

Here we are creating a linklist node of type ‘Node’ and assigning x’s data to it. The next and random will be NULL initially as mentioned in the constructor.

Hash – Map based Approach

Since we have to clone/copy the original linklist, we will definitely need some data structure to store the information of nodes of original linklist.

For that we will use hash-map where key will be the nodes of original linklist and value will be the nodes of cloned linklist.

Assign Data and next Pointer to the new node

In the first step, for each node in the original linklist we will create a new node with same data and then we will recursively assign its next Pointers.

Let’s understand it clearly with an example,

clone a linked list

Suppose this is the original Linklist given to us and we have to cloned it to new Linklist.

Let us give some address to the nodes of original linklist, it will be easy for us to understand.

clone a linked list

Now, I will create a new Node and I will assign it’s value to it. Let do it.

clone a linked list

This is the new node we created with the same node value.

NOTE we have not assigned it’s next and random pointer yet and also the address of the new node is different.

Now, we will assign next pointer to the new node and for that we will use recursion. Let’s see how.

Node* copyRandomList(Node* head) 
{
    if(head == NULL) return NULL;

    Node* newhead=new Node(head->val);
    newhead->next = copyRandomList(head->next);

    return newhead;
}

This is how recursive function will work. Here we have only assigned next pointer to the cloned linklist.

The pictorial diagram below make recursion more clear.

clone a linked list with next and random pointera
clone a linked list with next and random pointera
clone a linked list with next and random pointer

Nodes of cloned linklist will be created for every nodes of original linklist and at the same time we are actually assigning the next pointer of previous node to the current node of the new linklist.

If you are unable to understand the above, take a pen paper and dry run on it.

Assign random Pointer to the new node

We have already assigned the data values and next pointers to the nodes of new linklist. Now, we have to assigned the random pointer to it with respect to original linklist.

Since random pointers are random, so here we will need a data structure to store the random pointers of original linklist and accordingly we will assign the random pointer to the nodes of new linklist.

For this purpose we will use hash-map, let see how it will help us.

clone a linked list with next and random pointera

We will use the same example,

We will first create a hash-map where key will be the nodes of original linklist and value will be the nodes of cloned linklist.

clone a linked list with next and random pointera

What is the purpose of using hash-map ?

Let us understand what we need a hasp-map here.

clone a linked list with next and random pointera

Random Pointer of address 275 is 425 in the original linklist as mentioned in the diagram.

Value of the map with key 275 is 900. It means node with address 275 of original linklist corresponds to node with address 900 in new linklist.

Now, we know random pointer of 275 is 425, so we will set the random pointer of the node 900 to the value of the map with key 425.

And here the role of map comes to play. Hash-Map actually stores the resemblance of nodes of new linklist with respect to original linklist.

Hope I can able you to understand how we will set the random pointer.

newhead->random = copyRandomList(head->random);

After that we will find the random pointer in the map, if found we will return it’s value.

if(m.find(head) != m.end()) return m[head];

Hope this above part is clear to you, let us see the full code.

unordered_map<Node*,Node*> m;
Node* copyRandomList(Node* head) 
{
    if(head == NULL) return NULL;

    if(m.find(head) != m.end()) return m[head];

    Node* newhead=new Node(head->val);

    m[head]=newhead;

    newhead->next = copyRandomList(head->next);
    newhead->random = copyRandomList(head->random);

    return newhead;
}

Hope the above code is clear to you. Dry run above code and you will understand it clearly.

Time Complexity : O(n)
Space Complexity: O(n)


Since we are using a hash-map, the space complexity increases to O(n). But can you solve it in constant space?

NOTE: The space required for a new link list is not considered under space complexity because it is part of the problem. For constant space complexity, you cannot take any further extra space.

We will discuss the constant space solution in the next post. Till then try to understand clone-a-linked-list-with-next-and-random-pointer this approach and try to think of the constant space complexity approach as well.

That’s all folks..!!!

Tagged : /

Two Pointer Algorithm

Today we are going to discuss a trending Algorithm which is used frequently for solving problems the Two Pointer Algorithm.

In this post, we will first understand the Two Pointer Algorithm and then we will solve 2-3 problems based on it. Also, I will give problems for practice so that you can understand this Algorithm more clearly. So let’s start[Greedy Algorithm].

Technical Definition

Two Pointer Technique uses two-pointer in one loop over the given data structure. It is commonly used for solving array, string, linked list coding problems.

The main purpose of this algorithm is to reduce the complexity of O(n^3) or O(n^2) based solution to Linear time solution.

Common patterns in the two pointer algorithm approach involve-

(i) Two pointers each starting from the beginning and the end until they both meet.
(ii) One pointer moves at a slow pace while the other pointer moves at a faster pace.
(iii) Pointer-I and Pointer-II from two sequences.

We will discuss Questions to discuss the following Patterns.[Merge Sort Algorithms][Bubble Sort Algorithm]

Nth node from end of linked list

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Input:
The first line of input contains the number of testcase T. For each testcase, the first line of input contains the number of nodes in the linked list and the number N. The next line contains N nodes of the linked list.

Output:
For each testcase, output the data of node which is at Nth distance from the end or -1 in case node doesn’t exist.

User Task:
The task is to complete the function getNthFromLast() which takes two argumentsreference to head and N and you need to return Nth from the end.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= T <= 200
1 <= L <= 103
1 <= N <= 103

Example:
Input:
2
9 2
1 2 3 4 5 6 7 8 9
4 5
10 5 100 5

Output:
8
-1

Explanation:
Testcase 1:
 In the first example, there are 9 nodes in linked list and we need to find 2nd node from end. 2nd node from end is 8.  

Testcase 2: In the second example, there are 4 nodes in the linked list and we need to find 5th from the end. Since ‘n’ is more than the number of nodes in the linked list, the output is -1.

Analysis of Problem Statement

The problem seems simple and you might be thinking why the hell I am discussing this Question.

Yes, Problem Statement is simple and also the solution too but if I bring one extra constraint to this Question, then this problem becomes interesting.

And my motive to discuss any question is that you should learn something from it.

Naive Solution

I think the Problem statement is clear. You have to find the nth node of the linked list from the end.

The solution is simple, just count the number of nodes present in the linked list in the first traversal and then find the Nth node from the end in the second traversal.

Let’s see it’s code,

int getNthFromLast(Node *head, int n)
{
     Node *t = head,*t1 = head;  
     int k = 0;
     
     while(t != NULL)  
     {
         t=t->next;   
         k++;
     }
     if(k < n)  return -1;
     else
     {
         for(int i = 0; i < (k - n); i++)   
         {
             t1 = t1->next;
             
         }
         return (t1->data);
    }
}

I think above code is simple and time complexity is also O(n) but what if I tell you that you have to find the nth node from the end in just one traversal.

I mean that in the above code you need two traversal to find the result, but can you find the result in just one traversal.

It is highly recommended to think of a way to approach this problem in only one traversal.

Nth node from end in just One Traversal

The logic behind this solution is based on Two Pointer Approach. Let’s understand it more clearly.

Let’s take an example,

two pointer algorithm

And in the above we have to find 3rd node from end.

Now in the previous approach we were first traversing from 1st node to last node and then we were coming backward to find nth node from end or (k-n)th node from the front in the second traversal.

Do we need to go to the last node and come back again..??

To understand it clearly, let’s do a bit of Mathematics.

Let’s assume there are ‘k’ number of nodes with us. And we have to find nth node from the back.

two pointer algorithm

Now nth node from the back is actually (k-n)th node from the front.

two pointer algorithm

Now let us understand one thing, We can achieve this by another process too.

two pointer algorithm

In this algorithm, we will declare two-pointer both initialised to head initially. Now we will move Pointer 1 till Nth node. When Pointer 1 reaches the Nth node, at the same time we will move Pointer 2. We will move both the pointers simultaneously till Pointer 1 reaches the last position.

The distance travelled by both the pointer will be same after Pointer 1 crosses Nth node.

Now Total distance travelled by Pointer 1: K
Total distance travelled by Pointer 2 : (K – n)

Let us analyse how Pointer 2 travelled (K – n) distance from the front. How we are sure about it?

The reason behind is that when we started Pointer 2 to move, when Pointer 1 was at position N. So after that distance travelled by Pointer 1 is (K-n) which is same as distance travelled by Pointer 2 as well. But since Pointer 2 started it’s journey from starting point, that’s why total distance travelled by Pointer 2 is (K-n-0) which is (K – n) and the node present at this position is our resultant node.

Hope you understood the logic behind this Algorithm. This is one application of Two Pointer Approach.

Let’s see the code,

int getNthFromLast(Node *head, int n)
{
    Node *ptr1 = head, *ptr2 = head;
    for(int i=1; i <= n-1; i++){
        ptr1 = ptr1->next;
        if(ptr1 == NULL) return -1;
    }
    
    while(ptr1->next != NULL){
        ptr2 = ptr2->next;
        ptr1 = ptr1->next;
    }
    return ptr2->data;
}

In this way, we can find nth node from end in just one traversal. Now let’s move ahead to solve one more Question.

Problem : Key Pair[Two Pointer Algorithm]

Given an array A of N positive integers and another number X. Determine whether or not there exist two elements in A whose sum is exactly X.

Input:
The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N and X, N is the size of array. The second line of each test case contains N integers representing array elements A[i].

Output:
Print “Yes” if there exist two elements in A whose sum is exactly X, else “No” (without quotes).

Constraints:
1 ≤ T ≤ 100
01 ≤ N ≤ 105
1 ≤ A[i] ≤ 105

Example:
Input:

2
6 16
1 4 45 6 10 8
5 10
1 2 4 3 6

Output:
Yes
Yes

Explanation:
Testcases 1:
 10 and 6 are numbers making a pair whose sum is equal to 16.

Naive Method

Naive Method is to run two nested loops and find that if two numbers add up to the specific target or not. This process takes O(n^2) time complexity.

bool twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) 
    {
        for (int j = i+1; j < nums.size(); j++) 
        {
            if (nums[i] + nums[j] == target) {
                return true;
            }
        }
    }
    return false;
}

Two Pointer Approach

We can reduce the complexity to O(n) by Two Pointer Approach. Let’s see it.

Since Array is sorted, we can use two Pointer here. We will keep one pointer at the first element and second pointer at the last element.

Since Array is sorted, if sum of both the element if greater than target sum, we will update out second pointer or else we will update our first pointer.

Let’s see it’s code.

bool twoSum(vector<int>& nums, int target) {

        int pointerOne = 0;
        int pointerTwo = nums.size() - 1;

        while (pointerOne < pointerTwo) 
        {
            int sum = nums[pointerOne] + nums[pointerTwo];

            if (sum == target) {
                return true;
            } 

            else if (sum < target) {
                pointerOne++;
            } 

            else {
                pointerTwo--;
            }
        }
        return false;
    }

We will discuss more Problems on Two pointer algorithm in our next Post. Hope you understood the basics of Two Pointer Approach.

That’s all folks..!!!

Tagged : /