Batman And The CRIME !!

Batman is a savior of Gotham city. He has to save the city from the wrath of joker. So the batman asks Alfred (his tireless and faithful butler) to find a way to stop the deeds of the Joker. 

Batman wants to reach the crime scene as soon as possible from his cave. Alfred marks Joker’s probable crime scenes on Gotham's map. Whenever crime happens, Alfred receives coordinates of the scene by intercepting radio signals of Gotham Police.

Now as Batman wants to reach a crime scene as soon as possible, he asks Alfred about the shortest route to the crime scene from his cave. Now, you are Alfred and your task is to help Batman by telling him the shortest route to the crime scene.

You are given a 2D array A where A[i][0] and A[i][1] are coordinates of probable crime scene and A[i][2] is the distance between them. You are also given an array C, where each C[i] denotes the coordinate of the crime scene.

For each crime scene C[i], return the shortest distance to that coordinate from the Batman’s cave B.

It's an easy problem, right? Okay, let’s look into some examples to understand the problem better.

Example 1:

Input:

B = 0

A = [ [ 0 1 3 ]

        [ 0 3 4 ]

        [ 0 2 5 ]

        [ 3 2 3 ]

        [ 1 2 1 ] ]

C = [ 1 3 2 ]

Output:

[3 4 4]

Explanation

Let us plot the coordinates and see what we get. Now plotting these coordinates we get the following graph

We can clearly see that Batman’s cave is at 0. Now for crime scene 1 the shortest and the only distance is 3. For crime scene 3, the shortest distance is 4. Now to reach crime scene 2 we have 3 ways (0 > 1 > 2, 0 > 3 > 2, 0 > 2) with distances 4, 5, 7 respectively. Among these distances minimum is 4.

Now, how do we help Batman with this? Let’s look towards our very first approach to solve this.

Approach 1:

What we can do is, we can find all the paths from source to all other nodes and from these paths, we store the path with minimum distance. Let us find the time complexity of this approach. In the worst case the time complexity to find all the paths between two nodes is 

O(V * (V + E)) where V is number of nodes and E is number of edges.

Following this approach will make you find all the possible paths which is awesome if we have few nodes and edges. What if we have Nodes and edges in the range of let’s say 10^5 ?

Let’s look into a case to understand why this approach has high time complexity. Consider the following scenario :

Suppose we want to find the shortest distance from source (0) to destination (5), we will use strategies like BFS or DFS to find all the paths from source to destination. Clearly, we have a path (0 > 1 > 3 > 4 > 5), which is shortest, but we end up finding all other paths from source to destination in the search of minimum distance. And why are we doing so? Exactly, we are doing so because we are not certain that the path which we have found will give the minimum distance.

If we have that certainty, then we can find the shortest distance with much less effort. 

This approach will surely doesn’t work for large inputs. So what do we do now? To find an optimal solution, we always draw some observations. Let’s try to draw some.

Suppose we have a node N, a set of edges (directed from N) E = [e1, e2, e3…..] and corresponding weights of edges W = [w1, w2, w3…..]. If we sort the edges based on weights in ascending order then the edge with the minimum weight would be the shortest path to that corresponding node. For example, we have E = [1, 2, 3] and W = [3, 8, 6], now we can say that the minimum weight i.e 3, will be the minimum distance from N to the corresponding node i.e 1 in this case. In this, we are picking up the smallest distances greedily and also we are traversing the graph in BFS fashion. So here we can say that we need an algorithm which is a combination of BFS and greedy approach and here Dijkstra’s Algorithm comes to our rescue.

For code and time complexity of brute force approach refer to this github repository

Now let us look into another optimised approach.

Approach 2:

We will use Dijkstra’s algorithm to solve this problem. The algorithm is as follows:

Prerequisites

Data structures used in the algorithm are:

1. Priority Queue (min heap) (PQ) as we need an edge with minimum weight optimally.

2. An integer array named distance where distance[i] represents shortest distance of ith node from source.

3. An integer array named parent where parent[i] represents the parent of the node. Why do we have this mapping? This mapping is optional but it is good to have it because this mapping helps to trace all the shortest paths.

Approach used in the algorithm are:

1. Breadth First Search (BFS)

2. Greedy

Before applying this algorithm let us do some initialisations:

1. Initialise distance[i] to a very large value (to denote infinity). Why? Because this large value of distance[i] denotes that there is no way to reach node i from source.

Add the source node to the priority queue (PQ) (min heap) with distance = 0. Why? Because the minimum distance of the source node to itself is 0. (distance[0] = 0)

Dijkstra’s Algorithm and Time Complexity

The algorithm is as follows:

1. Since PQ is not empty, we poll the PQ and add to the distance array. Correspondingly add an entry to parent mapping. Let this polled node be n. If PQ is empty then we terminate this algorithm.

2. If distance[n] != Infinity, that means that we have already found the shortest distance for node n. Therefore we go to step 1 else go to step 3.

3. Now add all the neighbours (say B) of n to PQ with distance equal to distance[n] + nodeDistance[B].

4. After adding all the neighbours to PQ, we continue step 1. 

So easy an algorithm right? Now for better understanding see the image below. It demonstrates the algorithm in action.

Now let us say we have E number of edges and each edge is added to priority queue (min heap). The time taken by min heap to heapify when an element is added is O(logn), where n is the number of elements present in the heap. Since we are doing this for each edge we get the time complexity as O(E * log(V)), where V is the number of vertices, as there will be at most O(E) vertices in the priority queue. Which is better than the brute force approach with complexity O(V * (V + E)).

To solve the given problem, we will precompute shortest distances from source to all other nodes and then using this precomputation we can answer queries easily in O(1) time.

Let’s code this optimized approach.

For code and time complexity refer to this github repository.

So we are able to solve this problem in an optimized way. Now, let's see some applications and limitations of Dijkstra’s algorithm.

Applications:

1. It is used in Google Maps

2. It is used in finding Shortest Path.

3. It is used in geographical Maps

4. To find locations of Map which refers to vertices of a graph.

5. Distance between the location refers to edges.

6. It is used in IP routing to find the Open shortest Path First.

7. It is used in the telephone network.

Limitations:-

1.  Doing blind searches wastes a lot of time while processing.

2.  It can not handle negative edges.

3.  This leads to acyclic graphs and most often can not obtain the right shortest path.

THE TRUE POLITICIAN

In this post we will learn a very basic concept. Before we dive into the concept, let's have a look at a very  interesting problem. The problem says that :

You are given a group of politicians. Among these politicians your task is to identify the true politician.

A true politician has following qualities:

1. Does not trust anybody.
2. Gains trust of all other politician.

You are given a trust T[ ] array where T[i][j] => i trusts j.

Return the true politician if found else return -1

Note : There can be only one true politician.

Example 1 : N = 3    trust[[1,3 ], [2, 3]]

Output : 3

Example 2 : N = 3    trust[[1,3 ], [2, 3], [3, 1]]

Output : -1

Here N is the total number of politicians in the group.

Now reading these kind of problems can make you recall many concepts. But trust me, most of the graph based questions can be solved easily when you draw it on a piece of paper. Consider this example:

N = 4    trust = [

                            [1,4],

                            [2,3],

                            [2,4],

                            [3,4],

                        ]

Let's draw the relations:

                

In the above diagram, we can clearly see that 4  is the true politician. 

How did you find it? 

Exactly, you are thinking in right direction. Here in-out degree of the nodes will come to our rescue. We can clearly see the in-degrees and out-degrees of the nodes. Let X,  be the true politician. Now X do not trust anybody that means that the out-degree of X will be 0. Similarly, it is given that X gains trust of all other politicians, that means the in-degree of X will be N-1.

Now let's write an algorithm.

Algorithm 1 : 

1. Create two arrays of size N + 1 (For 1-based indexing) namely trustCount and outTrustCount.
2. Now we iterate through trust array and maintain in-degree of ith node in trustCount and out-degree in outTrustCount.
3. Finally we will iterate from i = 1 to N +1 and find a node i such that trustCount[i] = N - 1 and outTrustCount[i] = 0. If found we will return i else we will return -1

Damn easy, right? Now let's look at the implementation of above algorithm.

class Solution {
    public int findTruePolitician(int N, int[][] trust) {
        int [] trustCount = new int[N + 1];
        int [] outTrustCount = new int[N + 1];
        for(int[] row : trust){
            outTrustCount[row[0]]++;
            trustCount[row[1]]++;
        }
        for(int i = 1; i <= N; i++)
            if(trustCount[i] == N - 1 && outTrustCount[i] == 0) return i;
        return -1;
    }
}

Time Complexity : O(E + N) where E is number of edges

Space Complexity : O(N)

Can we do better?

Yes, instead of creating 2 arrays we can use just one array. Now let's see another algorithm which have same time and space complexities as Algorithm 1, but a better code in terms of implementation.

Algorithm 2 : 

1. Create an array trustCount  of size N + 1 (again for 1-based indexing).
2. Now we iterate through trust array and maintain in-degree of ith node in trustCount by incrementing trustCount[i] by 1 and out-degree of jth node by decreasing trustCount[j] by 1
3. At last we will iterate trustCount and find for a node with value trustCount[node] = N - 1. If found we return the node else we return -1.

The implementation of above algorithm is as follows:

class Solution {
    public int findTruePolitician(int N, int[][] trust) {       
        int [] trustCount = new int[N + 1];
        for(int[] row : trust){
            trustCount[row[0]]--;
            trustCount[row[1]]++;
        }
        
        for(int i = 1; i <= N; i++)
            if(trustCount[i] == N - 1) return i;
        
        return -1;
    }
}

The above code is short and clean.

Happy Coding 😀