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 : /

Clone a link list with next and random Pointer (Part II)

In the previous post, we have already discussed the map-based solution of the problem clone a link list with next and random pointer.

The map-based solution took O(n) extra space but in this post, we will discuss constant space complexity based solutions.

NOTE: The space required for creating 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.

Now let us understand the constant space complexity approach.

Problem with the Previous Solution

If you remember the map based solution, for the first part of the problem, for assigning data and next Pointer to the nodes of the new linklist we actually didn’t use the map as all.

The only purpose of the hash-map was to assign random pointers to the nodes of new linklist. Isn’t it ?

What was the actual role of the hash-map in our previous solution ?

If you understand this part, it will be easy for you to crack constant space complexity solution. Let’s understand this part clearly.

We will take the same example from the previous post,

CLONE A LINK LIST

This was the example we used, here we already have the information about the random pointer of nodes of the original linklist.

Also we know which node in original linklist corresponds to which node in new linklist and we were getting this information via hash-map.

Hash-map actually stores the resemblance of nodes of both the linklist. Isn’t it ?

So it’s like we have two information and from there we are finding the third information.

Do we really need a hash-map to store the resemblance ?

Can’t we get this information without using a hash-map ?

The basic idea to this approach is that we already know that total number of nodes in both original and new linklist will be same.

And it’s obvious that first node of original linklist resembles to first node of new linklist, second to second and it goes on.

We will use this information for our constant space based solution.

Idea behind Efficient Solution

CLONE A LINK LIST

The first one is the original linklist and the second one is the cloned linklist.

We will first point the next pointers of the nodes of original linklist to its corresponding node in the new linklist.

At the same time we will point the random pointers of the node of new linklist to its corresponding node in original linklist.

CLONE A LINK LIST

This transformation will help us finding the random pointers of nodes of new linklist.

First let’s discuss how we will convert the linklists to the above form.

We had already assigned data and next pointers to the nodes of new linklist.

Let’s see the code to transform the linklist,

Node *ptr = set_data_and_next_pointers(head);

Node *x = head;
Node *y = ptr;

while(x != NULL)
{
     Node *next_node = x->next;

     y->random = x;
     x->next = y;

     x = next_node;
     y = y->next;
}

‘ptr’ stores address of head of new linklist.

We will make a copy of both the head pointers so that we can keep the address of original head node of both linklists.

Let say ‘x’ stores address of head of original linklist and ‘y’ stores address of head of new linklist.

Now we will run a loop until (x != NULL) and according we will transform both the linklist.

Let us understand it by an example,

CLONE A LINK LIST
Node *next_node = x->next;
Here we store the address of next pointer of 'x' in next_node variable.

y->random = x;
x->next = y;
Here we set random pointer of 'y' to node 'x'. Also we set next pointer of 'x' to node 'y'.

x = next_node;
y = y->next;
At last we move ahead to transform the random and next pointer of next nodes.

This way we will move ahead and transform both the linklist, hope above code is clear to you all.

Why we did the above transformation ?

Now the questions arises, why we did the above transformation. The reason is hidden in the above pictorial diagram.

The idea behind the transformation is that now we can easily get the information of random pointers for the nodes of new linklist.

Let’s see how,

CLONE A LINK LIST

What will be address of the random pointer with node 4 ?

Let say node 4 is denoted by ‘y’, then (y->prev->prev->next) will give us that information about random pointer.

Yes, this is the masterstroke logic behind this algorithm. Now we can get the information about previous node in just O(1) time complexity.

We will run a loop from head pointer of new linklist till it becomes NULL and update the random pointers accordingly.

The code snippet will be,

y = ptr;
while(y != NULL)
{
     if(y->random->random == NULL) {
             y->random = NULL;
    }
    else 
    {
            y->random = y->random->random->next;
     }
     y = y->next;
}

Hope, you understood the above code, one extra condition we give there if random pointer of nodes of original linklist is NULL, then (y->random) will also be NULL. That’s it.

Hope above code and logic behind it is clear to you all.

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


Yes we didn’t use any extra space for creating new linklist instead we did some transformation and got the result.

Code in C/C++

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

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

    return newhead;
}

Node *copyRandomList(Node *head) {

    if(head == NULL) return NULL;

    Node *ptr = set_data_and_next_pointers(head);

    Node *x = head;
    Node *y = ptr;

    while(x != NULL)
    {
         Node *next_head = x->next;

         y->random = x;
         x->next = y;

         x = next_head;
         y = y->next;
    }

     y = ptr;

     while(y != NULL)
     {
         if(y->random->random == NULL) y->random = NULL;
         else y->random = y->random->random->next;
         y = y->next;
     }

     return ptr;
}

I hope the above explanation for Clone a link list with next and random Pointer is clear to you all.

That’s all folks..!!!

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 : /

Rat in a Maze Problem (Backtracking)

Problem Statement

The problem is a rat in a maze problem. Consider a rat placed at (0, 0) in a square matrix of order N*N. It has to reach the destination at (n-1, n-1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

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 two lines. The first line contains an integer N denoting the size of the square matrix. The next line contains N*N space-separated values of the matrix m where 0’s represents blocked paths and 1 represents valid paths.

Output:
For each test, case output will be space-separated sorted strings denoting all directions, which the rat could take to reach the destination. Print -1 if no such path exists.

User Task:
Your task is to complete the function printPath() which returns a sorted array of strings denoting all the possible paths which the rat can take to reach the destination at (n-1, n-1). If no such path exists the function should return an empty array.

Constraints:
1 <= T <= 100
2 <= N <= 5
0 <= matrix[i][j] <= 1


Example
Input:

3
4
1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1
4
1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1
2
1 0 1 0 

Output:
DRDDRR
DDRDRR DRDDRR
-1
Explanation:
Testcase 2: The given input is in the form
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR when printed in sorted order we get DDRDRR DRDDRR.

Analysis of Problem Statement

You are given 2-D matrix of size N*N and you have to find all paths so that rat can reach the maze. In N*N matrix ‘1’ signifies that you can move to that block and ‘0’ signifies that you cannot move to that block.

Rat is initially at (0,0) cell and maze is present at (N-1,N-1) cell. Now you have to find all paths if present for the rat to reach its maze.

rat in a maze problem
rat in a maze problem

In the above example, there is one path present. Your task is to print the direction in which rat should move to reach it’s destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

Output : DRRURRDDLDDR

If multiple paths are present you should print all the paths separated by a space.

Hope Problem Statement is clear.

Approach to the Rat in a maze problem

This is clearly a backtracking Problem, where we have to find the path from source to destination.

To solve this puzzle, we first start from the source and move in a direction where the path is not blocked. If taken path makes us reach to the destination then the puzzle is solved else, we come back and change our direction of the path taken.

Here we will write a recursive Algorithm which will search it’s path by it’s own, we just need to specify some of the conditions and rest work will be done by recursion itself.

Let’s move step by step so that we can understand the algorithm clearly.

Recursive Function

It’s clear that we will solve this problem by using recursion. So, let’s discuss the approach to write the recursive function.

Base Condition for the Recursion

The base condition will be simple, we cannot go out of the square matrix, and also we cannot move to the block with integer ‘0’ because ‘0’ means path is blocked.

Also, we will keep track of a visited array, to insure that we are not visiting the same block which we crossed earlier. So if the block is already visited, we will simply return it.

So, these are the base condition required for our algorithm.

Let see the code for base condition,

if(i < 0 || i >= n || j < 0 || j >= n)
{
    return;                // For not going out of the square matrix
}
if(m[i][j] == 0){
    return;                // For not going to the blocked area
}
if(vis[i][j] == 1){
    return;                // For not going to the visited block 
}

Hope above base condition is clear to you, these are very simple conditions. So, let’s move ahead.

Main body of the Recursion

For the sake of simplicity, let’s first find the path for the rat to reach the maze or let us first check whether there is any path present or not for the rat to reach the maze.

Later, we will modify the recursion to also find the direction of the path.

The body of the recursion will be simple, the rat can move only in four directions. So if the current position of the rat is M[x][y], then it can move to M[x-1][y], M[x+1][y], M[x][y-1], M[x][y+1]. Isn’t it?

It is as simple as that and this is the information we need to specify in the body of the recursion and rest work will be tackled by our base condition.

So, let’s see the code and we will then understand it by an example.

Code

int cnt = 0;
void dfs(int m[MAX][MAX],int i,int j,int n,int vis[MAX][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;                
    if(m[i][j] == 0 || vis[i][j] == 1) return;        
    
    if(i == n-1 && j == n-1)
    {
        cnt++;
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
  
    dfs(m,i-1,j,n,vis);
    dfs(m,i+1,j,n,vis);
    dfs(m,i,j-1,n,vis);
    dfs(m,i,j+1,n,vis);
    
    vis[i][j] = 0;
    return; 
}

If we reach the coordinate M[n-1][n-1] then count will get updated from that we will know if there is any path present or not.

Let us understand the code step by step and also with an help of a example.

The parameters of the recursive function are simple, the matrix M[][], the coordinates [i][j], the size of the array N and the visited array for keeping the track of the path.

rat in a maze problem

This is the 2-D Matrix given to us and we are currently at the source M[0][0] and we have to reach the maze present at M[3][3].

Now let us analyse the recursion by the help of below diagram.

rat in a maze problem

Hope, the above diagram is clear. The recursion tree is incomplete but the process will go on like this.

Note the recursive call which are returning is actually going to our base condition.

dfs(-1, 0) is actually going out of the square matrix.
dfs(0, 0) is actually visited before, so it is returned.

By going this way, this Algorithm will find it’s own path. Hope the recursion body is clear to you. If not clear then try to draw a recursion diagram by taking a small example and try to follow the steps which I have mentioned above.

What if a path is found ??

Now suppose the above algorithm finds a path by the above recursion but this is not the end of our solution.

We need to find all the path from source to destination. So for this we will again return back and we will unvisit the visited block, so that it can find more ways to reach the destination.

We will try to understand this part by taking an small example,

rat in a maze problem

In the above example, there are two paths to reach destination. We will see it’s recursion tree to understand how we will find both the paths.

rat in a maze problem

The first path is found, now our task is to find the second path, for this we will unvisit the remaining nodes and we will try to find the other path.

rat in a maze problem

This is how, recursion will find the second path, first it will unvisit the visited node (marked by grey) and then recursion will continue. This way it will find the second path.

Hope recursion is clear and now I hope you can visualize the bigger picture that how rat is finding it’s own way to reach the maze.

Solution to the Rat in a maze Problem

We have discussed the main logic of the problem and now we need to wrap up all the above discussion to solve the actual problem.

In the actual Problem, we have to find the way as well as we have to specify the direction in which rat has to travel to reach the maze.

We will use string to store the directions and when we reach the destination, we will store that string to the vector and at last we will return that vector.

Let’s see the code for it,

Complete Code for C/C++

vector<string> s;

void dfs(int m[][MAX],int i,int j,int n,string st,int vis[][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;
    if(m[i][j] == 0 || vis[i][j] == 1) return;
    
    if(i == n-1 && j == n-1)
    {
        s.push_back(st);
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
    
    st.push_back('U');
    dfs(m,i-1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('D');
    dfs(m,i+1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('L');
    dfs(m,i,j-1,n,st,vis);
    st.pop_back();
    
    st.push_back('R');
    dfs(m,i,j+1,n,st,vis);
    st.pop_back();
    
    vis[i][j] = 0;
    
    return;
    
}
vector<string> printPath(int m[MAX][MAX], int n)
{
    string st = "";
    s.clear();
    
    int vis[MAX][MAX];
    for(int i = 0;i<n;i++){
        for(int j=0;j<n;j++){
            vis[i][j] = 0;
        }
    }
    
    dfs(m,0,0,n,st,vis);
    sort(s.begin(),s.end());
    return s;
}

Note if no such path exists the function should return an empty vector. Don’t print (-1) for that case as it is clearly mentioned in the Problem Statement. The (-1) case will be handled by GFG.

I hope this explanation of rat in maze problem and working of Recursion are
clear to you all.

That’s all folks..!!!

Similar Problem : Find whether path exist

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 : /