Step 15 : Graph and its Types

1.1 Graph and its Types

What is a graph data structure?

There are two types of data structures

• Linear

• Non - linear

We are aware of linear data structures such as arrays, stacks, queues, and linked lists.
They are called linear because data elements are arranged in a linear or sequential
manner.

The only non-linear data structure that we’ve seen so far is Tree. In fact, a tree is a
special type of graph with some restrictions. Graphs are data structures that have a
wide-ranging application in real life. These include analysis of electrical circuits, finding
the shortest routes between two places, building navigation systems like Google Maps,
even social media using graphs to store data about each user, etc. To understand and
use the graph data structure, let’s get familiar with the definitions and terms associated
with graphs.

Definitions and Terminology

A graph is a non-linear data structure consisting of nodes that have data and are
connected to other nodes through edges.

Nodes are circles represented by numbers. Nodes are also referred to as vertices. They
store the data. The numbering of the nodes can be done in any order, no specific order
needs to be followed.

In the following example, the number of nodes or vertices = 5

Two nodes are connected by a horizontal line called Edge. Edge can be directed or
undirected. Basically, pairs of vertices are called edges.

In the above example, the edge can go from 1 to 4 or from 4 to 1, i.e. a bidirectional edge
can be in both directions, hence called an undirected edge. Thus, the pairs (1,4) and
(4,1) represent the same edge.

Types of Graphs

• An undirected graph is a graph where edges are bidirectional, with no direction

associated with them, i.e, there will be an undirected edge. In an undirected
graph, the pair of vertices representing any edge is unordered. Thus, the pairs (u,
v) and (v, u) represent the same edge.

• A directed graph is a graph where all the edges are directed from one vertex to
another, i.e, there will be a directed edge. It contains an ordered pair of vertices.
It implies each edge is represented by a directed pair <u, v>. Therefore, <u, v>
and <v, u> represent two different edges.
There can be multi-directed edges, hence bidirectional edges, as shown in the example
below.

Structure of Graph

Does every graph have a cycle?

The answer is No! Let us consider the following examples to understand this.

Fig. 1 does not form a cycle but still, it is a graph.

Fig. 2 is an example of a binary tree. It can also be called a graph because it follows all
the rules. We’ve nodes and edges, and this is the minimal condition to be called a
graph.

So a graph does not necessarily mean to be an enclosed structure, it can be an open

structure as well. A graph is said to have a cycle if it starts from a node and ends at the
same node. There can be multiple cycles in a graph.

If there is at least one cycle present in the graph then it is called an Undirected Cyclic
Graph.

In the following examples of directed graphs, the first directed graph is not cyclic as we
can’t start from a node and end at the same node. Hence it is called Directed Acyclic
Graph, commonly called DAG.

If we just add an edge to the directed graph, then at least one cycle is present in the
graph, hence it becomes Directed Cyclic Graph.
Path in a Graph

The path contains a lot of nodes and each of them is reachable.

Consider the given graph,

1 2 3 5 is a path.

1 2 3 2 1 is not a path, because a node can’t appear twice in a path.

1 3 5 is not a path, as adjacent nodes must have an edge and there is no edge between 1
and 3.

Degree of Graph

It is the number of edges that go inside or outside that node.

For undirected graphs, the degree is the number of edges attached to a node.

Example,

D(3) = 3

D(4) = 2
Property: It states that the total degree of a graph is equal to twice the number of edges.
This is because every edge is associated/ connected to two nodes.

Total Degree of a graph = 2 x E

Example, (2+2+3+2+3) = 2 x 6 => 12 = 12

For directed graphs, we’ve Indegree and Outdegree. The indegree of a node is the
number of incoming edges. The outdegree of a node is the number of outgoing edges.

Edge Weight

A graph may have weights assigned on its edges. It is often referred to as the cost of the
edge.
If weights are not assigned then we assume the unit weight, i.e, 1. In applications,
weight may be a measure of the cost of a route. For example, if vertices A and B
represent towns in a road network, then weight on edge AB may represent the cost of
moving from A to B, or vice versa.

1.2 Graph Representation in Java

In Java, there are two primary ways to represent a graph:

1. Adjacency Matrix

2. Adjacency List

1. Adjacency Matrix

Description:

• A 2D array of size V x V (V = number of vertices)

• matrix[i][j] = 1 means there is an edge from vertex i to vertex j

• For undirected graphs, matrix is symmetric

Example:

For a graph:

lua

CopyEdit

0 -- 1

| |

3 -- 2
Matrix:

css

CopyEdit

0123

0 [0 1 0 1]

1 [1 0 1 0]

2 [0 1 0 1]

3 [1 0 1 0]

Java Code:

java

CopyEdit

int V = 4;

int[][] adjMatrix = new int[V][V];

// Adding edge between 0 and 1

adjMatrix[0][1] = 1;

adjMatrix[1][0] = 1;

// Adding edge between 1 and 2

adjMatrix[1][2] = 1;

adjMatrix[2][1] = 1;

// Adding edge between 2 and 3

adjMatrix[2][3] = 1;

adjMatrix[3][2] = 1;

// Adding edge between 3 and 0

adjMatrix[3][0] = 1;
adjMatrix[0][3] = 1;

Pros:

• Fast access: check if edge exists in O(1)

• Easy to implement

Cons:

• Takes O(V²) space, even for sparse graphs

2. Adjacency List

Description:

• Use an array of lists

• Each list at index i stores all adjacent vertices of vertex i

• Space efficient for sparse graphs

Example:

Same graph:

0 -- 1

| |

3 -- 2

List:

0 → [1, 3]

1 → [0, 2]

2 → [1, 3]

3 → [0, 2]

Java Code:

import java.util.*;

class Graph {

int V;
 ArrayList<ArrayList<Integer>> adjList;

Graph(int V) {

this.V = V;

adjList = new ArrayList<>();

for (int i = 0; i < V; i++) {

adjList.add(new ArrayList<>());

void addEdge(int u, int v) {

adjList.get(u).add(v);

adjList.get(v).add(u); // remove this line for directed graph

void printGraph() {

for (int i = 0; i < V; i++) {

System.out.print(i + " → ");

for (int node : adjList.get(i)) {

System.out.print(node + " ");

System.out.println();

Usage:

java

CopyEdit
public class Main {

public static void main(String[] args) {

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(1, 2);

g.addEdge(2, 3);

g.addEdge(3, 0);

g.printGraph();

Pros:

• Space efficient: O(V + E)

• Better for large, sparse graphs

Cons:

• Checking if edge exists: O(degree of node)

When to Use Which?

Graph Type Recommended Representation

Dense Graph Adjacency Matrix

Sparse Graph Adjacency List

Weighted Graph Adjacency List with Pairs

Dynamic Graph Adjacency List

Advanced: Weighted Graph (Using List of Pairs)

java

class Pair {
 int node, weight;

Pair(int n, int w) {

node = n;

weight = w;

ArrayList<ArrayList<Pair>> weightedGraph = new ArrayList<>();

1.4 Connected Components in an Undirected Graph

Difficulty: MediumAccuracy: 48.5%Submissions: 14K+Points: 4

Given an undirected graph with V vertices numbered from 0 to V-1 and E edges,
represented as a 2D array edges[][], where each entry edges[i] = [u, v] denotes an edge
between vertices u and v.

Your task is to return a list of all connected components. Each connected component
should be represented as a list of its vertices, with all components returned in a
collection where each component is listed separately.

Note: You can return the components in any order, driver code will print the
components in sorted order.

Examples :

Input: V = 5, edges[][] = [[0, 1], [2, 1], [3, 4]]

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

Explanation:

Input: V = 7, edges[][] = [[0, 1], [6, 0], [2, 4], [2, 3], [3, 4]]

Output: [[0, 1, 6], [2, 3, 4], [5]]

Explanation:
Constraints:
1 ≤ V ≤ 105
1 ≤ edges.size() ≤ 105
0 <= edges[i][0], edges[i][1] < V

1.5 BFS of graph

Difficulty: EasyAccuracy: 44.09%Submissions: 492K+Points: 2Average Time: 10m

Given a connected undirected graph containing V vertices, represented by a 2-

d adjacency list adj[][], where each adj[i] represents the list of vertices connected to
vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting
vertices from left to right according to the given adjacency list, and return a list
containing the BFS traversal of the graph.

Note: Do traverse in the same order as they are in the given adjacency list.

Examples:

Output: [0, 2, 3, 1, 4]
Explanation: Starting from 0, the BFS traversal will follow these steps:
Visit 0 → Output: 0
Visit 2 (first neighbor of 0) → Output: 0, 2
Visit 3 (next neighbor of 0) → Output: 0, 2, 3
Visit 1 (next neighbor of 0) → Output: 0, 2, 3,
Visit 4 (neighbor of 2) → Final Output: 0, 2, 3, 1, 4

Input: adj[][] = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]
Output: [0, 1, 2, 3, 4]
Explanation: Starting from 0, the BFS traversal proceeds as follows:
Visit 0 → Output: 0
Visit 1 (the first neighbor of 0) → Output: 0, 1
Visit 2 (the next neighbor of 0) → Output: 0, 1, 2
Visit 3 (the first neighbor of 2 that hasn't been visited yet) → Output: 0, 1, 2, 3
Visit 4 (the next neighbor of 2) → Final Output: 0, 1, 2, 3, 4

Constraints:
1 ≤ V = adj.size() ≤ 104
1 ≤ adj[i][j] ≤ 104
1.6
2.1 547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is
connected directly with city b, and city b is connected directly with city c, then city a is
connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities

outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and
the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

Constraints:

• 1 <= n <= 200

• n == isConnected.length
• n == isConnected[i].length

• isConnected[i][j] is 1 or 0.

• isConnected[i][i] == 1

• isConnected[i][j] == isConnected[j][i]
2.2 Connected Components in an Undirected Graph

Given an undirected graph with V vertices numbered from 0 to V-1 and E edges,
represented as a 2D array edges[][], where each entry edges[i] = [u, v] denotes an edge
between vertices u and v.

Your task is to return a list of all connected components. Each connected component
should be represented as a list of its vertices, with all components returned in a
collection where each component is listed separately.

Note: You can return the components in any order, driver code will print the
components in sorted order.

Examples :

Input: V = 5, edges[][] = [[0, 1], [2, 1], [3, 4]]

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

Explanation:

Input: V = 7, edges[][] = [[0, 1], [6, 0], [2, 4], [2, 3], [3, 4]]

Output: [[0, 1, 6], [2, 3, 4], [5]]

Explanation:

Constraints:
1 ≤ V ≤ 105
1 ≤ edges.size() ≤ 105
0 <= edges[i][0], edges[i][1] < V
2.2.1 2685. Count the Number of Complete Components

You are given an integer n. There is an undirected graph with n vertices, numbered
from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes
that there exists an undirected edge connecting vertices ai and bi.

Return the number of complete connected components of the graph.

A connected component is a subgraph of a graph in which there exists a path between

any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of
the subgraph.

A connected component is said to be complete if there exists an edge between every

pair of its vertices.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]

Output: 3

Explanation: From the picture above, one can see that all of the components of this
graph are complete.

Example 2:
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]

Output: 1

Explanation: The component containing vertices 0, 1, and 2 is complete since there is

an edge between every pair of two vertices. On the other hand, the component
containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4
and 5. Thus, the number of complete components in this graph is 1.

Constraints:

• 1 <= n <= 50

• 0 <= edges.length <= n * (n - 1) / 2

• edges[i].length == 2

• 0 <= ai, bi <= n - 1

• ai != bi

• There are no repeated edges.

2.3 994. Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,

• 1 representing a fresh orange, or

• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange
becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh
orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten,
because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
 • n == grid[i].length

• 1 <= m, n <= 10

• grid[i][j] is 0, 1, or 2.

2.4 733. Flood Fill

You are given an image represented by an m x n grid of integers image,

where image[i][j] represents the pixel value of the image. You are also given three
integers sr, sc, and color. Your task is to perform a flood fill on the image starting from
the pixel image[sr][sc].

To perform a flood fill:

1. Begin with the starting pixel and change its color to color.

2. Perform the same process for each pixel that is directly adjacent (pixels that
share a side with the original pixel, either horizontally or vertically) and shares
the same color as the starting pixel.

3. Keep repeating this process by checking neighboring pixels of

the updated pixels and modifying their color if it matches the original color of the
starting pixel.

4. The process stops when there are no more adjacent pixels of the original color
to update.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

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

Explanation:
From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels
connected by a path of the same color as the starting pixel (i.e., the blue pixels) are
colored with the new color.

Note the bottom corner is not colored 2, because it is not horizontally or vertically
connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

Explanation:

The starting pixel is already colored with 0, which is the same as the target color.
Therefore, no changes are made to the image.

Constraints:

• m == image.length

• n == image[i].length

• 1 <= m, n <= 50

• 0 <= image[i][j], color < 216

• 0 <= sr < m

• 0 <= sc < n
2.5 Undirected Graph Cycle

Difficulty: MediumAccuracy: 30.13%Submissions: 580K+Points: 4Average Time: 20m

Given an undirected graph with V vertices and E edges, represented as a 2D

vector edges[][], where each entry edges[i] = [u, v] denotes an edge between

vertices u and v, determine whether the graph contains a cycle or not.

Examples:

Input: V = 4, E = 4, edges[][] = [[0, 1], [0, 2], [1, 2], [2, 3]]

Output: true

Explanation:

1 -> 2 -> 0 -> 1 is a cycle.

Input: V = 4, E = 3, edges[][] = [[0, 1], [1, 2], [2, 3]]

Output: false

Explanation:

No cycle in the graph.

Constraints:
1 ≤ V ≤ 105
1 ≤ E = edges.size() ≤ 105
2.7 542. 01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two cells sharing a common edge is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]

Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]

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

Constraints:

• m == mat.length

• n == mat[i].length
 • 1 <= m, n <= 104

• 1 <= m * n <= 104

• mat[i][j] is either 0 or 1.

• There is at least one 0 in mat.

2.8 130. Surrounded Regions

Medium

Topics

Companies

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that
are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.

• Region: To form a region connect every 'O' cell.

• Surround: The region is surrounded with 'X' cells if you can connect the
region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original
board. You do not need to return anything.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the
board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 200

• board[i][j] is 'X' or 'O'.

2.9 1020. Number of Enclaves

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents
a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally)
land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the
grid in any number of moves.

Example 1:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output: 3

Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed
because its on the boundary.

Example 2:
Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output: 0

Explanation: All 1s are either on the boundary or can reach the boundary.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 500

• grid[i][j] is either 0 or 1
2.10 127. Word Ladder

A transformation sequence from word beginWord to word endWord using a

dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.

• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be
in wordList.

• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList,

return the number of words in the shortest transformation
sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" ->
cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore there is no valid

transformation sequence.

Constraints:

• 1 <= beginWord.length <= 10

• endWord.length == beginWord.length

• 1 <= wordList.length <= 5000

• wordList[i].length == beginWord.length

• beginWord, endWord, and wordList[i] consist of lowercase English letters.

• beginWord != endWord

• All the words in wordList are unique.

2.11 126. Word Ladder II

A transformation sequence from word beginWord to word endWord using a

dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.

• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be
in wordList.

• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all
the shortest transformation sequences from beginWord to endWord, or an empty list
if no such sequence exists. Each sequence should be returned as a list of the
words [beginWord, s1, s2, ..., sk].

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Explanation: There are 2 shortest transformation sequences:

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore there is no valid

transformation sequence.

Constraints:

• 1 <= beginWord.length <= 5

• endWord.length == beginWord.length

• 1 <= wordList.length <= 500

• wordList[i].length == beginWord.length

• beginWord, endWord, and wordList[i] consist of lowercase English letters.

 • beginWord != endWord

• All the words in wordList are unique.

• The sum of all shortest transformation sequences does not exceed 105.

2.12 Number of Distinct Islands

Difficulty: MediumAccuracy: 62.29%Submissions: 102K+Points: 4Average Time: 20m

Given a boolean 2D matrix grid of size n * m. You have to find the number of distinct
islands where a group of connected 1s (horizontally or vertically) forms an island. Two
islands are considered to be distinct if and only if one island is not equal to another (not
rotated or reflected).

Example 1:

Input:

grid[][] = {{1, 1, 0, 0, 0},

{1, 1, 0, 0, 0},

{0, 0, 0, 1, 1},

{0, 0, 0, 1, 1}}

Output:

Explanation:

grid[][] = {{1, 1, 0, 0, 0},

{1, 1, 0, 0, 0},

{0, 0, 0, 1, 1},

{0, 0, 0, 1, 1}}

Same colored islands are equal.

We have 2 equal islands, so we

have only 1 distinct island.

Example 2:

Input:
grid[][] = {{1, 1, 0, 1, 1},

{1, 0, 0, 0, 0},

{0, 0, 0, 0, 1},

{1, 1, 0, 1, 1}}

Output:

Explanation:

grid[][] = {{1, 1, 0, 1, 1},

{1, 0, 0, 0, 0},

{0, 0, 0, 0, 1},

{1, 1, 0, 1, 1}}

Same colored islands are equal.

We have 4 islands, but 2 of them

are equal, So we have 3 distinct islands.

Your Task:

You don't need to read or print anything. Your task is to complete the
function countDistinctIslands() which takes the grid as an input parameter and returns
the total number of distinct islands.

Expected Time Complexity: O(n * m)

Expected Space Complexity: O(n * m)

Constraints:
1 ≤ n, m ≤ 500
grid[i][j] == 0 or grid[i][j] == 1
2.13 785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered

between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes
that node u is adjacent to. More formally, for each v in graph[u], there is an undirected
edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).

• There are no parallel edges (graph[u] does not contain duplicate values).

• If v is in graph[u], then u is in graph[v] (the graph is undirected).

• The graph may not be connected, meaning there may be two nodes u and v such
that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent

sets A and B such that every edge in the graph connects a node in set A and a node in
set B.

Return true if and only if it is bipartite.

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: There is no way to partition the nodes into two independent sets such that
every edge connects a node in one and a node in the other.

Example 2:
Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

• graph.length == n

• 1 <= n <= 100

• 0 <= graph[u].length < n

• 0 <= graph[u][i] <= n - 1

• graph[u] does not contain u.

• All the values of graph[u] are unique.

• If graph[u] contains v, then graph[v] contains u.

2.14 210. Course Schedule II

There are a total of numCourses courses you have to take, labeled

from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] =
[ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take
course 1.

Return the ordering of courses you should take to finish all courses. If there are many
valid answers, return any of them. If it is impossible to finish all courses, return an
empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are a 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: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [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].

Example 3:

Input: numCourses = 1, prerequisites = []

Output: [0]

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= numCourses * (numCourses - 1)

• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses

• ai != bi

• All the pairs [ai, bi] are distinct.

3.1 Topological sort

Difficulty: MediumAccuracy: 56.52%Submissions: 292K+Points: 4Average Time: 15m

Given a Directed Acyclic Graph (DAG) of V (0 to V-1) vertices and E edges represented
as a 2D list of edges[][], where each entry edges[i] = [u, v] denotes a directed edge u -
> v. Return the topological sort for the given graph.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such
that for every directed edge u -> v, vertex u comes before v in the ordering.

Note: As there are multiple Topological orders possible, you may return any of them. If
your returned Topological sort is correct then the output will be true else false.

Examples:

Input: V = 4, E = 3, edges[][] = [[3, 0], [1, 0], [2, 0]]

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological
orders for the given graph are:

[3, 2, 1, 0]
[1, 2, 3, 0]
[2, 3, 1, 0]
Input: V = 6, E = 6, edges[][] = [[1, 3], [2, 3], [4, 1], [4, 0], [5, 0], [5,2]]

Output: true

Explanation: The output true denotes that the order is valid. Few valid Topological
orders for the graph are:
[4, 5, 0, 1, 2, 3]
[5, 2, 4, 0, 1, 3]

Constraints:
2 ≤ V ≤ 103
1 ≤ E = edges.size() ≤ (V * (V - 1)) / 2
3.3 Directed Graph Cycle

Difficulty: MediumAccuracy: 27.88%Submissions: 488K+Points: 4

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check
whether it contains any cycle or not.
The graph is represented as a 2D vector edges[][], where each entry edges[i] = [u,
v] denotes an edge from verticex u to v.

Examples:

Input: V = 4, edges[][] = [[0, 1], [0, 2], [1, 2], [2, 0], [2, 3]]

Output: true

Explanation: The diagram clearly shows a cycle 0 → 2 → 0

Input: V = 4, edges[][] = [[0, 1], [0, 2], [1, 2], [2, 3]

Output: false

Explanation: no cycle in the graph

Constraints:
1 ≤ V, E ≤ 105
u≠v
3.4 207. Course Schedule

There are a total of numCourses courses you have to take, labeled

from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] =
[ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take
course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are a total of 2 courses to take.

To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: There are a total of 2 courses to take.

To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• All the pairs prerequisites[i] are unique.

3.5 210. Course Schedule II

There are a total of numCourses courses you have to take, labeled

from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] =
[ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take
course 1.

Return the ordering of courses you should take to finish all courses. If there are many
valid answers, return any of them. If it is impossible to finish all courses, return an
empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are a 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: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [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].

Example 3:

Input: numCourses = 1, prerequisites = []

Output: [0]

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= numCourses * (numCourses - 1)

• prerequisites[i].length == 2
 • 0 <= ai, bi < numCourses

• ai != bi

• All the pairs [ai, bi] are distinct.

3.6 802. Find Eventual Safe States

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is
represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of
nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every
possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted
in ascending order.

Example 1:

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

Explanation: The given graph is shown above.

Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.

Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2:

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Output: [4]

Explanation:

Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.
Constraints:

• n == graph.length

• 1 <= n <= 104

• 0 <= graph[i].length <= n

• 0 <= graph[i][j] <= n - 1

• graph[i] is sorted in a strictly increasing order.

• The graph may contain self-loops.

• The number of edges in the graph will be in the range [1, 4 * 104]
3.7 Alien Dictionary

Difficulty: HardAccuracy: 47.81%Submissions: 169K+Points: 8

A new alien language uses the English alphabet, but the order of letters is unknown. You
are given a list of words[] from the alien language’s dictionary, where the words are
claimed to be sorted lexicographically according to the language’s rules.

Your task is to determine the correct order of letters in this alien language based on
the given words. If the order is valid, return a string containing the unique letters in
lexicographically increasing order as per the new language's rules. If there are multiple
valid orders, return any one of them.

However, if the given arrangement of words is inconsistent with any possible letter
ordering, return an empty string ("").

A string a is lexicographically smaller than a string b if, at the first position where they
differ, the character in a appears earlier in the alien language than the corresponding
character in b. If all characters in the shorter word match the beginning of the longer
word, the shorter word is considered smaller.

Note: Your implementation will be tested using a driver code. It will print true if your
returned order correctly follows the alien language’s lexicographic rules; otherwise, it
will print false.

Examples:

Input: words[] = ["baa", "abcd", "abca", "cab", "cad"]

Output: true
Explanation: A possible corrct order of letters in the alien dictionary is "bdac".
The pair "baa" and "abcd" suggests 'b' appears before 'a' in the alien dictionary.

The pair "abcd" and "abca" suggests 'd' appears before 'a' in the alien dictionary.

The pair "abca" and "cab" suggests 'a' appears before 'c' in the alien dictionary.

The pair "cab" and "cad" suggests 'b' appears before 'd' in the alien dictionary.

So, 'b' → 'd' → 'a' → 'c' is a valid ordering.

Input: words[] = ["caa", "aaa", "aab"]

Output: true
Explanation: A possible corrct order of letters in the alien dictionary is "cab".
The pair "caa" and "aaa" suggests 'c' appears before 'a'.
The pair "aaa" and "aab" suggests 'a' appear before 'b' in the alien dictionary.
So, 'c' → 'a' → 'b' is a valid ordering.
Input: words[] = ["ab", "cd", "ef", "ad"]
Output: ""
Explanation: No valid ordering of letters is possible.
The pair "ab" and "ef" suggests "a" appears before "e".
The pair "ef" and "ad" suggests "e" appears before "a", which contradicts the ordering
rules.

Constraints:
1 ≤ words.length ≤ 500
1 ≤ words[i].length ≤ 100
words[i] consists only of lowercase English letters.
4.1 Shortest Path in Undirected Graph

Difficulty: MediumAccuracy: 49.98%Submissions: 145K+Points: 4Average Time: 20m

You are given an adjacency list, adj of Undirected Graph having unit weight of the
edges, find the shortest path from src to all the vertex and if it is unreachable to reach
any vertex, then return -1 for that vertex.

Examples :

Input: adj[][] = [[1, 3], [0, 2], [1, 6], [0, 4], [3, 5], [4, 6], [2, 5, 7, 8], [6, 8], [7, 6]], src=0

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

Input: adj[][]= [[3], [3], [], [0, 1]], src=3

Output: [1, 1, -1, 0]

Input: adj[][]= [[], [], [], [4], [3], [], []], src=1

Output: [-1, 0, -1, -1, -1, -1, -1]

Constraint:
1<=adj.size()<=104
0<=edges<=adj.size()-1
4.2 Shortest path in Directed Acyclic Graph

Difficulty: MediumAccuracy: 48.48%Submissions: 174K+Points: 4Average Time: 20m

Given a Directed Acyclic Graph of V vertices from 0 to n-1 and a 2D Integer array(or
vector) edges[ ][ ] of length E, where there is a directed edge from edge[i][0] to edge[i][1]
with a distance of edge[i][2] for all i.

Find the shortest path from src(0) vertex to all the vertices and if it is impossible to
reach any vertex, then return -1 for that vertex.

Examples :

Input: V = 4, E = 2, edges = [[0,1,2], [0,2,1]]

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

Explanation: Shortest path from 0 to 1 is 0->1 with edge weight 2. Shortest path from 0
to 2 is 0->2 with edge weight 1. There is no way we can reach 3, so it's -1 for 3.

Input: V = 6, E = 7, edges = [[0,1,2], [0,4,1], [4,5,4], [4,2,2], [1,2,3], [2,3,6], [5,3,1]]

Output: [0, 2, 3, 6, 1, 5]
Explanation: Shortest path from 0 to 1 is 0->1 with edge weight 2. Shortest path from 0
to 2 is 0->4->2 with edge weight 1+2=3. Shortest path from 0 to 3 is 0->4->5->3 with
edge weight 1+4+1=6. Shortest path from 0 to 4 is 0->4 with edge weight 1.Shortest path
from 0 to 5 is 0->4->5 with edge weight 1+4=5.

Constraint:
1 <= V <= 100
1 <= E <= min((N*(N-1))/2,4000)
0 <= edgesi,0, edgesi,1 < n
0 <= edgei,2 <=105
4.3 Dijkstra Algorithm

Difficulty: MediumAccuracy: 50.83%Submissions: 231K+Points: 4Average Time: 25m

Given an undirected, weighted graph with V vertices numbered from 0 to V-1

and E edges, represented by 2d array edges[][], where edges[i]=[u, v, w] represents
the edge between the nodes u and v having w edge weight.
You have to find the shortest distance of all the vertices from the source vertex src, and
return an array of integers where the ith element denotes the shortest distance
between ith node and source vertex src.

Note: The Graph is connected and doesn't contain any negative weight edge.

Examples:

Input: V = 3, edges[][] = [[0, 1, 1], [1, 2, 3], [0, 2, 6]], src = 2

Output: [4, 3, 0]

Explanation:

Shortest Paths:

For 2 to 0 minimum distance will be 4. By following path 2 -> 1 -> 0

For 2 to 1 minimum distance will be 3. By following path 2 -> 1

For 2 to 2 minimum distance will be 0. By following path 2 -> 2

Input: V = 5, edges[][] = [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 2], [3, 4, 10]], src = 0

Output: [0, 4, 8, 10, 10]

Explanation:

Shortest Paths:
For 0 to 1 minimum distance will be 4. By following path 0 -> 1

For 0 to 2 minimum distance will be 8. By following path 0 -> 2

For 0 to 3 minimum distance will be 10. By following path 0 -> 2 -> 3

For 0 to 4 minimum distance will be 10. By following path 0 -> 1 -> 4

Constraints:
1 ≤ V ≤ 105

1 ≤ E = edges.size() ≤ 105
0 ≤ edges[i][j] ≤ 104

0 ≤ src < V
4.4 Why priority Queue is used in Djisktra's Algorithm

What is Dijkstra's Algorithm?

Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a
graph. It uses a priority queue for finding the shortest path. For more detail, about
Dijkstra's Algorithm, you can refer to this article.

Why Dijkstra's Algorithm uses a Priority Queue?

We use min heap in Dijkstra's Algorithm because a node can have multiple weighted
edges but for the shortest path, we have to consider the smallest weighted edge
associated with a node. For this, we use a priority queue (min-heap) which gives us the
minimum element on the top of the priority queue.

4.5 1091. Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the
matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-
right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.

• All the adjacent cells of the path are 8-directionally connected (i.e., they are
different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]

Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

Constraints:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 100

• grid[i][j] is 0 or 1
4.6 1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of
size rows x columns, where heights[row][col] represents the height of cell (row, col). You
are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right
cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and
you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two

consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right
cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in

consecutive cells.

This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]

Output: 1

Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in

consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]

Output: 0

Explanation: This route does not require any effort.

Constraints:

• rows == heights.length

• columns == heights[i].length
 • 1 <= rows, columns <= 100

• 1 <= heights[i][j] <= 10

4.7 787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an
array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from
city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest
price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k

=1

Output: 700

Explanation:

The graph is shown above.

The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 +
600 = 700.

Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2
stops.

Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph is shown above.

The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 +
100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output: 500

Explanation:

The graph is shown above.

The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

• 1 <= n <= 100

• 0 <= flights.length <= (n * (n - 1) / 2)

• flights[i].length == 3

• 0 <= fromi, toi < n

• fromi != toi

• 1 <= pricei <= 104

• There will not be any multiple flights between two cities.

• 0 <= src, dst, k < n

• src != dst
4.8 743. Network Delay TimeYou are given a network of n nodes, labeled from 1 to n.
You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi),
where ui is the source node, vi is the target node, and wi is the time it takes for a signal to
travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all
the n nodes to receive the signal. If it is impossible for all the n nodes to receive the
signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1

Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2

Output: -1

Constraints:

• 1 <= k <= n <= 100

• 1 <= times.length <= 6000

• times[i].length == 3

• 1 <= ui, vi <= n

• ui != vi

• 0 <= wi <= 100

• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
4.9 1976. Number of Ways to Arrive at Destination

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-
directional roads between some intersections. The inputs are generated such that you
can reach any intersection from any other intersection and that there is at most one
road between any two intersections.

You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi,
timei] means that there is a road between intersections ui and vi that takes timei minutes
to travel. You want to know in how many ways you can travel from intersection 0 to
intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of
time. Since the answer may be large, return it modulo 109 + 7.

Example 1:

Input: n = 7, roads =
[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]

Output: 4

Explanation: The shortest amount of time it takes to go from intersection 0 to

intersection 6 is 7 minutes.

The four ways to get there in 7 minutes are:

-0➝6

-0➝4➝6

-0➝1➝2➝5➝6
-0➝1➝3➝5➝6

Example 2:

Input: n = 2, roads = [[1,0,10]]

Output: 1

Explanation: There is only one way to go from intersection 0 to intersection 1, and it

takes 10 minutes.

Constraints:

• 1 <= n <= 200

• n - 1 <= roads.length <= n * (n - 1) / 2

• roads[i].length == 3

• 0 <= ui, vi <= n - 1

• 1 <= timei <= 109

• ui != vi

• There is at most one road connecting any two intersections.

• You can reach any intersection from any other intersection.

4.10 Minimum Multiplications to reach End

Difficulty: MediumAccuracy: 48.94%Submissions: 157K+Points: 4Average Time: 20m

Given start, end and an array arr of n numbers. At each step, start is multiplied with any
number in the array and then mod operation with 100000 is done to get the new start.

Your task is to find the minimum steps in which end can be achieved starting from start.
If it is not possible to reach end, then return -1.

Example 1:

Input:

arr[] = {2, 5, 7}

start = 3, end = 30

Output:

Explanation:

Step 1: 3*2 = 6 % 100000 = 6

Step 2: 6*5 = 30 % 100000 = 30

Example 2:

Input:

arr[] = {3, 4, 65}

start = 7, end = 66175

Output:

Explanation:

Step 1: 7*3 = 21 % 100000 = 21

Step 2: 21*3 = 63 % 100000 = 63

Step 3: 63*65 = 4095 % 100000 = 4095

Step 4: 4095*65 = 266175 % 100000 = 66175

Your Task:
You don't need to print or input anything. Complete the
function minimumMultiplications() which takes an integer array arr, an
integer start and an integer end as the input parameters and returns an integer,
denoting the minumum steps to reach in which end can be achieved starting from start.

Expected Time Complexity: O(105)

Expected Space Complexity: O(105)

Constraints:

• 1 <= n <= 104

• 1 <= arr[i] <= 104

• 1 <= start, end < 105

4.11 Bellman-Ford

Difficulty: MediumAccuracy: 48.11%Submissions: 204K+Points: 4Average Time: 25m

Given an weighted graph with V vertices numbered from 0 to V-1 and E edges,
represented by a 2d array edges[][], where edges[i] = [u, v, w] represents a direct edge
from node u to v having w edge weight. You are also given a source vertex src.

Your task is to compute the shortest distances from the source to all other vertices. If
a vertex is unreachable from the source, its distance should be marked as 108.
Additionally, if the graph contains a negative weight cycle, return [-1] to indicate that
shortest paths cannot be reliably computed.

Examples:

Input: V = 5, edges[][] = [[1, 3, 2], [4, 3, -1], [2, 4, 1], [1, 2, 1], [0, 1, 5]], src = 0

Output: [0, 5, 6, 6, 7]
Explanation: Shortest Paths:
For 0 to 1 minimum distance will be 5. By following path 0 → 1

For 0 to 2 minimum distance will be 6. By following path 0 → 1 → 2

For 0 to 3 minimum distance will be 6. By following path 0 → 1 → 2 → 4 → 3

For 0 to 4 minimum distance will be 7. By following path 0 → 1 → 2 → 4

Input: V = 4, edges[][] = [[0, 1, 4], [1, 2, -6], [2, 3, 5], [3, 1, -2]], src = 0

Output: [-1]

Explanation: The graph contains a negative weight cycle formed by the path 1 → 2 → 3 →
1, where the total weight of the cycle is negative.

Constraints:
1 ≤ V ≤ 100
1 ≤ E = edges.size() ≤ V*(V-1)
-1000 ≤ w ≤ 1000
0 ≤ src < V
4.12: Floyd Warshall

Difficulty: MediumAccuracy: 32.89%Submissions: 199K+Points: 4Average Time: 15m

You are given an weighted directed graph, represented by an adjacency

matrix, dist[][] of size n x n, where dist[i][j] represents the weight of the edge from node
i to node j. If there is no direct edge, dist[i][j] is set to a large value (i.e., 108) to
represent infinity.
The graph may contain negative edge weights, but it does not contain any negative
weight cycles.

Your task is to find the shortest distance between every pair of nodes i and j in the
graph.

Note: Modify the distances for every pair in place.

Examples :

Input: dist[][] = [[0, 4, 108, 5, 108], [108, 0, 1, 108, 6], [2, 108, 0, 3, 108], [108, 108, 1, 0, 2], [1,
108, 108, 4, 0]]

Output: [[0, 4, 5, 5, 7], [3, 0, 1, 4, 6], [2, 6, 0, 3, 5], [3, 7, 1, 0, 2], [1, 5, 5, 4, 0]]

Explanation: Each cell dist[i][j] in the output shows the shortest distance from node i to
node j, computed by considering all possible intermediate nodes.
Input: dist[][] = [[0, -1, 2], [1, 0, 108], [3, 1, 0]]

Output: [[0, -1, 2], [1, 0, 3], [2, 1, 0]]

Explanation: Each cell dist[i][j] in the output shows the shortest distance from node i to
node j, computed by considering all possible intermediate nodes.
From 2 to 0 shortest distance should be 2 by following path 2 -> 1 -> 0
From 1 to 2 shortest distance should be 3 by following path 1 -> 0 -> 2

Constraints:
1 ≤ dist.size() ≤ 100
-1000 ≤ dist[i][j] ≤ 1000
dist[i][j] can be 108 to represent infinity.
4.13 1334. Find the City With the Smallest Number of Neighbors at a Threshold
Distance

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi,
toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi,
and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path
and whose distance is at most distanceThreshold, If there are multiple such cities,
return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the
edges' weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

Output: 3

Explanation: The figure above describes the graph.

The neighboring cities at a distanceThreshold = 4 for each city are:

City 0 -> [City 1, City 2]

City 1 -> [City 0, City 2, City 3]

City 2 -> [City 0, City 1, City 3]

City 3 -> [City 1, City 2]

Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return

city 3 since it has the greatest number.

Example 2:
Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2

Output: 0

Explanation: The figure above describes the graph.

The neighboring cities at a distanceThreshold = 2 for each city are:

City 0 -> [City 1]

City 1 -> [City 0, City 4]

City 2 -> [City 3, City 4]

City 3 -> [City 2, City 4]

City 4 -> [City 1, City 2, City 3]

The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

• 2 <= n <= 100

• 1 <= edges.length <= n * (n - 1) / 2

• edges[i].length == 3

• 0 <= fromi < toi < n

• 1 <= weighti, distanceThreshold <= 10^4

• All pairs (fromi, toi) are distinct.

5.1 Minimum Spanning Tree

Difficulty: MediumAccuracy: 47.82%Submissions: 165K+Points: 4Average Time: 25m

Given a weighted, undirected, and connected graph with V vertices and E edges, your
task is to find the sum of the weights of the edges in the Minimum Spanning Tree (MST)
of the graph. The graph is represented by an adjacency list, where each element adj[i] is
a vector containing vector of integers. Each vector represents an edge, with the first
integer denoting the endpoint of the edge and the second integer denoting the weight of
the edge.

Input:

33

015

123

021

Output: 4

Explanation:

The Spanning Tree resulting in a weight

of 4 is shown above.
Input:
21
015

Output: 5

Explanation: Only one Spanning Tree is possible which has a weight of 5.

Constraints:
2 ≤ V ≤ 1000
V-1 ≤ E ≤ (V*(V-1))/2
1 ≤ w ≤ 1000
The graph is connected and doesn't contain self-loops & multiple edges.
5.3 Disjoint set (Union-Find)

Difficulty: EasyAccuracy: 40.03%Submissions: 64K+Points: 2

Given an array par[] that stores all number from 1 to n (both inclusive and sorted)
and k queries.

The task is to do the following operations on array elements :

1. UNION x z : Perform union of x and z i.e. parent of z will become the parent of x.
2. FIND x: Find the ultimate parent of x and print it.

Note: Initially all are the parent of themselves.The ultimate parent is the topmost node
such that par[node]=node.

Input: n = 5, k = 4, queries[] = {{find 4}, {find 1}, {unionSet 3 1}, {find 3}}

Output: 4 1 1

Explanation:

1. The parent of 4 is 4. Hence the output is 4.

2. The parent of 1 is 1. Hence the output is 1.

3. After performing unionSet 3 1, parent of 3 becomes 1, since, parent of 1 is currently 1

itself.

4. The parent of 3 is now 1. Hence, the output is 1.

Constraints:
1 <= n,k <= 100
5.4 Disjoint set (Union-Find)

Difficulty: EasyAccuracy: 40.03%Submissions: 64K+Points: 2

Given an array par[] that stores all number from 1 to n (both inclusive and sorted)
and k queries.

The task is to do the following operations on array elements :

1. UNION x z : Perform union of x and z i.e. parent of z will become the parent of x.
2. FIND x: Find the ultimate parent of x and print it.

Note: Initially all are the parent of themselves.The ultimate parent is the topmost node
such that par[node]=node.

Input: n = 5, k = 4, queries[] = {{find 4}, {find 1}, {unionSet 3 1}, {find 3}}

Output: 4 1 1

Explanation:

1. The parent of 4 is 4. Hence the output is 4.

2. The parent of 1 is 1. Hence the output is 1.

3. After performing unionSet 3 1, parent of 3 becomes 1, since, parent of 1 is currently 1

itself.

4. The parent of 3 is now 1. Hence, the output is 1.

Constraints:
1 <= n,k <= 100
5.5 1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-
plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between
them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if
there is exactly one simple path between any two points.

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output: 20

Explanation:
We can connect the points as shown above to get the minimum cost of 20.

Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]

Output: 18

Constraints:

• 1 <= points.length <= 1000

• -106 <= xi, yi <= 106

• All pairs (xi, yi) are distinct.

5.6 1319. Number of Operations to Make Network Connected

There are n computers numbered from 0 to n - 1 connected by ethernet

cables connections forming a network where connections[i] = [ai, bi] represents a
connection between computers ai and bi. Any computer can reach any other computer
directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables
between two directly connected computers, and place them between any pair of
disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the
computers connected. If it is not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]

Output: 1

Explanation: Remove cable between computer 1 and 2 and place between computers
1 and 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

Output: 2
Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]

Output: -1

Explanation: There are not enough cables.

Constraints:

• 1 <= n <= 105

• 1 <= connections.length <= min(n * (n - 1) / 2, 105)

• connections[i].length == 2

• 0 <= ai, bi < n

• ai != bi

• There are no repeated connections.

• No two computers are connected by more than one cable.

5.7 947. Most Stones Removed with Same Row or Column

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate

point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as
another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of
the ith stone, return the largest possible number of stones that can be removed.

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Output: 5

Explanation: One way to remove 5 stones is as follows:

1. Remove stone [2,2] because it shares the same row as [2,1].

2. Remove stone [2,1] because it shares the same column as [0,1].

3. Remove stone [1,2] because it shares the same row as [1,0].

4. Remove stone [1,0] because it shares the same column as [0,0].

5. Remove stone [0,1] because it shares the same row as [0,0].

Stone [0,0] cannot be removed since it does not share a row/column with another stone
still on the plane.

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

Output: 3

Explanation: One way to make 3 moves is as follows:

1. Remove stone [2,2] because it shares the same row as [2,0].

2. Remove stone [2,0] because it shares the same column as [0,0].

3. Remove stone [0,2] because it shares the same row as [0,0].

Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with
another stone still on the plane.

Example 3:
Input: stones = [[0,0]]

Output: 0

Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

Constraints:

• 1 <= stones.length <= 1000

• 0 <= xi, yi <= 104

• No two stones are at the same coordinate point.

5.8 721. Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, where the
first element accounts[i][0] is a name, and the rest of the elements
are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the
same person if there is some common email to both accounts. Note that even if two
accounts have the same name, they may belong to different people as people could
have the same name. A person can have any number of accounts initially, but all of their
accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first
element of each account is the name, and the rest of the elements are emails in sorted
order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts =
[["John","[email protected]","[email protected]"],["John","[email protected]
m","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]

Output:
[["John","[email protected]","[email protected]","[email protected]"],["Mary"
,"[email protected]"],["John","[email protected]"]]

Explanation:

The first and second John's are the same person as they have the common email
"[email protected]".

The third John and Mary are different people as none of their email addresses are used
by other accounts.

We could return these lists in any order, for example the answer [['Mary',
'[email protected]'], ['John', '[email protected]'],

['John', '[email protected]', '[email protected]', '[email protected]']] would

still be accepted.

Example 2:

Input: accounts =
[["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","Kevin
[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["H
anzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","Fern1@
m.co","[email protected]"]]

Output:
[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","Gab
[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],
["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","Fern1@
m.co","[email protected]"]]

Constraints:

• 1 <= accounts.length <= 1000

• 2 <= accounts[i].length <= 10

• 1 <= accounts[i][j].length <= 30

• accounts[i][0] consists of English letters.

• accounts[i][j] (for j > 0) is a valid email.

5.9 Number Of Islands

Difficulty: MediumAccuracy: 60.65%Submissions: 54K+Points: 4Average Time: 30m

You are given a n,m which means the row and column of the 2D matrix and an array
of size k denoting the number of operations. Matrix elements is 0 if there is water or 1 if
there is land. Originally, the 2D matrix is all 0 which means there is no land in the matrix.
The array has k operator(s) and each operator has two integer A[i][0], A[i][1] means that
you can change the cell matrix[A[i][0]][A[i][1]] from sea to island. Return how many
island are there in the matrix after each operation.You need to return an array of size k.
Note : An island means group of 1s such that they share a common side.

Example 1:

Input: n = 4

m=5

k=4

A = {{1,1},{0,1},{3,3},{3,4}}

Output: 1 1 2 2

Explanation:

0. 00000

00000

00000

00000

1. 00000

01000

00000

00000

2. 01000

01000

00000

00000
3. 01000

01000

00000

00010

4. 01000

01000

00000

00011

Example 2:

Input: n = 4

m=5

k=4

A = {{0,0},{1,1},{2,2},{3,3}}

Output: 1 2 3 4

Explanation:

0. 00000

00000

00000

00000

1. 10000

00000

00000

00000

2. 10000

01000
 00000

00000

3. 10000

01000

00100

00000

4. 10000

01000

00100

00010

Your Task:
You don't need to read or print anything. Your task is to complete the function
numOfIslands() which takes an integer n denoting no. of rows in the matrix, an integer m
denoting the number of columns in the matrix and a 2D array of size k denoting the
number of operators.

Expected Time Complexity: O(m * n)

Expected Auxiliary Space: O(m * n)

Constraints:

1 <= n,m <= 100

5.10 27. Making A Large Island

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to
be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]

Output: 3

Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area =
3.

Example 2:

Input: grid = [[1,1],[1,0]]

Output: 4

Explanation: Change the 0 to 1 and make the island bigger, only one island with area =
4.

Example 3:

Input: grid = [[1,1],[1,1]]

Output: 4

Explanation: Can't change any 0 to 1, only one island with area = 4.

Constraints:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 500

• grid[i][j] is either 0 or 1.
5.11 78. Swim in Rising Water

You are given an n x n integer matrix grid where each value grid[i][j] represents the
elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim
from a square to another 4-directionally adjacent square if and only if the elevation of
both squares individually are at most t. You can swim infinite distances in zero time. Of
course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start
at the top left square (0, 0).

Example 1:

Input: grid = [[0,2],[1,3]]

Output: 3

Explanation:

At time 0, you are in grid location (0, 0).

You cannot go anywhere else because 4-directionally adjacent neighbors have a higher
elevation than t = 0.

You cannot reach point (1, 1) until time 3.

When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

Output: 16

Explanation: The final route is shown.

We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 50

• 0 <= grid[i][j] < n2

• Each value grid[i][j] is unique.

6.1 1192. Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-

server connections forming a network where connections[i] = [ai, bi] represents a
connection between servers ai and bi. Any server can reach other servers directly or
indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to
reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]]

Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]

Output: [[0,1]]

Constraints:

• 2 <= n <= 105

• n - 1 <= connections.length <= 105

• 0 <= ai, bi <= n - 1

 • ai != bi

• There are no repeated connections.

6.2 Articulation Point - I

Difficulty: HardAccuracy: 39.26%Submissions: 77K+Points: 8Average Time: 20m

Given an undirected connected graph with V vertices and adjacency list adj. You are
required to find all the vertices removing which (and edges through it) disconnects the
graph into 2 or more components and return it in sorted manner.
Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops
present in the graph.

Example 1:

Input:

Output:{1,4}

Explanation: Removing the vertex 1 will

discconect the graph as-

Removing the vertex 4 will disconnect the

graph as-
Your Task:
You don't need to read or print anything. Your task is to complete the
function articulationPoints() which takes V and adj as input parameters and returns a
list containing all the vertices removing which turn the graph into two or more
disconnected components in sorted order. If there are no such vertices then returns a
list containing -1.

Expected Time Complexity: O(V + E)

Expected Auxiliary Space: O(V)

Constraints:
1 ≤ V ≤ 105
6.3 Strongly Connected

Difficulty: MediumAccuracy: 50.61%Submissions: 109K+Points: 4Average Time: 20m

Given an adjacency list, adj of Directed Graph, Find the number of strongly connected
components in the graph.

Examples :

Input: adj[][] = [[2, 3], [0], [1], [4], []]

Output: 3

Explanation: We can clearly see that there are 3 Strongly Connected Components in
the Graph.

Input: adj[][] = [[1], [2], [0]]

Output: 1

Explanation: All of the nodes are connected to each other. So, there's only one SCC.

Input: adj[][] = [[1], []]

Output: 2

Constraints:
2<=adj.size()<=106
0<=edges<=adj.size()-1